BAB 2 DIGRAPH
Pada bab ini akan dijelaskan teori-teori dasar tentang digraph yang meliputi definisi dua cycle, primitifitas dari digraph, eksponen, dan lokal eksponen. Dengan demikian, akan mempermudah peneliti dalam menjelaskan teori digraph dwiwarna pada bab berikutnya. 2.1. Dua Cycle Digraph atau graph berarah adalah sekumpulan titik-titik atau verteks yang dihubungkan oleh busur berarah atau arc. Berikut ini definisi yang diungkapkan oleh Suwilo (2001). Definisi 2.1. Sebuah graph berarah (directed graph) atau digraph D adalah himpunan hingga dan tak kosong V = {1, 2, . . . , n} yang unsur-unsurnya disebut dengan verteks, bersama dengan himpunan E yang merupakan pasangan-pasangan verteks di D yang unsur-unsurnya disebut dengan arc. Representasi dari sebuah digraph D dapat dilihat pada contoh berikut. Contoh 2.1. Representasi dari digraph dengan 5 buah verteks.
v1 •@
@ @
• v5
-
@ I @
@•
v2 •@
@
-
@ R @
@ @•
v4
v3
Gambar 2.1 Representasi digraph Dari Gambar 2.1 terdapat himpunan V yakni V = {v1, v2, v3, v4 , v5} dan terdapat himpunan busur E yakni E = {(1, 2), (1, 5), (2, 3), (4, 1), (4, 3), (5, 4)}. Andaikan digraph D terdiri atas n verteks vj = v1, v2, . . . , n, didefinisikan derajat masuk (In Degree) yaitu banyaknya busur berarah yang menuju vj dinotasikan sebagai id(vj ), dan derajat keluar (Out Degree) yaitu banyaknya busur 6
Universitas Sumatera Utara
7 berarah yang keluar dari vj dinotasikan sebagai od(vj ). Pada Contoh 2.1 terlihat yang memiliki derajat masuk yaitu v2, v3, v4, v5, id(v2) = 1 karena hanya terdapat satu busur berarah yang menuju v2, id(v3) = 2, id(v4) = 2, dan id(v5) = 1. Serta yang memiliki derajat keluar yaitu v1 , v2, v4, v5, od(v1 ) = 3 karena terdapat tiga busur berarah yang keluar (meninggalkan) v1 , od(v2 ) = 1, od(v4 ) = 1, dan od(v5 ) = 1. Pada digraph D terdapat path, cycle dan walk. Sebuah path atau lintasan sederhana dari verteks u ke verteks v adalah sebuah lintasan dimana tidak terjadi pengulangan satu atau lebih verteks dari u ke v. Sebuah lintasan dari verteks u ke verteks v disebut cycle apabila verteks awal dan ujungnya sama atau dapat ditulis u = v. sebuah lintasan dari verteks u ke verteks v disebut walk apabila terdapat pengulangan satu atau beberapa verteks dari u ke v. Suatu jalan w merupakan jalan yang menghubungkan dua buah verteks u dan v di digraph D. Panjang jalan w dinotasikan dengan `(w) yaitu banyaknya arc atau busur berarah yang dilalui bila bergerak dari verteks u ke verteks v. Dalam hal ini jalan dapat berupa path, cycle ataupun walk. Pada Contoh 2.1 dapat ditemukan beberapa path, cycle, dan walk yaitu: 1. Terdapat dua buah path dari verteks 1 ke verteks 3, yaitu v1 → v2 → v3 dengan panjang `(v1, v3 ) = 2 dan v1 → v5 → v4 → v3 dengan panjang `(v1 , v3) = 3. 2. Terdapat sebuah path dari verteks 1 ke verteks 2, yaitu v1 → v2 dengan panjang `(v1 , v2) = 1. 3. Terdapat sebuah path dari verteks 1 ke verteks 4, yaitu v1 → v5 → v4 dengan panjang `(v1 , v4) = 2. 4. Terdapat cycle dari verteks 1 ke verteks 1, v1 → v5 → v4 → v1 dengan panjang `(v1 , v1) = 3. 5. Terdapat walk dari verteks 1 ke verteks 3, v1 → v5 → v4 → v1 → v2 → v3 dengan panjang 5. Dua cycle didefinisikan sebagai sebuah digraph D yang terdiri tepat dua cycle. Dua cycle yang dimaksud dapat bersinggungan maupun berpotongan. Dua Universitas Sumatera Utara
8 cycle yang bersinggungan dapat bersinggungan pada sebuah busur berarah atau pada salah satu verteks di D. Representasi dua cycle dapat dilihat pada Contoh 2.2. Contoh 2.2. Representasi dari dua cycle
v1
v4
v1
v4
v1
v4
v6
v2
v3
v2
v3
v5 v2
v3
v5
(a)
(b)
(c)
Gambar 2.2 (a) Dua cycle berpotongan, (b) dua cycle bersinggungan pada sebuah busur berarah, dan (c) dua cycle bersinggungan pada satu verteks Pada Gambar 2.2 (a) melukiskan dua cycle yaitu dari v1 → v2 → v3 → v1 dengan panjang 3 dan dari v1 → v2 → v3 → v4 → v1 dengan panjang 4. Gambar 2.2 (b) melukiskan dua cycle yaitu dari v3 → v4 → v5 → v3 dengan panjang 3 dan dari v1 → v2 → v3 → v4 → v1 dengan panjang 4. Gambar 2.2 (c) melukiskan dua cycle yaitu dari v3 → v5 → v6 → v3 dengan panjang 3 dan dari v1 → v2 → v3 → v4 → v1 dengan panjang 4. 2.2. Primitifitas Sebuah digraph dikatakan terhubung kuat (strongly connected) bila untuk setiap pasangan verteks (u, v) di D terdapat jalan dari verteks u ke v dan dari v ke u. Sebaliknya, sebuah digraph dikatakan tidak terhubung kuat bila untuk beberapa pasangan verteks (u, v) di D tidak terdapat jalan dari u ke v atau dari v ke u. Untuk lebih memahami digraph terhubung kuat dan tidak terhubung kuat dapat dilihat pada Gambar 2.3. Gambar 2.3 (a) memperlihatkan sebuah digraph yang terhubung kuat karena untuk setiap verteks u dan v di D, terdapat jalan dari u ke v dan dari v ke u. Misalnya jalan dari verteks 2 ke verteks 1 yaitu 2 → 3 → 1, lalu jalan dari verteks 1 ke verteks 2 yaitu 1 → 3 → 2, begitu pula untuk pasangan verteks yang lain. Gambar 2.3 (b) memperlihatkan sebuah digraph yang tidak terhubung kuat. Pada digraph ini, cukup dengan melihat Universitas Sumatera Utara
9 adanya jalan dari verteks 1 ke verteks 3 yaitu 1 → 3, namun tidak terdapat jalan dari verteks 3 ke verteks 1, sehingga merupakan digraph yang tidak terhubung kuat. Proposisi berikut memperlihatkan hubungan antara terhubung kuat dengan verteks-verteks pada cycle.
v1
v1 R
6
?
v2
v3 (a)
v2
v3 (b)
Gambar 2.3 (a) Digraph terhubung kuat, dan (b) digraph tak terhubung kuat Proposisi 2.2. Andaikan D adalah suatu digraph terhubung kuat maka setiap verteks terletak pada cycle. Bukti. Andaikan digraph D terdiri atas n verteks {v1, v2, . . . , vn}. Ambil sebarang verteks u dan v di D, karena D terhubung kuat, maka terdapat sebuah lintasan sederhana (path) dari verteks u ke verteks v dan dari verteks v ke verteks u. Sehingga gabungan dua buah path tersebut u → · · · → v → · · · → u membentuk sebuah cycle di D. Akibatnya, verteks u dan v terletak pada cycle. Suatu digraph D yang terhubung kuat dikatakan primitif apabila untuk dua buah verteks u dan v di D terdapat jalan dari u ke v dan dari v ke u dengan panjang k. Nilai k digunakan untuk perhitungan eksponen dari digraph D. Bilangan bulat positif terkecil k disebut eksponen dari digraph D dan ditulis dengan exp(D). Andaikan D adalah digraph yang terhubung kuat. Misalkan terdapat sebuah verteks tertentu x di D. Untuk dua buah verteks u dan v di D terdapat jalan wxu yaitu jalan dari verteks x ke verteks u dan jalan wxv yaitu jalan dari verteks x ke verteks v. Jika `(wxu ) = `(wxv ), maka verteks u dan v dikatakan ekivalen dan ditulis dengan u ∼ v. Pemilihan verteks tertentu adalah bebas. Untuk setiap verteks y di D, wyu adalah jalan dari verteks y ke verteks u, wyu dapat Universitas Sumatera Utara
10 diilustrasikan sebagai: w
w
xu y→x → u
dan jalan wyv yaitu jalan dari verteks y ke verteks v, wyv dapat diilustrasikan sebagai: w
w
xv y→x → v.
Karena u dan v ekivalen, ini berakibat jalan dari y ke u dan dari y ke v memiliki panjang yang sama dimana w merupakan jalan dari y ke x. Andaikan C = {C1 , C2, . . . , Cr } adalah himpunan semua cycle-cycle di D. Misalkan `(C) adalah matriks baris dengan kolom ke-i dimana i = 1, 2, . . . ,r, dan entri-entri dari `(C) adalah panjang cycle Ci (`(Ci )), yakni `(C) = {`(C1 ), `(C2 ), . . . , `(Cr )} dan misalkan m = gcd(`(C1 ), `(C2 ), . . . , `(Cr )). Definisikan H sebagai sebuah subgrup dari grup bilangan bulat Z, dimana H dibangun oleh himpunan `(C). Yakni H = h`(C1 ), `(C2 ), . . . , `(Cr )i. Karena Z adalah sebuah grup siklik, demikian juga halnya dengan H. Akibatnya H dibangun oleh sebuah bilangan bulat, dalam hal ini H = gcd(`(C1 ), `(C2 ), . . . , `(Cr )). Andaikan D adalah digraph imprimitif dengan indeks imprimitifitas k, maka k = gcd(`(C1 ), `(C2 ), . . . , `(Cr )). Suatu digraph adalah primitif jika k = 1 dan imprimitif jika k > 1. Teorema berikut menjelaskan tentang imprimitifitas dari digraph D. Teorema 2.3. Andaikan D adalah sebuah digraph terhubung kuat. D adalah primitif jika dan hanya jika pembagi persekutuan terbesar dari panjang cycle-cycle di D adalah 1. Bukti. Andaikan digraph D adalah primitif. Maka untuk setiap pasangan verteks u dan v di D, u ∼ v, Karena `(wuv ) ∈ H untuk setiap pasangan verteks u dan v di D dan setiap jalan (wuv ) dari u ke v maka u ∼ v. Di ambil jalan dengan panjang 1, maka 1 ∈ H, karena H = hgcd(`(c1 ), `(c2 ), . . . , `(ct )i maka pembagi persekutuan terbesar dari panjang cycle-cycle di D adalah 1. Sebaliknya, andaikan pembagi persekutuan terbesar dari panjang cycle-cycle di D adalah 1, maka H = Z sehingga untuk setiap pasangan verteks u dan v di Universitas Sumatera Utara
11 D dan setiap jalan wuv dari u ke v di D diperoleh `(wuv ) ∈ H. Sehingga masingmasing pasangan verteks di D adalah ekivalen. Akibatnya digraph D adalah primitif. Contoh 2.3. Pada Gambar 2.3 (a), sebuah dua cycle dengan panjang 3 dari v1 → v2 → v3 → v1 dan dengan panjang 4 dari v1 → v2 → v3 → v4 → v1. Gcd(3, 4) = 1, sehingga dua cycle tersebut adalah primitif.
2.3. Matriks Ketetanggaan Andaikan D(2) adalah sebuah digraph atas n verteks {v1, v2, . . . , vn }. Sebuah matriks ketetanggaan A = (aij ) dari D adalah sebuah sebuah matriks bujursangkar berordo n yang didefinisikan sebagai berikut. ( 1, jika terdapat busur berarah dari verteks i ke verteks j, aij = 0, jika sebaliknya dimana i, j = 1, 2, . . . , n. Berikut ini diberikan contoh matriks ketetanggaan dari sebuah digraph. Contoh 2.4. Dari Gambar 2.3 (a) dan (b), matriks ketetanggaannya adalah 0 1 1 0 1 1 A = 1 0 1 B = 1 0 1 . 1 0 0
0 0 0
Sebuah matriks ketetanggaan A dari sebuah digraph D dikatakan primitif, jika terdapat bilangan bulat positif k sehingga seluruh entri dari Ak adalah positif. Hal ini sesuai dengan pendapat Wielandt (Schneider, 2002), yaitu sebuah matriks tak negatif A dikatakan primitif jika Ak > 0. Pada Contoh 2.3, matriks ketetanggaan A adalah matriks ketetanggaan dari digraph primitif, hal ini dapat dilihat bahwa
0 1 1 A1 = A = 1 0 1 . 1 0 0
Dengan mengambil bilangan bulat positif k yang lebih dari 1 diperoleh 4 4 5 4 1 3 1 2 2 2 0 1 A2 = 1 1 1 , A3 = 2 1 2 , A4 = 3 2 3 , A5 = 5 3 5 . 0 1 1
2 0 1
1 2 2
4 1 3
Universitas Sumatera Utara
12 Untuk nilai k > 5, Ak > 0. Sehingga disimpulkan seluruh entri pada Ak dengan k ≥ 4 adalah positif. Matriks B adalah matriks dari digraph yang tak terhubung kuat sehingga tidak primitif. Andaikan B adalah primitif maka untuk bilangan bulat positif k, B k > 0. Bila primitif, maka untuk nilai k yang besar, seluruh entri B k adalah positif. Diambil k = 30 sehingga diperoleh 1 0 1 B 30 = 0 1 1 . 0 0 0
Untuk bilangan bulat positif k > 30, entri dari B k hanya berada pada interval [0, 1]. Karena masih terdapat entri yang bernilai 0, mengakibatkan digraph D dengan matriks ketetanggaan B tidak primitif. 2.4. Eksponen Eksponen dari digraph D didefinisikan sebagai bilangan bulat positif terkecil k sehingga untuk setiap pasangan verteks u dan v di D terdapat jalan dari u ke v dan dari v ke u dengan panjang k. Eksponen dari digraph tersebut dinotasikan dengan exp(D). Dalam hal ini, eksponen hanya ada bila digraph D adalah primitif. Contoh 2.5. Dari Gambar 2.3 (a), akan diperlihatkan bahwa nilai eksponennya adalah 4 yaitu dengan memperlihatkan semua kemungkinan jalan dengan panjang 1, jalan dengan panjang 2, jalan dengan panjang 3, dan jalan dengan panjang 4. 1. Jalan dengan panjang 1,yaitu v1 → v2 ,
v1 → v3 ,
v2 → v1 ,
v2 → v3 ,
v3 → v1
Karena tidak terdapat jalan yang panjangnya 1 dari v1 ke v1 , v2 ke v2 , v3 ke v2, dan v3 ke v3 maka 1 bukanlah eksponennya. 2. Jalan dengan panjang 2, yaitu v1 → v2 → v3
v2 → v1 → v2
v1 → v2 → v1
v2 → v1 → v3
v2 → v3 → v1
v3 → v1 → v2
v3 → v1 → v3
Karena tidak terdapat jalan yang panjangnya 2 dari v1 ke v2 , dan v3 ke v1 maka 2 bukanlah eksponennya. Universitas Sumatera Utara
13 3. Jalan dengan panjang 3, yaitu v1 → v2 → v3 → v1
v2 → v3 → v1 → v2
v3 → v1 → v2 → v1
v1 → v3 → v1 → v2
v2 → v3 → v1 → v3
v3 → v1 → v2 → v3
v1 → v2 → v1 → v3
v2 → v1 → v2 → v1
Karena tidak terdapat jalan yang panjangnya 3 dari v3 ke v2 maka 3 bukanlah eksponennya. 4. Jalan dengan panjang 4, yaitu v1 → v2 → v1 → v2 → v1
v2 → v1 → v2 → v1 → v3
v1 → v2 → v3 → v1 → v2
v3 → v1 → v2 → v3 → v1
v1 → v2 → v3 → v1 → v3
v3 → v1 → v2 → v1 → v2
v2 → v3 → v1 → v2 → v1
v3 → v1 → v2 → v1 → v3
v2 → v1 → v3 → v1 → v2 Karena terdapat jalan yang panjangnya 4 dari setiap pasangan verteks (u, v) maka eksponen dari digraph tersebut adalah 4. Eksponen suatu digraph D dapat dicari dengan menggunakan perpangkatan dari matriks ketetanggaan A. Brualdi dan Ryser (1991), menyatakan bahwa entri (i, j) dari Ak merupakan banyaknya jalan dari verteks vi ke vj dengan panjang k. Berikut ini diperlihatkan hubungan antara suatu digraph dengan matriks ketetanggaannya. Proposisi 2.4. Andaikan A adalah suatu matriks ketetanggaan dari digraph D. Entri (i, j) dari Ak menyatakan banyaknya jalan dari vi ke vj yang panjangnya k di D. Bukti. Akan dibuktikan dengan induksi pada k. Jika k = 1 maka setiap entri a1ij dari A1 menyatakan banyaknya jalan dari vi ke vj yang panjangnya satu. Asumsikan setiap entri akij dari Ak menyatakan banyaknya jalan dari vi ke vj yang panjangnya adalah k di D, untuk k ≥ 1. Akan diperlihatkan ak+1 adalah banyaknya jalan dari vi ke vj yang panij jangnya k + 1, untuk k ≥ 1. Perhatikan setiap jalan dari vi ke vj di D dengan panjang k + 1 dapat didekomposisikan sebagai jalan dari verteks vi ke v` dengan Universitas Sumatera Utara
14 panjang k untuk ` = 1, 2, . . . , n dan dilanjutkan dengan busur berarah dari v` ke vj , sehingga aki` a`j menyatakan jalan dengan panjang k + 1 dari vi ke vj di D. Andaikan tidak terdapat jalan yang panjang k dari vi ke v` di D, maka aki` = 0 sedemikian sehingga aki` a`j = 0. Ini berarti tidak terdapat jalan dengan panjang k + 1 dari vi ke vj yang melalui v` di D sehingga banyaknya jalan dengan panjang k + 1 dari vi ke vj di D adalah: aki1a1j
+
aki2a2j
+ ··· +
akin anj
=
n X
aki` a`j .
`=1
Karena Ak+1 = Ak A diperolehlah ak+1 ij
=
n X
aki` a`j .
`=1
Hal ini berakibat ak+1 adalah benar menyatakan banyaknya jalan dari vi ke vj ij dengan panjang k+1 di D. Jadi, setiap entri (i, j) dari Ak menyatakan banyaknya jalan dengan panjang k dari vi ke vj . Dengan menggunakan Proposisi 2.4 akan dicari eksponen dari Contoh 2.3 (a). Dari subbab 2.3 sebelumnya bahwa telah diketahui matriks ketetanggaan 0 1 1 4 1 3 4 4 5 A = 1 0 1. Nilai dari A4 = 3 2 3 dan A5 = 5 3 5. Karena setiap 1 0 0 1 2 2 4 1 3 entri dari Ak > 0 dipenuhi oleh k ≥ 4 dan dari definisi eksponen adalah bilangan positif terkecil k sehingga eksponen dari digraph tersebut adalah 4. 2.5. Eksponen Lokal Digraph Andaikan D adalah sebuah digraph primitif atas n verteks V = {v1, v2, . . . , vn }. Untuk vi ∈ V di D, eksponen lokal dari verteks vi di D adalah bilangan bulat positif terkecil ` sehingga untuk setiap verteks vj dimana j = 1, 2, . . . , n terdapat jalan dari verteks vi ke verteks vj di D dengan panjang `. Eksponen verteks vi disebut juga sebagai eksponen lokal keluar dari verteks vi dan dinotasikan dengan expout(vi, D). Andaikan D adalah digraph primitif yang terdiri dari n verteks. Jika verteksverteks di D adalah (v1, v2, . . . , vn ) sedemikian hingga expout(v1, D) ≤ expout(v2, D) ≤ · · · ≤ expout(vn , D). Universitas Sumatera Utara
15 Contoh 2.6. Dari Gambar 2.3 (a), akan dicari eksponen lokal dari setiap verteks di D berdasarkan Proposisi 2.4 yaitu dengan melihat entri akij dari Ak , dimana semua entri pada baris ke-i harus bernilai positif. Matriks ketetanggaan dari Gambar 2.3 (a) adalah 0 1 1 A = 1 0 1 . 1 0 0
2 0 1 Nilai dari A2 = 1 1 1, pada A2 terlihat baris ke-2 memiliki entri yang positif, 0 1 1
1 2 2 sehingga expout(v2, D) = 2. Untuk A3 = 2 1 2, pada A3 terlihat baris ke-1
2 0 1 dan ke-2 memiliki entri-entri yang positif, maka expout(v1, D) = 3. Selanjutnya 4 1 3 A4 = 3 2 3, pada A4 terlihat setiap baris memiliki entri-entri yang positif, 1 2 2 sehingga expout(v3, D) = 4.
Dari Contoh 2.6 expout(v1 , D) = 3, expout(v2, D) = 2, dan expout(v3, D) = 4. Bila hasil ini dibandingkan dengan nilai eksponen pada subbab 2.4 yaitu exp(D) = 4, maka untuk setiap i = 1, 2, . . . , n nilai expout(vi, D) ≤ exp(D).
Universitas Sumatera Utara
