BAB 2 GRAF PRIMITIF
Pada bagian ini akan dijelaskan mengenai definisi graf, istilah-istilah dalam graf, matriks ketetanggaan, graf terhubung, primitivitas graf, dan scrambling index. 2.1
Definisi Graf
Sebuah graf G terdiri atas suatu himpunanan tak kosong dan berhingga V (G) yang anggotanya disebut titik (vertex) dan sebuah himpunan berhingga E(G) yang anggotanya disebut sisi (edge) dimana sisi tersebut merupakan pasangan tak berurut dari titik-titik pada V (G). Sebuah sisi {v, w} adalah sisi yang menghubungkan titik v dan titik w, yang biasanya disingkat menjadi vw. Sebagai contoh, Gambar 2.1 merepresentasikan graf G dengan himpunan titik V (G) = {u, v, w, x, y} dan himpunan sisi E(G) yang terdiri dari sisi uw, ux, vx, vy, uy dan vw.
Gambar 2.1. Contoh Graf
2.2
Istilah-istilah dalam Graf
Andaikan terdapat sebuah graf G, berikut akan dijelaskan beberapa istilah dan notasi dalam graf yang digunakan dalam penjelasan selanjutnya. a. Jalan. Sebuah jalan merupakan sebuah barisan sisi yang berhingga dengan bentuk v0 v1 , v1 v2 , ..., vm−1 vm juga dapat dinotasikan dengan v0 ↔ v1 ↔ v2 ↔
Universitas Sumatera Utara
6 ... ↔ vm dimana v0 merupakan titik awal dan vm merupakan titik akhir. Sebuah jalan yang menghubungkan vi dan vj dinotasikan dengan Wvi vj . Pada Gambar 2.1, w ↔ v ↔ y ↔ v ↔ x adalah sebuah jalan Wwx . b. Panjang. Panjang dari sebuah jalan Wvi vj adalah banyaknya sisi di jalan Wvi vj dan dinotasikan dengan `(Wvi vj ). Pada Gambar 2.1, w ↔ u ↔ y ↔ v adalah sebuah jalan Wwv dengan panjang 3, atau dapat dinotasikan dengan `(Wwv ) = 4. c. Lintasan. Lintasan merupakan sebuah jalan dengan titik yang berbeda kecuali jika titik awal juga merupakan titik akhir (v0 = vm ). Lintasan yang menghubungkan vi dan vj dinotasikan dengan Pvi vj . Pada Gambar 2.1, u ↔ x ↔ v ↔ y adalah sebuah lintasan Puy dengan panjang 3 atau dapat dinotasikan dengan `(Puy ) = 3. d. Cycle. Cycle merupakan sebuah lintasan yang berawal dan berakhir pada titik yang sama. Pada Gambar 2.1, lintasan u ↔ y ↔ v ↔ w ↔ u adalah sebuah cycle dengan panjang 4. Sebuah cycle dengan panjang ganjil disebut cycle ganjil dan sebuah cycle dengan panjang genap disebut cycle genap. e. Distance. Panjang dari jalan terpendek yang menghubungkan u dan v di G disebut distance dinotasikan dengan d(u, v). Pada Gambar 2.1, diperoleh d(w, y) = 2.
2.3
Matriks Ketetanggaan
Matriks ketetanggaan (adjacency matrix) dari sebuah graf G atas n titik v1 , v2 , ..., vn adalah sebuah matriks bujur angkar A = (aij ) dengan ordo n yang setiap entrinya didefinisikan sebagai: 1, bila {vi , vj } ∈ E(G) aij = 0, bila {v , v } ∈ i j / E(G). Oleh definisi tersebut, diperoleh bahwa aij = aji . Hal ini berakibat matriks ketetanggaan A(G) dari sebuah graf G adalah sebuah matriks simetrik. Graf
Universitas Sumatera Utara
7 pada Gambar 2.1 dapat direpresentasikan menjadi matriks ketetanggaan A sebagai berikut:
0 1 1 1 0 1 1 1 1 0 0 0 . 1 0 0 0 1 0 0 0
0 0 A = 1 1 1
Sebuah matriks A dikatakan matriks non negatif jika semua entri (aij ) ≥ 0. Sedangkan sebuah matriks A dikatakan matriks positif jika semua entri (aij ) ≥ 1. Perhatikan contoh berikut: 1 1 X= 1 3
0 1 0 2 0 0 1 1 0 0 0 1
,
1 2 Y = 3 1
2 1 4 3 1 4 . 1 1 1 2 1 1
Matriks X merupakan matriks tak negatif karena semua entri (xij ) ≥ 0. Sedangkan matriks Y merupakan matriks positif karena semua entri (yij ) ≥ 1. Teorema 2.1 (Bona, 2006) Andaikan G adalah sebuah graf dan A = (aij ) adalah sebuah matriks ketetanggaan dari G. Misalkan akij adalah entri (i, j) dari matriks Ak . Maka akij menyatakan banyaknya jalan dengan panjang k yang menghubungkan titik i dengan titik j. Bukti. Kita buktikan dengan menggunakan induksi atas k. Bila k = 1 entri (1)
aij = aij dari A yang menyatakan banyaknya jalan dengan panjang satu yang (k)
menghubungkan titik i dengan titik j. Asumsikan bahwa entri aij dari Ak menyatakan banyaknya jalan dengan panjang k yang menghubungkan titik i dengan titik j. Karena Ak+1 = Ak A, maka (k+1) aij
=
n X
(k)
ai` a`j .
`=1 (k)
Untuk ` = 1, 2, ..., n, oleh hipotesis induksi dan prinsip perkalian ai` a`j adalah banyaknya jalan dengan panjang k + 1 yang melalui titik `. Sehingga oleh prinsip
Universitas Sumatera Utara
8 (k+1)
penjumlahan ai`
adalah banyaknya jalan dengan panjang k + 1 yang menghubu-
ngkan titik i dengan titik j. 2.4
Graf Terhubung
Sebuah graf G dikatakan terhubung (connected graph) jika untuk setiap titik u dan v di G dihubungkan oleh sebuah jalan dengan u dan v merupakan titik ujung. Sebaliknya, graf tidak terhubung (disconnected graph) merupakan graf terdapat sembarang titik yang tidak terhubung ke titik lainnya di G. Dengan kata lain, tidak terdapat yang jalan menghubungkan titik tersebut ke titik yang lain di G.
Gambar 2.2. (a) Graf Terhubung dan (b) Graf tidak Terhubung Graf pada Gambar 2.2(a) merupakan graf terhubung, karena untuk tiap titik terdapat jalan yang menghubungkan antara satu titik ke titik lainnya. Sedangkan graf pada Gambar 2.2(b) merupakan graf tidak terhubung, karena tidak terdapat jalan yang menghubungkan satu titik dengan titik lainnya seperti v3 ke v4 , v2 ke v3 dan lainnya. Teorema 2.2 (Bona, 2006) Andaikan G adalah sebuah graf atas n titik dengan matriks ketetanggaan A. Graf G adalah terhubung jika dan hanya jika matriks A + A2 + ... + An−1 mempunyai entri yang semuanya positif. Bukti. Andaikan G adalah sebuah graf terhubung dengan n titik dan misalkan B = A + A2 + ... + An−1 . Karena G adalah graf terhubung, maka untuk setiap pasangan titik i dan j terdapat sebuah lintasan yang menghubungkan titik i dan
Universitas Sumatera Utara
9 titik j. Sebuah lintasan di G tidak terdapat titik berulang kecuali i = j, bila i 6= j terdapat lintasan dengan panjang kurang dari n yang menghubungkan i dengan j. Hal ini berarti untuk setiap pasangan titik i dan j yang berbeda, terdapat sebuah bilangan bulat positif k dengan 1 ≤ k ≤ n − 1 sehingga entri akij > 0. Sehingga semua entri di luar entri diagonal dari matriks B adalah positif. Bila i = j, maka (2)
terdaoat sebuah cycle dengan panjang 2 yang memuat titik i, sehingga entri aij > 0 untuk semua i = 1, 2, ..., n. Jadi entri diagonal dari matriks B adalah positif. Sekarang dapat disimpulkan bahwa semua entri dari matriks B = A+A2 +...+An−1 adalah positif. Sekarang andaikan setiap entri dari matriks A + A2 + ... + An−1 adalah positif. Akibatnya untuk setiap pasangan titik i dan j terdapat sebuah bilangan positif k dengan 1 ≤ k ≤ n − 1 sehingga akij > 0. Hal ini berarti untuk setiap pasangan titik i dan j di G terdapat sebuah jalan dengan panjang k yang menghubungkan i dan j. Sehingga oleh definisi G adalah sebuah graf terhubung. 2.5
Primitivitas Graf
Graf primitif merupakan graf terhubung dimana terdapat bilangan bulat positif k sehingga untuk setiap pasangan titik u dan v terdapat sebuah jalan Wuv dengan panjang k. Sebuah graf G dikatakan primitif jika G merupakan graf terhubung dan terdapat paling sedikit satu cycle ganjil (Liu et al., 1990).
Gambar 2.3. (a) Graf Primitif dan (b) Graf tidak Primitif
Universitas Sumatera Utara
10 Graf pada Gambar 2.3(a) merupakan graf primitif, karena terdapat cycle dengan panjang ganjil. Sedangkan graf pada Gambar 2.3(b) bukan merupakan graf primitif, karena tidak terdapat cycle dengan panjang ganjil. Sebuah graf G dapat direpresentasikan menjadi sebuah matriks ketetanggaan A. Sebuah matriks persegi non negatif A dikatakan primitif jika terdapat bilangan bulat k sedemikian hingga semua entri di Ak bernilai positif (Brualdi dan Ryser, 1991). Graf pada Gambar 2.3(a) dapat direpresentasikan menjadi matriks persegi non negatif A sebagai berikut: 0 1 1 A= 0 0 0
1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1
0 0 1 . 0 1 0
Untuk memperlihatkan bahwa matriks A merupakan matriks primitif, maka akan diperlihatkan terdapat bilangan bulat positif terkecil k sehingga semua entri di Ak bernilai positif. Dengan kata lain, matriks Ak merupakan matriks positif. Perhatikan matriks A4 berikut :
9 8 10 6 8 8 8 9 10 6 8 8 10 10 29 4 10 10 4 A = 6 6 4 5 6 6 . 8 8 10 6 9 8 8 8 10 6 8 9 Diperoleh bahwa setiap entri di matriks A4 bernilai positif. Karena terdapat bilangan bulat positif k sehingga matriks Ak merupakan matriks positif, maka matriks A adalah primitif.
Universitas Sumatera Utara
11
2.6
Scrambling Index
Scrambling index dari graf primitif G dinotasikan dengan k(G) adalah bilangan bulat positif terkecil k sehingga untuk setiap pasangan titik yang berbeda u dan v, terdapat sebuah titik w sehingga terdapat jalan dari titik u dan titik v ke titik w dengan panjang k atau dengan kata lain terdapat Wuw dan Wvw dengan panjang k (Alkebek dan Kirkland 2009a, 2009b). Untuk setiap u, v ∈ V (G) dan u 6= v, scrambling index lokal dari titik u dan v di G didefinisikan sebagai berikut: ku,v (G) = min {k : terdapat Wuw dan Wvw dengan panjang k}. w∈V (G)
Jika scrambling index lokal dari titik u dan v di G adalah ku,v (G), maka untuk setiap k 0 ≥ ku,v (G), terdapat titik w0 sehingga terdapat Wuw0 dan Wvw0 dengan panjang k 0 . Sehingga scrambling index dari graf G didefinisikan sebagai berikut: k(G) = max {ku,v (G)}. u,v∈V (G)
Contoh 2.1 Andaikan G adalah graf yang terdiri dari sebuah cycle dengan panjang 5 seperti pada Gambar 2.4.
Gambar 2.4. Graf yang Terdiri Atas Sebuah Cycle dengan Panjang 5 Scrambling index dari graf G dapat diselesaikan dengan menentukan scrambling index lokal untuk tiap dua titik yang berbeda pada graf G terlebih dahulu.
Universitas Sumatera Utara
12 kv1 ,v2 (G) = min{kv1 ,v2 (v1 ), kv1 ,v2 (v2 ), kv1 ,v2 (v3 ), kv1 ,v2 (v4 ), kv1 ,v2 (v5 )} = min{4, 4, 3, 2, 3} = 2 kv1 ,v3 (G) = min{kv1 ,v3 (v1 ), kv1 ,v3 (v2 ), kv1 ,v3 (v3 ), kv1 ,v3 (v4 ), kv1 ,v3 (v5 )} = min{2, 1, 2, 3, 3} = 1 kv1 ,v4 (G) = min{kv1 ,v4 (v1 ), kv1 ,v4 (v2 ), kv1 ,v4 (v3 ), kv1 ,v4 (v4 ), kv1 ,v4 (v5 )} = min{2, 3, 3, 2, 1} = 1 kv1 ,v5 (G) = min{kv1 ,v5 (v1 ), kv1 ,v5 (v2 ), kv1 ,v5 (v3 ), kv1 ,v5 (v4 ), kv1 ,v5 (v5 )} = min{4, 3, 2, 3, 4} = 2 kv2 ,v3 (G) = min{kv2 ,v3 (v1 ), kv2 ,v3 (v2 ), kv2 ,v3 (v3 ), kv2 ,v3 (v4 ), kv2 ,v3 (v5 )} = min{3, 4, 4, 3, 2} = 2 kv2 ,v4 (G) = min{kv2 ,v4 (v1 ), kv2 ,v4 (v2 ), kv2 ,v4 (v3 ), kv2 ,v4 (v4 ), kv2 ,v4 (v5 )} = min{3, 2, 1, 2, 3} = 1 kv2 ,v5 (G) = min{kv2 ,v5 (v1 ), kv2 ,v5 (v2 ), kv2 ,v5 (v3 ), kv2 ,v5 (v4 ), kv2 ,v5 (v5 )} = min{1, 2, 3, 3, 2} = 1 kv3 ,v4 (G) = min{kv3 ,v4 (v1 ), kv3 ,v4 (v2 ), kv3 ,v4 (v3 ), kv3 ,v4 (v4 ), kv3 ,v4 (v5 )} = min{2, 3, 4, 4, 3} = 2 kv3 ,v5 (G) = min{kv3 ,v5 (v1 ), kv3 ,v5 (v2 ), kv3 ,v5 (v3 ), kv3 ,v5 (v4 ), kv3 ,v5 (v5 )} = min{3, 3, 2, 1, 2} = 1 kv3 ,v5 (G) = min{kv4 ,v5 (v1 ), kv4 ,v5 (v2 ), kv4 ,v5 (v3 ), kv4 ,v5 (v4 ), kv4 ,v5 (v5 )} = min{3, 2, 3, 4, 4} = 2 Setelah memperoleh scrambling index lokal untuk tiap dua titik yang berbeda di graf G, selanjutnya adalah menentukan scrambling index untuk graf G.
k(G) =
max {kvi ,vj (G)} = max{2, 1, 1, 2, 2, 1, 1, 2, 1, 2} = 2.
vi ,vj ∈V (G)
Scrambling index dari matriks primitif A adalah bilangan bulat positif terkecil k sehingga untuk setiap dua baris di Ak terdapat sedikitnya satu entri positif pada posisi kolom yang sama (Alkebek dan Kirkland 2009a, 2009b). Pada Gambar 2.5, graf G dapat direpresentasikan menjadi matriks ketetanggan M seperti berikut:
Universitas Sumatera Utara
13
0 1 M = 0 0 1
1 0 0 1 0 1 0 0 1 0 1 0 . 0 1 0 1 0 0 1 0
Untuk k = 1, pada baris pertama dan kedua di M k = M tidak terdapat bilangan positif pada kolom yang sama. Sehingga, perlu dicari bilangan bulat positif k > 1, sehingga untuk setiap dua baris di M k terdapat sedikitnya satu entri positif pada posisi kolom yang sama. Perhatikan matriks M 2 berikut: 2 0 2 M = 1 1 0
0 1 1 0 2 0 1 1 0 2 0 1 . 1 0 2 0 1 1 0 2
• Pada baris pertama dan baris kedua, terdapat entri positif pada kolom yang sama yaitu kolom keempat. • Pada baris pertama dan baris ketiga, terdapat entri positif pada kolom yang sama yaitu kolom pertama dan ketiga. • Pada baris pertama dan baris keempat, terdapat entri positif pada kolom yang sama yaitu kolom pertama dan keempat. • Pada baris pertama dan baris kelima, terdapat entri positif pada kolom yang sama yaitu kolom ketiga. • Pada baris kedua dan baris ketiga, terdapat entri positif pada kolom yang sama yaitu kolom kelima. • Pada baris kedua dan baris keempat, terdapat entri positif pada kolom yang sama yaitu kolom kedua dan keempat.
Universitas Sumatera Utara
14 • Pada baris kedua dan baris kelima, terdapat entri positif pada kolom yang sama yaitu kolom kedua dan kelima. • Pada baris ketiga dan baris keempat, terdapat entri positif pada kolom yang sama yaitu kolom pertama. • Pada baris ketiga dan baris kelima, terdapat entri positif pada kolom yang sama yaitu kolom ketiga dan kelima. • Pada baris keempat dan baris kelima, terdapat entri positif pada kolom yang sama yaitu kolom kedua. Oleh karena 2 merupakan bilangan bulat positif terkecil sehingga setiap dua baris di M 2 terdapat elemen positif pada posisi kolom yang sama, maka scrambling index dari matriks M adalah 2. Proposisi 2.3 Andaikan G adalah sebuah graf dan k 0 adalah bilangan bulat genap positif. Jika untuk tiap pasangan titik yang berbeda u dan v di G, terdapat sebuah jalan dengan panjang genap Wuv ≤ k 0 , maka k(G) ≤ k 0 /2. Bukti. Andaikan u dan v adalah dua titik yang berbeda di G dan andaikan Wuv adalah jalan dengan panjang genap u = v0 ↔ v1 ↔ v2 ↔ ... ↔ v2m−1 ↔ v2m = v untuk beberapa bilangan bulat positif m dengan panjang `(Wuv ) ≤ k 0 . Andaikan C2 0 adalah cycle v2m ↔ v2m−1 ↔ v2m dengan panjang 2. Maka jalan Wuv yang berawal
di u, bergerak ke v sepanjang jalan Wuv dan bergerak k 0 − `(Wuv ) kali disekitar C2 adalah sebuah sebuah Wuv dengan panjang k 0 . Karena k 0 adalah genap, maka terdapat sebuah titik w sehingga terdapat sebuah jalan Wuw dengan panjang terdapat sebuah jalan Wvw dengan panjang
k0 2
. Sehingga k(G) ≤
k0 2
.
k0 2
dan
Universitas Sumatera Utara
