bab iii determinan matriks ketetanggaan dari graf lolipop dan

12

BAB III

Determinan Matriks Ketetanggaan dari Graf Lolipop ( ) dan ( )

Pada bab ini akan dijelaskan mengenai determinan matriks ketetanggan dari graf

lollipop ( ) dan ( ).

3.1 Determinan Matriks Ketetanggaan dari Graf Lolipop ( )

Secara umum, matriks ketetanggaan dari graf lollipop dengan dan

dapat dituliskan sebagai ( ( )). Matriks ( ( )) merupakan

matriks berukuran dengan yang dapat dinyatakan sebagai

berikut.

( ( ))

[ ]

Matriks ketetanggaan ( ( )) dapat dinyatakan dalam bentuk partisi

matriks seperti berikut.

( ( )) [ ( ) ( ) ( ) ( )

]

, untuk

dengan

adalah matriks yang berukuran yang semua entrinya bernilai 1,

[

].

adalah matriks identitas yang berukuran , [

].

Sehingga [

] dan ( ) .

13

( ) ( )merupakan matriks tridiagonal,

( ) ( )

[

]

Matriks ( ) merupakan matriks yang semua entrinya bernilai 0

kecuali pada baris ketiga kolom pertama bernilai 1,

( ) [

]

Matriks ( ) merupakan matriks yang semua entrinya bernilai 0

kecuali pada baris pertama kolom ketiga bernilai 1,

( ) [

]

Invers dari matriks dapat ditentukan dengan menggunakan metode

Eliminasi Gauss-Jordan sebagai berikut:

[

]

( )

[

]

[

]

( ) [

]

( ) [

]

[

]

14

( ) [

]

( )

[

]

Sehingga diperoleh ( )

[

]

.

Untuk mendapatkan matriks ( )( ) ( ) diperlukan

beberapa tahapan seperti berikut:

1. [

]

[

]

[

]

Hasil kali pada akan memindahkan baris ketiga pada ke

baris pertama pada matriks .

2. ( ) [

] [

]

[

]

Pada matriks akan muncul nilai 0 kecuali pada baris ke-3 kolom

ke-1 yang bernilai 1. Hal ini akan menyebabkan, perkalian antara

( ) dan diperoleh nilai

pada baris ke-1 kolom ke-1.

Berdasarkan hasil tersebut, diperoleh matriks sebagai berikut.

[ ]

[

]

15

[

]

Lema 3.1 Misalkan ( ( )) menyatakan matriks ketetanggaan dari graf lolipop

( )dengan ( ( )) [ ( ) ( ) ( ) ( )

]

,untuk

( )

{

Bukti:

Matriks dapat ditentukan dengan melakukan ekspansi kofaktor

sebagai berikut.

1. Kasus I, jika

Dengan melakukan ekspansi kofaktor sepanjang baris pertama, diperoleh

( )

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

16

( ) ( )

.

Dengan demikian, ( )

jika .

2. Kasus II, jika

Dengan melakukan ekspansi kofaktor sepanjang baris pertama, diperoleh

( )

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

( ) ( )

Dengan demikian, ( )

jika .

3. Kasus III, jika

Dengan melakukan ekspansi kofaktor sepanjang baris kedua, diperoleh

( )

|

|

|

|

|

|

17

|

|

|

|

|

|

|

|

|

|

|

|

(( ) ) (( ) ) .

Dengan demikian, ( ) jika .

4. Kasus 4, jika

Dengan melakukan ekspansi kofaktor sepanjang baris kedua, diperoleh

( )

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

(( ) ( )) (( ) )

Dengan demikian, ( ) jika .

Berdasarkan keempat kasus tersebut diperoleh teorema mengenai

( ( ( ))) seperti berikut.

18

Teorema 3.1.1

( ( ( ))) {

Bukti:

Misalkan [

]. Telah dijelaskan sebelumnya bahwa ( ) .

Berdasarkan Lema 3.1, diperoleh ( )

{

Karena ( ( )) dinyatakan sebagai ( ( )) [ ( ) ( ) ( ) ( )

]

,

untuk maka,

( ( )) 0

1 ( ) ( )

1. Jika

( ( ( )) ( ) ( )

2. Jika

( ( ( )) ( ) ( )

3. Jika

( ( ( )) ( ) ( )

19

4. Jika

( ( ( )) ( ) ( )

Contoh 3.1.1 Pada contoh ini akan ditunjukkan bahwa nilai determinan matriks

ketetanggaan graf lolipop ( ) sesuai dengan hasil yang dikemukakan pada

Teorema 3.1.1.

Gambar 3.1.1 Graf Lolipop ( ).

Matriks ketetanggaan dari graf lolipop ( ) adalah

( ( )) [

]

dengan ( ( )) dapat dinyatakan dalam bentuk partisi matriks ( ( ))

0

1

[

]

( ) [ ]

( ) , -

( ) ( ) , -

20

Diperoleh,

( ) [

] 2 dan =

[

]

.

Akibatnya,

( ) , - , -

[

]

[ ] [

]

Dengan demikian, ( )

sehingga ( ( )) ( ) ( ) (

) .

Contoh 3.1.2 Pada contoh ini akan ditunjukkan bahwa nilai determinan matriks

ketetanggaan graf lolipop ( ) sesuai dengan hasil yang dikemukakan pada

Teorema 3.1.1.

Gambar 3.1.2 Graf Lolipop ( ).

Matriks ketetanggaan dari graf lolipop ( ) adalah

( ( ))

[

]

21

dengan ( ( )) dapat dinyatakan dalam bentuk partisi matriks ( ( ))

0

1.

[

]

( ) [

]

( ) 0

1

( ) ( ) 0

1

Diperoleh,

( ) [

] 2 dan =

[

]

.

Akibatnya,

( ) 0

1 0

1

[

]

[

] [

]

Dengan demikian, ( )

sehingga ( ( )) ( ) ( ) ( )

22

3.2 Determinan Matriks Ketetanggaan dari Graf Lolipop ( )

Secara umum, matriks ketetanggaan dari graf lolipop dengan dan

dapat dituliskan sebagai ( ( )). Matriks ( ( )) merupakan

matriks berukuran dengan yang dapat dinyatakan sebagai

berikut.

( ( )) =

[ ]

Matriks ketetanggaan ( ( )) dapat dinyatakan dalam bentuk partisi

matriks seperti berikut..

( ( )) [ ( ) ( ) ( ) ( )

]

,untuk

dengan

adalah matriks yang berukuran yang semua entrinya bernilai 1,

[

].

adalah matriks identitas yang berukuran , [

]

Sehingga [

] dan ( ) .

( ) ( ) merupakan matriks tridiagonal,

23

( ) ( )

[

]

( ) merupakan matriks yang semua entrinya bernilai 0 kecuali pada

baris ketiga kolom pertama bernilai 1,

( ) [

]

( ) merupakan matriks yang semua entrinya bernilai 0 kecuali pada

baris pertama kolom ketiga bernilai 1,

( )

[

]

Invers dari matriks dapat ditentukan dengan menggunakan metode

Eliminasi Gauss-Jordan sebagai berikut:

[

]

( )

[

]

[

]

( ) [

]

( ) [

]

24

( ) [

]

( ) [

]

( )

[

]

(( ) )

[

]

(

)

[

]

.

/

[

]

( )

[

]

( )

[

]

25

( )

[

]

( )

[

]

Sehingga, diperoleh ( )

[

]

Untuk mendapatkan matriks ( )( ) ( ) diperlukan

beberapa tahapan seperti berikut.

1.

[

]

[

]

[

]

Hasil kali pada akan memindahkan baris 3 pada ke baris ke-

1 pada matriks C.

2. ( )

[

]

[

]

[

]

26

Pada matriks akan muncul nilai 0 kecuali pada baris ke-3 kolom ke-

1 yang bernilai 1. Hal ini akan menyebabkan, perkalian antara

( ) dan diperoleh nilai

pada baris ke-1 kolom ke-1.

Berdasarkan hasil tersebut, diperoleh matriks sebagai

berikut.

[ ]

[

]

[

]

Lema 3.2 Misalkan ( ( )) menyatakan matriks ketetanggaan dari graf lolipop

( ) dengan ( ( )) [ ( ) ( ) ( ) ( )

]

,untuk .

( )

{

Bukti:

Determinan matriks dapat ditentukan dengan melakukan ekspansi

kofaktor sebagai berikut.

1. Kasus I, jika

Dengan melakukan ekspansi kofaktor sepanjang baris pertama, diperoleh

27

( )

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

( ) ( )

.

Dengan demikian, ( )

jika .

2. Kasus II, jika

Dengan melakukan ekspansi kofaktor sepanjang baris pertama, diperoleh

( )

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

( ) ( )

.

Dengan demikian, ( )

jika

28

3. Kasus III, jika

Dengan melakukan ekspansi kofaktor sepanjang baris kedua, diperoleh

( )

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

(( ) ) (( ) )

Dengan demikian, ( ) jika .

4. Kasus 4, jika

Dengan melakukan ekspansi kofaktor sepanjang baris kedua, diperoleh

( )

[

]

29

|

|

|

|

|

|

|

|

|

|

|

|

(( ) ( )) (( ) )

Dengan demikian, ( ) jika

Berdasarkan keempat kasus tersebut diperoleh teorema mengenai

( ( ( ))) seperti berikut.

Teorema 3.2.1

( ( )) {

Bukti:

Misalkan [

]. Telah dijelaskan sebelumnya bahwa ( )

.

Berdasarkan Lema 3.2, diperoleh ( )

{

Karena ( ( )) dinyatakan sebagai ( ( )) [ ( ) ( ) ( ) ( )

]

untuk maka,

( ( )) 0

1 ( ) ( ) .

1. Jika

( ( ( )) ( ) ( )

30

2. Jika

( ( ( )) ( ) ( )

3. Jika

( ( ( )) ( ) ( )

4. Jika

( ( ( )) ( ) ( )

Contoh 3.2.1 Pada contoh ini akan ditunjukkan bahwa nilai determinan matriks

ketetanggaan graf lolipop ( ) sesuai dengan hasil yang dikemukakan pada

Teorema 3.2.1.

Gambar 3.2.1 Graf lolipop ( ).

Matriks ketetanggaan dari graf lolipop ( ) adalah

31

( ( ))

[

]

dengan ( ( )) dapat dinyatakan dalam bentuk partisi matriks ( ( ))

0

1

[

]

( ) [

]

( ) , -

( ) ( ) , -

Diperoleh,

( ) [

] dan

[

]

Akibatnya,

( ) , - , -

[

]

[

] 0

1

Dengan demikian, ( )

32

sehingga ( ) ( ) .

/

Contoh 3.2.2 Pada contoh ini akan ditunjukkan bahwa nilai determinan matriks

ketetanggaan graf lolipop ( ) sesuai dengan hasil yang dikemukakan pada

Teorema 3.2.1.

Gambar 3.2.2 Graf lolipop ( ).

Matriks ketetanggaan dari graf lolipop ( ) adalah

( ( ))

[

]

dengan ( ( )) dapat dinyatakan dalam bentuk partisi matriks ( ( ))

0

1

[

]

( ) [

]

( ) 0

1

( ) ( ) 0

1

Diperoleh,

33

( ) [

] dan

[

]

.

Akibatnya,

( ) 0

1 (0

1

[

]

[

]

[

].

Dengan demikian, ( )

sehingga ( ) ( ) ( )