BAB 2 GRAF PRIMITIF
Pada bab ini akan dijelaskan beberapa konsep dasar seperti definisi dan teorema yang dijadikan landasan teori dalam penelitian ini. Konsep dasar tersebut berkaitan dengan definisi graf, terhubung kuat, primitifitas, graf primitif jarang, dan scrambling index. 2.1 Definisi Graf Pada subbab ini akan diberikan definisi tentang graf serta notasi-notasi yang akan dipergunakan dalam pembahasan selanjutnya. Secara sederhana, graf dinotasikan dengan G merupakan himpunan tak kosong dari titik-titik selanjutnya disebut vertex yang dihubungkan oleh garis selanjutnya disebut edge dari graf G tersebut. Secara matematika, sebuah graf G terdiri dari dua himpunan, yaitu: 1. Himpunan vertex yang dinotasikan dengan V = {v1 , v2 , · · · , vn } dengan i adalah bilangan bulat positif dan vi adalah elemen dari himpunan V dan n(V ) 6= 0. 2. Himpunan edge dari graf G yang dinotasikan dengan E merupakan himpunan bagian dari pasangan tak berurut dari elemen-elemen di V . Jika diberikan notasi e = (v1 , v2 ) adalah sebuah edge dari graf G, maka v1 disebut sebagai vertex awal dan v2 sebagai vertex akhir. Contoh 2.1 Perhatikan himpunan vertex V = {v1 , v2 , v3 , v4 , v5 } bersama dengan himpunan bagian pasangan tak berurut E = {{v1 , v2 }, {v1 , v3 }, {v1 , v4 }, {v1 , v5 }, {v2 , v3 }, {v4 , v5 }}. Pasangan G(V, E) adalah sebuah graf dengan 5 vertex dan 6 edge dan direpresentasikan seperti pada Gambar 2.1.
5 Universitas Sumatera Utara
6
Gambar 2.1 : Graf dengan 5 vertex dan 6 edge
Andaikan G sebuah graf. Misalkan u dan v adalah vertex di G. Sebuah jalan dengan panjang m dari u ke v adalah sebuag barisan m edge dalam bentuk u = v0 ↔ v1 ↔ · · · ↔ vm−1 ↔ vm = v Dengan m ≥ 0, v0 = u dan vm = v. Jika u = v maka jalan tersebut dikatakan jalan tertutup dan jika u 6= v maka jalan tersebut dikatakan jalan terbuka. Sebuah lintasan adalah sebuah jalan tanpa perulangan vertex kecuali mungkin kedua vertex ujungnya. Jika kedua vertex ujungnya sama maka dinamakan lintasan tertutup atau lebih dikenal dengan sebuah lingkaran. Loop adalah lingkarang yang panjangnya satu. Dengan menggunakan graf pada Contoh 2.1 akan dijelaskan beberapa definisi diatas. 1. Barisan edge v1 ↔ v2 ↔ v3 ↔ v1 ↔ v4 ↔ v5 adalah sebuah jalan yang menghubungkan v1 dengan v5 , tetapi bukan sebuah lintasan karena ada perulangan vertex v1 . 2. Barisan edge v3 ↔ v1 ↔ v4 adalah sebuah lintasan dari v3 ke v4 . 3. Barisan edege v1 ↔ v2 ↔ v3 ↔ v1 adalah sebuah lingkaran.
2.2 Matriks Ketetanggan dari Graf Sebuah graf G atas n vertex dapat direpresentasikan dalam (0,1)-matriks, yaitu matriks yang entrinya 0 atau 1. Matriks yang demikian disebut dengan matriks ketetanggaan.
Universitas Sumatera Utara
7 Sebuah matriks ketetanggaan dari graf G atas n vertex adalah matriks berorde n, A(G) = [aij ] dengan 1, jika terdapat edge dari vi ke vj di G aij = 0, vertex lainnya Contoh 2.2 Perhatikan graf G pada gambar di bawah ini.
Gambar 2.2 : Graf dengan 6 vertex dan 7 edge
Matriks ketetanggaan dari graf di atas adalah sebagai berikut.
A(D) =
0 1 1 0 0 0
1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0
2.3 Primitifitas dari Graf Terhubung Sebuah graf G dikatakan terhubung jika untuk setiap pasangan vertex u dan v di G terdapat jalan yang menghubungkan u dan v, sebaliknya graf G dikatakan tidak
Universitas Sumatera Utara
8 terhubung jika terdapat sebarang satu vertex atau lebih sehingga tidak terdapat jalan dari u dan v. Contoh 2.3 Berikut contoh graf terhubung dan tidak terhubung.
Gambar 2.3 : (a) Graf terhubung dan (b) graf tidak terhubung
Gambar 2.3(a) menunjukan graf terhubung karena terdapat jalan dari setiap pasangan vertex di G, dan gambar 2.3(b) menunjukan graf yang tidak terhubung karena tidak terdapat jalan yang menghubungkan v5 dengan vertex lainnya.
Berikut diberikan syarat perlu dan cukup agar satu graf terhubung G adalah graf primitif.
Teorema 2.1 Andaikan G adalah suatu graf. Graf G dikatakan primitif jika dan hanya jika terhubung dan mengandung lingkaran ganjil.
Bukti. Andaikan G adalah suatu graf. Andaikan graf G adalah primitif, maka terdapat bilangan bulat positif k sehingga untuk setiap pasangan vertex u dan vertex v di G terdapat jalan dari vertex u ke vertex v di G dengan panjang k. Hal ini berakibat G adalah terhubung. Perhatikan bahwa untuk setiap pasangan vertex u dan vertex v di G terdapat jalan dengan panjang m untuk semua bilangan m > k. Andaikan m adalah ganjil. Untuk setiap vertex u dan v di G dapat dibentuk jalan dengan panjang ganjil. Andaikan u ↔ u adalah jalan yang menghubungkan vertex u ke dirinya sendiri. Misalkan puv adalah lintasan yang menghubungkan vertex u ke vertex v. Jalan u ↔ v dapat dibentuk dari vertex u ke vertex v melalui lintasan puv
Universitas Sumatera Utara
9 dan kembali ke vertex u melalui lintasan puv yang sama. Andaikan l(wuu ) adalah panjang jalan dari vertex u ke u. Perhatikan bahwa l(wuu ) adalah genap. Agar wuu mempunyai panjang ganjil maka wuu hrus melewati satu lingkaran ganjil disebarang vertex, misalnya vertex x. Jalan wuu yang terdiri dari lintasan pux , lintasan pxx , dan lintasan pxu adalah suatu jalan wuu dengan panjang ganjil. Sehingga untuk setiap vertex u dan v di G haruslah mempunyai lingkaran ganjil. Contoh 2.4 Berikut contoh graf primitif
Gambar 2.4 : Contoh graf primitif
Graf diatas merupakan graf primitif karena memuat lingkaran dengan panjang ganjil yakni lingkaran v1 → v2 → v3 → v1 dengan panjang 3.
Sebuah graf primitif dikatakan graf primitif jarang bila graf primitif tersebut dibentuk dengan jumlah edge yang minimum.
Universitas Sumatera Utara
10 Contoh 2.5 Berikut contoh graf primitif jarang
Gambar 2.5 : Graf dengan 5 vertex dan 6 edge
Gambar 2.6 : Graf dengan 5 vertex dan 7 edge
Kedua graf diatas merupakan graf dengan 5 vertex dan scrambling index 1. Gambar 2.5 dibentuk dengan 6 edge, sedangkan Gambar 2.6 dibentuk dengan 7 edge sehingga graf pada Gambar 2.5 merupakan graf primitif jarang karena dibentuk dengan jumlah edge yang minimum dibandingkan dengan graf pada Gambar 2.6.
2.4 Matriks Tak Negatif Matriks tak negatif A merupakan sebuah mariks yang setiap entri aij dari A adalah bilangan bulat tak negatif, sebaliknya jika setiap entri aij dari matriks A adalah bilangan bulat positif maka matriks tersebut disebut matriks positif. Perhatikan dua buah matriks berikut ini.
Universitas Sumatera Utara
11
0 3 5
P = 7 5 9 8 1 0 matriks 13 Q= 17 9
tak negatif 5 5 5 1 11 10
matriks positif 2.5 Scrambling Index Graf Primitif 2.5.1 Scrambling Index Lokal Graf Primitif Untuk u, v ∈ V (G)(u 6= v), scrambling index lokal dari setiap pasangan dua vertex berbeda di G didefinisikan sebagai, k
k
ku,v (G) =min{k : u ↔ w dan v ↔ w untuk semua w ∈ V (G)} 2.5.2 Scrambling Index Graf Primitif Scrambling index dari sebuah graf primitif G, dinotasikan dengan k(G), adalah bilangan bulat positif terkecil k sehingga untuk setiap pasangan dua vertex u dan v yang berbeda terdapat sebuah vertex w dengan sifat terdapat sebuah jalan dari u ke w dan sebuah jalan dari v ke w dengan panjang k, atau k(G) = max {ku,v (G)} u,v∈V (G)
Dari definisi diperoleh hubungan ku,v (G) ≤ k(G).
Universitas Sumatera Utara
12 Contoh 2.6 Perhatikan Contoh 2.2 Menurut definisi, diperoleh scrambling index
lokal dari graf primitif di atas sebagai berikut, kv1 ,v2 (G) =min{2, 2, 1, 2, 3, 2} = 1 kv1 ,v3 (G) =min{2, 1, 2, 3, 4, 3} = 1 kv1 ,v4 (G) =min{2, 2, 1, 2, 3, 2} = 1 kv1 ,v5 (G) =min{3, 3, 2, 3, 4, 3} = 2 kv1 ,v6 (G) =min{2, 2, 1, 2, 3, 2} = 1 kv2 ,v3 (G) =min{1, 2, 2, 4, 4, 3} = 1 kv2 ,v4 (G) =min{2, 2, 1, 2, 3, 2} = 1 kv2 ,v5 (G) =min{3, 3, 2, 3, 4, 3} = 2 kv2 ,v6 (G) =min{2, 2, 1, 2, 3, 2} = 1 kv3 ,v4 (G) =min{2, 2, 3, 4, 4, 4} = 2 kv3 ,v5 (G) =min{3, 3, 2, 1, 2, 1} = 1 kv3 ,v6 (G) =min{2, 2, 3, 4, 5, 4} = 2 kv4 ,v5 (G) =min{3, 3, 4, 5, 6, 5} = 3 kv4 ,v6 (G) =min{2, 2, 1, 2, 1, 2} = 1 kv5 ,v6 (G) =min{3, 3, 4, 5, 6, 5} = 3 Dari definisi diperoleh k(G) = max {ku,v (G)} = 3 u,v∈V (G)
Scrambling index dari graf primitif G dapat dicari menggunakan matriks ketetanggaan A(G). Jika untuk setiap dua baris pada A(G)k terdapat sedikitnya satu entri yang nilainya positif pada kolom yang sama maka k merupakan scrambling index dari graf primitif G.
Universitas Sumatera Utara
13 Contoh 2.7 Perhatikan Contoh 2.2 1. Untuk k = 1, diperoleh 1 A =
0 1 1 0 0 0
1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0
Graf pada Contoh 2.2 tidak memiliki scrambling index 1, karena setidaknya ada dua baris pada matriks A1 , yaitu baris pertama dan baris kelima tidak memiliki entri positif pada kolom yang sama. 2. Untuk k = 2, diperoleh 2 A =
2 1 1 1 0 1
1 2 1 1 0 1 1 1 4 0 2 0 1 1 0 2 0 2 0 0 2 0 2 0 1 1 0 2 0 2
Graf pada Contoh 2.2 tidak memiliki scrambling index 2, karena setidaknya ada 2 baris pada matriks A2 , yaitu baris keempat dan baris kelima tidak memiliki entri positif pada kolom yang sama. 3. Untuk k = 3, diperoleh 3 A =
2 3 5 1 2 1
3 2 5 1 2 1 5 5 2 6 0 6 1 1 6 0 4 0 2 2 0 4 0 4 1 1 6 0 4 0
Universitas Sumatera Utara
14
Graf pada Contoh 2.2 memiliki scrambling index 3, karena untuk setiap 2 baris pada matriks A3 setidaknya terdapat satu entri positif pada kolom yang sama.
Universitas Sumatera Utara
