BAB 2 TINJAUAN PUSTAKA
Pada bagian ini akan dijelaskan beberapa konsep dasar yang berkaitan dengan permasalahan, seperti definisi dan teorema yang dijadikan landasan dalam penelitian ini.
2.1 Graf Graf G adalah pasangan (V (G), E(G)) dengan V (G) adalah himpunan tidak kosong dan berhingga dari objek-objek yang disebut titik, dan E(G) adalah himpunan (mungkin kosong) pasangan tak berurut dari titik-titik yang berbeda di V (G) yang disebut sisi (Abdusakir et al.,2009). Titik disajikan dalam bentuk noktah atau lingkaran kecil dan sisi disajikan dalam bentuk garis atau kurva yang memasangkan dua titik. Titik pada graf dapat dinomori dengan huruf, seperti a, b, c, · · · , u, v, · · · , dengan bilangan asli, 1, 2, 3, · · · atau gabungan keduanya. Sedangkan sisi yang menghubungkan titik u dengan titik v dinyatakan dengan pasangan (u, v) atau dinyatakan dengan lambang e1 , e2 , · · · . Jadi, jika e adalah sisi yang menghubungkan titik u dan titik v, maka e dapat ditulis sebagai e = (u, v), u dan v disebut sebagai titik ujung dari sisi e. Sisi-sisi yang memiliki titik ujung sama disebut sisi ganda dan suatu sisi yang menghubungkan sebuah titik ke dirinya sendiri disebut loop. Cara yang paling mudah dalam menyajikan graf adalah dengan menggunakan gambar atau grafis, dengan bentuk inilah sifat-sifat graf dapat dikenali secara detail. Contoh 2.1 Berikut merupakan contoh representasi grafis dari sebuah graf
Gambar 2.1 : Sebuah graf
6 Universitas Sumatera Utara
7 Andaikan G adalah sebuah graf. Misalkan u dan v adalah titik di G. Sebuah jalan dengan panjang m yang menghubungkan titik u dan v di G merupakan sebuah barisan m sisi dalam bentuk {u = vv , u1 }, {v1 , v2 }, ..., {vm−1 , vm = v}, juga dapat dinotasikan dengan u = v0 ↔ v1 ↔ v2 ↔ · · · ↔ vm−1 ↔ vm = v. Untuk lebih sederhananya, sebuah jalan dengan panjang m yang menghubungkan titik t
u dan v dinotasikan dengan u ←→ v. Sebuah jalan dengan u 6= v dikatakan terbuka dan sebuah jalan dengan u = v dikatakan tertutup. Sebuah jalan memungkinkan terdapat sisi yang berulang. Sebuah jalan tanpa perulangan sisi disebut sebagai lintasan. Lebih lanjut dalam sebuah lintasan sangat memungkinkan juga terdapat penggunaan titik secara berulang. Sebuah lintasan tanpa pengulangan titik, kecuali mungkin titik-titik ujungnya, disebut sebagai sebuah lintasan sederhana. Panjang lintasan adalah jumlah sisi pada lintasan tersebut. Sebuah lintasan dikatakan terbuka apabila u 6= v dan dikatakan tertutup (cycle) apabila u = v. Sebuah lingkaran adalah suatu lintasan tertutup. Jarak dari u dan v, yaitu d(u, v) merupakan panjang dari lintasan terpendek yang menghubungkan u dan v. Teorema 2.1 Andaikan G adalah sebuah graf. Setiap jalan yang menghubungkan titik u dan titik v di G memuat lintasan yang menghubungkan titik u dan titik v. Bukti. Andaikan W : u = v0 ↔ v1 ↔ v2 ↔ · · · ↔ vm = v adalah sebuah jalan yang menghubungkan titik u dan titik v. Jika semua titik v1 , v2 , · · · vt−1 adalah berbeda, maka W adalah sebuah lintasan yang menghubungkan u dan v. Jika tidak, maka terdapat bilangan i dan j dengan i ≤ j sehingga vi = vj . Buang jalan vi ↔ vi+1 ↔ · · · ↔ vj−1 sehingga dihasilkan sebuah jalan W 0 yang menghubungkan u dengan v dan lebih pendek dari jalan W . Jika W 0 memuat titik tengah yang berulang, maka ulangi proses di atas sehingga pada akhirnya ditemukan sebuah jalan W 00 yang tidak memuat titik tengah berulang. jalan W 00 adalah sebuah lintasan yang menghubungkan titik u dengan titik v.
2.2 Matriks Ketetanggaan (Adjacency) Merepresentasikan graf secara grafis merupakan cara yang mudah untuk menjelaskan suatu graf, tetapi memiliki kelemahan ketika akan mempelajari graf melalui hitungan matematis atau ketika mengolah data graf menggunakan aplikasi komputer. Merepresentasikan graf dalam bentuk matriks akan memberikan
Universitas Sumatera Utara
8 kemudahan untuk menyelesaikan permasalahan yang melibatkan graf dengan bantuan komputer. Matriks ketetanggaan dari graf G, dinotasikan dengan A(G), adalah matriks (n × n) dengan unsur pada baris ke-i dan kolom ke-j bernilai 1 jika titik vi terhubung langsung dengan titik vj serta bernilai 0 jika titik vi tidak terhubung langsung dengan titik vj .
aij =
1, jika vi ke vj ∈ E(G) 0, jika vi ke vj ∈ / E(G)
Oleh definisi matriks ketetanggaan, diperoleh aij = aji untuk semua 1 ≤ i, j ≤ n. Akibatnya, matriks ketetanggaan A(G) dari G adalah matriks simetris. Contoh 2.2 Berikut adalah sebuah graf
Gambar 2.2 : Graf 4-wheel (W) Matriks ketetanggaan dari graf pada gambar 2.2 adalah
0 1 0 1 1
1 0 1 A(G) = 0 1 0 1 0 1 1 1 1
0 1 1 1 0 1 1 0
Universitas Sumatera Utara
9 2.3 Graf Terhubung Titik u dan v di G dikatakan terhubung jika terdapat sebuah jalan di G yang menghubungkan titik u dengan titik v. Sebuah titik dalam sebuah graf adalah terhubung dengan dirinya sendiri. Sehingga relasi 2 titik terhubung adalah refleksif. Jika u dan v adalah 2 titik yang terhubung maka terdapat jalan yang menghubungkan u dengan v, tetapi dengan bergerak mundur diperoleh sebuah jalan yang menghubungkan v dengan u. Sehingga v terhubung dengan u. Jadi relasi 2 titik terhubung adalah relasi simetrik. Selanjutnya jika u dan v adalah terhubung dan titik v dan w adalah terhubung, maka terdapat jalan yang menghubungkan u dengan v dan jalan yang menghubungkan v dengan u. Hal ini berakibat bahwa jalan yang menghubungkan u dengan v, kemudian dilanjutkan dengan jalan yang menghubungkan v dengan w adalah sebuah jalan yang menghubungkan u dengan w. Sehingga titik u terhubung dengan titik w. Jadi relasi 2 titik terhubung adalah transitif. Dapat disimpulkan bahwa relasi 2 titik terhubung adalah relasi ekivalensi. Kelas ekivalensi dari relasi 2 titik terhubung disebut sebagai komponen terhubung dari graf G. Sebuah graf G dikatakan terhubung jika G mempunyai tepat satu komponen terhubung, artinya sebuah graf dikatakan terhubung jika untuk setiap pasangan titik u dan v terdapat sebuah jalan yang menghubungkan titik u dengan titik v. Berikut diberikan sebuah cara untuk mendeteksi keterhubungan dari sebuah graf. Teorema 2.2 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 dan misalkan B = A + A2 + · · · + An−1 . Teorema 2.1 menjamin bahwa untuk setiap pasangan titik i dan j terdapat sebuah lintasan sederhana yang menghubungkan titik i dengan titik j. Karena G mempunyai n titik dan pada lintasan sederhana tidak terdapat titik berulang kecuali i = j, jika i 6= j terdapat lintasan sederhana 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 (k)
dengan 1 ≤ k ≤ n − 1 sehingga entri aij ≥ 0. Sehingga semua entri selain entri diagonal dari matriks B adalah positif. JIka i = j, maka terdapat sebuah
Universitas Sumatera Utara
10 (2)
lingkaran dengan panjang 2 yang memuat titik i, sehingga entri aii ≥ 0 untuk semua i = 1, 2, · · · , n. Jadi entri diagonal dari matriks B adalah positif. Dapat disimpulkan bahwa semua entri dari matriks B = A + A2 + · · · + An−1 adalah positif.
Selanjutnya, misalkan setiap entri dari matriks A + A2 + · · · + An−1 adalah positif. Akibatnya untuk setiap pasangan titik i dan j terdapat sebuah bilangan (k)
positif k dengan 1 ≤ k ≤ n − 1 sehingga aij ≥ 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. Contoh 2.3 Berikut contoh graf terhubung dan tidak terhubung
Gambar 2.3 : Contoh graf terhubung dan graf tidak terhubung
Gambar 2.3(a) menunjukkan graf terhubung karena terdapat jalan dari setiap pasangan titik di G dan gambar 2.3(b) menunjukkan graf yang tidak terhubung karena tidak terdapat jalan yang menghubungkan titik v5 dengan titik lainnya. Proposisi-proposisi berikut menjelaskan beberapa sifat-sifat jalan pada sebuah graf terhubung. Proposisi 2.3 Misalkan G merupakan sebuah graf terhubung dengan u, v ∈ G. m
m+2t
Maka, setiap jalan u ←→ v dapat diperpanjang menjadi jalan u ←→ v untuk suatu bilangan bulat positif t. Bukti. Ambil u dan v merupakan titik di G dan misalkan W : u = v0 ↔ v1 ↔ m
v2 ↔ · · · ↔ vm−1 ↔ vm = v merupakan jalan u ←→ v di G. Maka jalan W 0 yang dimulai dari u berjalan ke v sepanjang jalan W dan kemudian berpindah t kali m+2t
mengelilingi lingkaran v ↔ vt−1 ↔ v merupakan sebuah jalan u ←→ v.
Universitas Sumatera Utara
11 Proposisi 2.4 Misalkan G merupakan sebuah graf terhubung dengan u, v, w adalah titik yang berbeda di G dan m adalah sebuah bilangan positif. Terdapat m
m
2m
u ←→ w dan v ←→ w jika dan hanya jika terdapat u ←→ v di G. m
Bukti. Andaikan u dan v adalah dua titik berbeda di G sehingga terdapat u ←→ m
m
w dan v ←→ w untuk suatu titik w di G. Maka u ←→ w yang dilanjutkan m
2m
dengan jalan w ←→ v adalah sebuah u ←→ v. Sebaliknya, asumsikan bahwa W : u = v0 ↔ v1 ↔ v2 ↔ · · · ↔ v2m−1 ↔ v2m = v 2m
m
m
merupakan u ←→ v di G. Jika w = vm , maka terdapat u ←→ w dan v ←→ w di G.
2.4 Primitifitas suatu Graf Sebuah graf terhubung G dikatakan primitif, jika terdapat bilangan bulat positif k sedemikian hingga untuk setiap pasangan titik u dan v di G terdapat jalan k
u ←→ v. Teorema 2.5 Andaikan G adalah suatu graf, G dikatakan primitif jika dan hanya jika terhubung dan mengandung lingkaran dengan panjang ganjil. Bukti. Andaikan G adalah suatu graf dan G adalah primitif, maka terdapat bilangan bulat positif k sehingga untuk setiap pasangan titik u dan titik v di k
G terdapat u ←→ v. Akibatnya, G adalah terhubung. Untuk setiap pasangan titik u dan titik v di G terdapat jalan dengan panjang m untuk semua m ≥ k. Misalkan m adalah ganjil. Untuk setiap titik u dan titik v di G dapat dibentuk jalan dengan panjang ganjil.
Andaikan u ←→ u adalah jalan yang menghubungkan titik u ke dirinya sendiri. Misalkan puv adalah lintasan yang menghubungkan titik u ke titik v. Jalan u ←→ v dapat dibentuk dari titik u ke titik v melalui lintasan puv dan kembali ke titik u melalui lintasan puv yang sama. Misalkan l(wuu ) adalah panjang jalan dari titik u ke titik u. l(wuu ) adalah genap, agar wuu mempunyai panjang ganjil maka wuu harus melewati 1 lingkaran ganjil disebarang titik, misalkan titik x. Jalan wuu yang terdiri dari lintasan pux , lintasan pxx , dan lintasan pxu adalah suatu jalan wuu dengan panjang ganjil. Sehingga untuk setiap titik u dan v di G haruslah mempunyai lingkaran ganjil.
Universitas Sumatera Utara
12 Contoh 2.4 Berikut contoh graf primitif
Gambar 2.4 : Contoh graf primitif
Pada Gambar 2.4, graf tersebut merupakan graf primitif karena memuat lingkaran dengan panjang ganjil 3 yaitu v1 ↔ v5 ↔ v2 ↔ v1 .
2.5 Matriks Tak Negatif dan Eksponen dari Graf 2.5.1 Matriks Tak Negatif Matriks tak negatif A merupakan sebuah matriks yang setiap entri aij dari A adalah bilangan bulat tak negatif. Jika setiap entri aij dari matriks A adalah bilangan bulat positif, maka matriks tersebut disebut matriks positif. Contoh matriks tak negatif dan matriks positif dapat dilihat pada 2 buah matriks berikut.
1 2 0
4 2 6
A = 4 0 1 , matriks tak negatif; B = 8 4 4 , matriks positif. 8 7 1
1 1 0
Secara umum, sebuah matriks ketetanggaan A dikatakan primitif jika terdapat sebuah bilangan bulat positif k sedemikian sehingga Ak adalah sebuah matriks positif. Matrik ketetanggaan dari graf pada gambar 2.4 adalah sebagai berikut
0 1 0 1 1
1 0 1 A(G) = 0 1 0 1 0 1 1 1 1
0 1 1 1 0 0 0 0
Universitas Sumatera Utara
13 Matriks ketetanggaan dikatakan primitif jika semua entri akij dari matriks Ak bernilai positif. Perhatikan matriks berikut 0 1 1 a. Untuk k = 1; diperoleh A = 0 1 1
1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0
Bukan merupakan matriks positif karena terdapat 11 entri bernilai 0 yang bukan merupakan bilangan bulat 3 1 b. Untuk k = 2; diperoleh A2 = 3 0 1
positif. 1 3 0 1 3 1 2 2 1 3 0 1 2 0 2 2 2 1 2 3
Bukan merupakan matriks positif karena terdapat 4 entri bernilai 0 yang bukan merupakan bilangan bulat 2 7 c. Untuk k = 3; diperoleh A3 = 2 6 7
positif. 7 2 6 7 4 7 2 5 7 2 6 7 2 6 0 2 5 7 2 4
Bukan merupakan matriks positif karena terdapat 1 entri bernilai 0 yang bukan merupakan bilangan bulat positif. 20 11 20 4 11 11 19 11 14 18 d. Untuk k = 4; diperoleh A4 = 20 11 20 4 11 4 14 4 12 14 11 18 11 14 19 Karena seluruh entri aij ≥ 0, maka A4 merupakan matriks positif, sehingga A adalah matriks primitif.
Universitas Sumatera Utara
14 2.5.2 Eksponen dari Graf Eksponen dari sebuah graf G merupakan bilangan bulat positif terkecil k sehingga untuk setiap pasang titik u dan v di G terdapat jalan dari u ke v dengan panjang k dan dinotasikan dengan exp(G). Eksponen lokal u dan v, dinotasikan expG (u, v), m
merupakan bilangan bulat terkecil k sehingga u ←→ v untuk semua m ≥ k, sehingga exp(G) = maxu,v∈V (G) {expG (u, v)} Teorema 2.6 Andaikan G adalah sebuah graf dan A = (aij ) adalah sebuah matriks ketetanggaan dari G. Misalkan akij adalah elemen (i, j) dari matriks Ak , maka akij menyatakan banyaknya jalan berbeda dengan panjang k yang menghubungkan titik i dengan titik j di G. Bukti. Pembuktian dilakukan dengan induksi matematika. Untuk k = 1, entri a1ij = aij dari A menyatakan banyaknya jalan dengan panjang 1 yang menghubungkan titik i dengan titik j. Asumsikan bahwa entri akij dari Ak menyatakan banyaknya jalan dengan panjang k yang menghubungkan titik i dengan titik j. (k+1)
Selanjutnya akan diperlihatkan bahwa aij
adalah banyaknya jalan dari i ke j
dengan panjang k + 1 di G dengan k ≥ 1. Setiap jalan dari titik i ke j di G dengan panjang k + 1 yang terdiri dari jalan i ke l dengan panjang k untuk l = 1, 2, · · · , n, dan dilanjutkan dengan sisi dari titik l ke titik j, sehingga akil alj menyatakan jalan dengan panjang k + 1 dari titik i ke titik j di G untuk k = 1, 2, · · · , n. Jika tidak terdapat jalan yang (k)
(k)
panjangnya k dari titik i ke titik j di G, maka aij = 0 sehingga aij aij = 0. Hal ini berakibat tidak terdapat jalan yang panjangnya k + 1 dari titik i ke titik j yang melalui titik l di G sehingga diperoleh banyaknya jalan dengan panjang k + 1 dari titik i ke titik j di G adalah (k)
(k)
(k)
ai1 a1j + ai2 a2j + ... + ain anj =
n X
akil alj
i=1
karena Ak+1 = Ak A maka (k)
aij =
n X
akil alj
i=1
Universitas Sumatera Utara
15 (k+1)
Sehingga aij
adalah menyatakan banyaknya jalan dari titik i ke titik j yang
panjangnya k + 1 di G.
Contoh matriks untuk graf pada Gambar 2.4, nilai k = 6 yang diperoleh adalah jalan dengan panjang terkecil dari setiap pasang titik yang ada di G, maka eksponen dari graf pada Gambar 2.4 adalah exp(A)=exp (G(A))=4.
2.6 Scrambling Index 2.6.1 Scrambling Index Graf Primitif Sebuah graf dikatakan primitif jika dan hanya jika terhubung dan mengandung lingkaran dengan panjang ganjil. Menurut Alkelbek dan Kirkland (2009a), untuk titik u, v dan w dari graf G, jika {u, w}, {v, w} ∈ E(G), maka titik w dikatakan sebagai tetangga persekutuan luar bersama (common out-neighbour) dari titik u dan v. Scrambling index dari graf primitif G adalah bilangan bulat positif terkecil k sehingga untuk setiap pasang dua titik u dan v yang berbeda di G, k
k
terdapat sebuah titik w dengan sifat terdapat u ↔ w dan v ↔ w, yang dapat juga dikatakan sebagai bilangan bulat terkecil k sehingga setiap pasang titik dari G mempunyai tetangga persekutuan luar bersama di Gk . Scrambling index dari G akan dinotasikan sebagai k(G). Untuk setiap dua titik u dan v yang berbeda, scrambling index lokal dari u dan v adalah bilangan bulat positif ku,v (G) yang didefinisikan sebagai k
k
ku,v (G) = min{k : u ↔ w dan v ↔ w} w∈V
Dari definisi scrambling index k(G) dan scrambling index lokal ku,v (G) diperoleh hubungan k(G) ≥ ku,v (G). Karena G adalah graf terhubung, maka 0
untuk setiap bilangan bulat l ≥ ku,v (G) dapat ditemukan sebuah titik w sehingl
0
l
0
ga terdapat u ↔ w dan v ↔ w . Hal ini mengakibatkan nilai dari k(G) yang juga disebut dengan scrambling index global adalah maksimum dari nilai-nilai scrambling index lokal ku,v (G) yang didefinisikan sebagai berikut: k(G) = max{ku,v (G)} u6=v
Universitas Sumatera Utara
16 Berdasarkan definisi, scrambling index lokal dari graf pada Gambar 2.4 sebagai berikut, kv1 ,v2 (G) =min{2, 2, 2, 3, 1} = 1 kv1 ,v3 (G) =min{2, 1, 2, 1, 1} = 1 kv1 ,v4 (G) =min{3, 2, 3, 4, 2} = 2 kv1 ,v5 (G) =min{2, 1, 2, 3, 2} = 1 kv2 ,v3 (G) =min{2, 2, 2, 3, 1} = 1 kv2 ,v4 (G) =min{1, 2, 1, 2, 2} = 1 kv2 ,v5 (G) =min{1, 2, 1, 2, 2} = 1 kv3 ,v4 (G) =min{3, 2, 4, 3, 2} = 2 kv3 ,v5 (G) =min{2, 1, 2, 3, 2} = 1 kv4 ,v5 (G) =min{1, 2, 1, 2, 2} = 1 Dari definisi diperoleh max {ku,v (G)}
k(G) =
u,v∈V (G)
max {1, 1, 2, 1, 1, 1, 1, 2, 1, 1}
=
u,v∈V (G)
= 2 Sehingga scrambling index dari graf diatas k(G) = 2. Scrambling index dari suatu graf dapat diperoleh dari matriks ketetanggaannya. Scrambling index dari matriks primitif A adalah bilangan bulat positif terkecil k sedemikian sehingga untuk setiap dua baris dari Ak memiliki paling sedikit satu entri positif pada kolom yang sama, dan dinotasikan oleh k(A). Scrambling index dari matriks primitif A juga dapat didefinisikan sebagai bilangan bulat positif terkecil k sedemikian sehingga Ak (AT )k seluruh entrinya bernilai positif. Perhatikan contoh matriks dari graf primitif pada Gambar 2.4. 1. Untuk k = 1, diperoleh
0 1 0 1 1
1 0 1 1 A = 0 1 0 1 0 1 1 1 1
0 1 1 1 0 0 0 0
Universitas Sumatera Utara
17 A tidak memiliki scrambling index 1, karena pada baris ketiga dan keempat tidak memiliki entri positif di kolom yang sama. 2. Untuk k = 2, diperoleh
3 1 3 0 1
1 3 1 A2 = 3 1 3 0 2 0 1 2 1
2 2 0 1 2 2 2 3
karena setiap dua baris dari Ak dengan k = 2 memiliki paling sedikit satu entri positif pada kolom yang sama, maka k(A)=2. Chen dan Liu (2010) memperlihatkan hubungan antara scrambling index dan eksponen dari graf primitif, jika G adalah graf primitif dengan order n ≥ 2 dan u, v adalah pasangan titik dari G
expG (u, v) ku,v (G) ≤ 2 dan
exp(G) k(G) = 2
dimana dae adalah integer terkecil ≥ a. Graf pada Gambar 2.4 memiliki exp(G) = 4, maka nilai scrambling indexnya adalah
exp(G) k(G) = 2 4 = 2 = 2
2.6.2 Scrambling Index dari Lingkaran Ganjil Graf berbentuk cycle (s-graf cycle) dengan titik sebanyak s dengan s ≥ 3 disebut graf cycle dan ditulis Cs . Graf cycle yang banyak titiknya ganjil disebut cycle ganjil dan cycle yang banyak titiknya genap disebut cycle genap. Graf cycle
Universitas Sumatera Utara
18 sering disebut sebagai graf lingkaran karena gambarnya dapat dibentuk menjadi lingkaran. Gao dan Shao (2013) memberikan teori mengenai scrambling index pada lingkaran dengan panjang s adalah ganjil, Cs : v1 ↔ v2 ↔ · · · ↔ vs − 1 ↔ vs ↔ v1
Proposisi 2.7 Andaikan Cs adalah sebuah lingkaran dengan panjang ganjil s ≥ 3, maka k(Cs ) = (s − 1)/2.
Bukti. Jalan yang menghubungkan titik v1 dengan vs dengan panjang genap terpendek adalah v1 ↔ v2 ↔ · · · ↔ vs−1 ↔ vs dengan panjang s − 1. Oleh proposisi 2.4 terdapat titik w ∈ Cs sehingga ada (s−1)/2
(s−1)/2
jalan v1 ←→ w dan vs ←→ w. Sehingga kv1 ,vs (Cs ) = (s − 1)/2, Akibatnya k(Cs ) ≥ (s − 1)/2. Selanjutnya diperlihatkan bahwa k(Cs ) ≤ (s−1)/2. Pertama, diperlihatkan bahwa untuk setiap dua titik berbeda vi dan vj di Cs terdapat jalan yang menghubungkan vi dan vj dengan panjang genap m ≤ (s−1). Jika d(vi , vj ) adalah genap, maka terdapat jalan dari vi ke vj dengan panjang genap m = d(vi , vj ) ≤ s − 1. Jika d(vi , vj ) adalah ganjil, maka terdapat jalan yang menghubungkan u dan v dengan panjang genap m = s − d(vi , vj ) ≤ s − 1. Proposisi 2.3 menjamin bahwa (s−1)
untuk setiap dua titik vi dan vj yang berbeda terdapat vi ←→ vj . Oleh proposisi 2.4, untuk setiap dua titik u dan v yang berbeda terdapat titik w di Cs sehingga (s−1)/2
(s−1)/2
ada jalan vi ←→ w dan vj ←→ w. Sehingga k(Cs ) ≤ (s − 1)/2, Karena terpenuhi k(Cs ) ≥ (s − 1)/2 dan k(Cs ) ≤ (s − 1)/2, maka k(Cs ) = (s − 1)/2.
2.6.3 Graf dengan Scrambling Index 1 Walni (inpress) memberikan syarat perlu dan cukup untuk graf dengan scrambling index 1.
Proposisi 2.8 Andaikan G adalah sebuah graf primitif dengan n ≥ 3 titik dan tanpa loop. Scrambling index k(G) = 1 jika dan hanya jika memenuhi dua kondisi
Universitas Sumatera Utara
19 berikut. 1. Setiap titik dari graf G berada pada sebuah segitiga. 2. Untuk titik u dan v yang terletak pada dua segitiga berbeda, terdapat jalan dengan panjang 2 yang menghubungkan u dan v. Bukti. Andaikan k(G) = 1, dan misalkan u adalah sebarang titik di G. Karena G terhubung, maka terdapat sebuah titik v di G sehingga {u, v} adalah sebuah sisi di G. Karena k(G) = 1, terdapat sebuah titik w sehingga {u, w} dan {v, w} masing-masing adalah sebuah sisi dari graf G. Akibatnya, sisi {u, v}, {u, w} dan {v, w} membentuk sebuah segitiga yang memuat u. Jadi setiap titik di G terletak pada sebuah segitiga. Andaikan x dan y adalah dua titik di graf G yang terletak pada sebuah segitiga berbeda. Karena k(G) = 1, maka terdapat sebuah titik z di G sehingga {x, z} dan {y, z} masing-masing adalah sebuah sisi pada graf G. Akibatnya jalan x ↔ z ↔ y adalah sebuah jalan yang menghubungkan x dan y dengan panjang 2. Sekarang misalkan G adalah primitif dan memenuhi kondisi (1) dan kondisi (2) pada proposisi 2.8. Untuk setiap dua titik u dan v yang berbeda diperlihatkan bahwa ku,v (G) = 1. Jika u dan v terletak pada sebuah segitiga, maka terdapat 1
1
titik w pada segitiga sehingga ada jalan u ←→ w dan v ←→ w. Jadi ku,v (G) = 1. Jika u dan v berada pada dua segitiga yang berbeda, maka kondisi (2) menjamin bahwa terdapat jalan dengan panjang 2 yang menghubungkan u dan v. Hal ini 1
1
berakibat terdapat titik w di graf G sehingga ada u ↔ w dan v ↔ w. Jadi ku,v (G) = 1. Oleh definisi k(G) = max{ku,v (G)} = 1. u6=v
Universitas Sumatera Utara
