Bab 3 HASIL UTAMA Pada Bab ini, disajikan hasil utama dari pengerjaan tugas akhir ini, yakni algoritma untuk mengkonstruksi pewarnaan sisi-f pada graf roda, graf kipas dan graf dengan degeneracy, arboricity dan bilangan unisiklis tertentu serta algoritma heuristik yang dapat digunakan untuk mengkonstruksi pewarnaan sisi-f pada kelas graf lainnya.
3.1
Penyusunan Algoritma
Secara umum, cara kerja algoritma yang diajukan tampak pada Gambar 3.1. Setelah algoritma diberikan masukan graf G , kemudian dibentuk matriks ketetanggaan dan keterkaitan. Kemudian, G akan direduksi dengan algoritma reduksi. Setelah itu, algoritma akan masuk ke proses penentuan pilihan penyelesaian masalah. Pertama, menyelesaian masalah pewarnaan sisi-f untuk graf G menggunakan algoritma EDGE-COLOR yang telah dibahas pada Bab 2. Kedua adalah penyelesaian masalah pewarnaan sisi-f untuk graf G menggunakan algoritma warna-sisi-rodakipas. Dan ketiga adalah adalah penyelesaian masalah pewarnaan sisi-f untuk graf G menggunakan algoritma heuristik. Alur algoritma tampak pada Gambar 3.1.
27
28
BAB 3. HASIL UTAMA
Gambar 3.1: Algoritma umum
3.1.1
Algoritma Reduksi
Berikut ini akan ditampilkan algoritma dari reduksi masalah pewarnaan sisi-f menjadi pewarnaan biasa. Algoritma berikut ini disusun berdasarkan penjelasan pada Subbab 2.1. Misalkan graf yang direduksi adalah graf G = (V, E). Algoritma tersebut sebagai berikut: reduksi(G); (mulai); 1. bentuk graf Gf tanpa sisi dengan n(Gf ) = f (v); (V (Gf ) = {u11 , u12 , ..., u1f (v1 ) , u21 , u22 , ..., u2f (v2 ) , ..., un1 , un2 , ..., unf (v1 ) }) i) ⌉ 2. a[i] = ⌈ d(v f (vi
BAB 3. HASIL UTAMA
29
3. untuk i:=1 sampai n(G) lakukan (a) untuk j:=i+1 sampai n(G) lakukan i. mulai ii. k=1; iii. jika matriksketetanggaanG[i, j] <> 0 maka matriksketetangganGf [uik , ujk ]=1; jika k <= f (v) maka k = k + 1, lainnya k = 1; selesai (selesai);
3.1.2
Algoritma warna-sisi-roda-kipas
Pada bagian ini akan disusun algoritma O(n) untuk pewarnaan sisi suatu graf roda Wn dengan n > 2. Berdasarkan Teorema 2.7, graf roda Wn dapat diwarnai dengan ∆(Wn ) warna. Algoritma pewarnaan graf roda dan graf kipas yang akan dikonstruksi adalah sesuai dengan bukti yang dikemukakan pada Teorema 2.6 dan 2.7. warna-sisi-roda-kipas; diasumsikan bahwa masukan adalah graf roda atau kipas G dengan n > 3 (mulai);
1. warnai sisi-sisi pada titik dasar dengan ∆(G) warna. 2. warnai sisi sisa dengan ∆(G) warna dimulai dari warna 3 sampai ∆(G) warna, kemudian dua sisi terakhir diwarnai dengan warna 1 dan 2 (selesai);
BAB 3. HASIL UTAMA
3.1.3
30
Algoritma EDGE-COLOR [7]
Pada bagian ini, akan disusun algoritma yang efisien dengan kompleksitas O(n log n) untuk pewarnaan sisi suatu graf G untuk kasus a′ (G) dibatasi dan ∆(G) yang besar: ∆(G) ≥ 4a′ (G). Sebelumnya telah dibahas bahwa a′ (G) ≤ s(G). Pertama-tama graf G didekomposisi menjadi beberapa subgraf Gi yang sisi-sisinya saling bebas dengan derajat maksimum yang kecil, kemudian mewarnai subgraf-subgraf tersebut. Teorema 3.1 [] Jika bilangan unisiklis a′ (G) terbatas dan ∆(G) ≥ 4a′ (G), maka graf G dapat diwarnai dengan ∆(G) warna dalam O(n log n). Dengan Lemma 2.2 dan persamaan (2.2.4), dan (2.2.5) didapat akibat berikut ini. Akibat 3.1 Graf G dapat diwarnai dengan ∆(G) warna dalam O(n log n) jika salah satu di bawah ini berlaku: 1. a(G) terbatas dan ∆(G) ≥ 4a(G); 2. s(G) terbatas dan ∆(G) ≥ 4s(G); Selanjutnya, akan dibuktikan Teorema 3.1 menggunakan algoritma Chrobak dan Nishizeki[4]. Lemma 3.1 [7] Jika G adalah graf terhubung, ∆(G) terbatas dan ∆(G) ≥ 4a′ (G), maka G memiliki Θ(n) sisi yang dapat dieliminasi. Bukti: Misalkan U = {u ∈ V |d(v, G) ≤ 2a′ (G)}, maka U 6= ∅ karena dengan Lemma 2.1(2) δ(G) ≤ 2a′ (G). Lebih jauh, V − U = ∅ karena ∆(G) ≥ 4a′ (G) > 2a′ (G). Maka dari itu, graf H didapat dari G dengan menghapus semua titik di U yang tak kosong. Misalkan W = {w ∈ V H|d(w, H) ≤ 2a′ (G)}, dan misalkan E ′ himpunan sisi (u, v) ∈ EG sehingga u ∈ U dan v ∈ U ∪ W . Maka cukup untuk membuktikan (1) dan (2) dibawah ini: 1. setiap sisi (u, v) ∈ E ′ dapat dieliminasi; dan 2. banyaknya sisi di E ′ adalah Θ(n),
31
BAB 3. HASIL UTAMA
Misalkan (u, v) merupakan sebarang sisi di E ′ . Karena u ∈ U , d(u) ≤ 2a′ (G) < ∆. Di sisi lain, d∗ u (v) ≤ 2a′ (G): jika v ∈ U maka d∗ u (V ) ≤ d(v, G) ≤ 2a′ (G); dan jika v ∈ W maka d∗ u (v) ≤ d(v, H) ≤ 2s′ (G) karena tidak ada tetangga dari v di U berderajat ∆. Maka dari itu, d(u) + d∗ u (v) ≤ 4a′ (G) ≤ ∆ dan karenanya sisi (u, v) terhapuskan. Sehingga (1) terbukti. Karena paling sedikit satu sisi di E ′ berkaitan dengan setiap titik di W maka |E ′ | ≥ |W |.
(3.1.1)
Dengan menggunakan Lemma 2.1(3) pada graf H maka |W | ≥
n(H) . +1
(3.1.2)
2a′ (H)
Karena a′ (H) ≤ a′ (G) dan n(H) = n − |U |, akan didapat |W | ≥ Jika |U | kecil, misalkan |U | ≤
2∆−1 n 2∆+1
n − |U | . 2a′ (G) + 1
(3.1.3)
maka dengan persamaan (3.1.1) dan (3.1.3),
maka |E ′ | ≥
1
(n − |U |) +1 2 n, ≥ ′ (2a (G) + 1)(2∆ + 1) 2a′ (G)
(3.1.4) (3.1.5)
dan akibatnya |E ′ | = Θ(n) karena ∆(G) dan a′ (G) terbatas. Sehingga cukup untuk memastikan |E ′ | = Θ(n) untuk kasus ketika |U | > n − |U | <
2∆−1 n 2∆+1
yaitu
2 n. 2∆ + 1
(3.1.6)
Sisi di EG − E ′ terhubung dengan dua titik di W atau terkait dengan titik di V − U − W . Banyaknya sisi sebelumnya paling banyak a′ (G)|W |, dan banyaknya sisi setelahnya adalah paling banyak ∆(n − |U | − |W |). Maka dari itu, didapat |E ′ | ≥ |E| − a′ (G)|W | − ∆(n − |U | − |W |)
(3.1.7)
= |E| − ∆(n − |U |) + (∆ − a′ (G))|W |.
(3.1.8)
BAB 3. HASIL UTAMA
32
Karena G terhubung, m ≥ n − 1. Maka dari itu, dengan persamaan (3.1.3), (3.1.6) dan (3.1.7) didapat ∆ − a′ (G) (n − |U |) 2a′ (G) + 1 a′ (G)(2∆ + 1) = n−1− (n − |U |) 2a′ (G) + 1 a′ (G)(2∆ + 1) > n−1− n 2a′ (G) + 1 1 n−1 = ′ 2a (G) + 1
|E ′ | ≥ n − 1 − ∆(n − |U |) +
(3.1.9) (3.1.10) (3.1.11) (3.1.12)
Sehingga |E ′ | = Θ(n) karena a′ (G) terbatas. Sehingga (2) terbukti Chrobak dan Nishizeki dengan tepat mewarnai-sisi dari graf G dengan ∆(G) warna jika ∆(G) terbatas dan G memiliki Θ(n) sisi yang dapat dieliminasi. Sehingga didapat punya lemma berikut ini. Lemma 3.2 Jika ∆(G) terbatas dan ∆(G) ≥ 4a′ (G), maka sisi G dapat diwarnai dengan ∆(G) warna dalam O(n log n). Lemma 3.2 cukup menyatakan bahwa terdapat algoritma untuk mewarnai sisi G dengan ∆(G) warna hanya untuk kasus dimana ∆(G) tidak terbatas, misalkan ∆(G) ≥ 8s(G)(> 4a′ (G)). Idenya adalah dengan melakukan dekomposisi pada graf G dengan derajat yang besar menjadi beberapa subgraf yang sisinya saling bebas G1 , G2 , ..., Gj yang memiliki derajat maksimum yang kecil ∆(Gi ) untuk setiap i dan mewarnai sisi dari G dengan ∆(G) warna dapat didapat dengan penyatuan pewarnaan sisi dari Gi dengan ∆(Gi ) warna. Perhatikan bahwa pewarnaan sisi dari Gi dapat ditemukan dengan waktu yang terbatas seperti tersebut dalam Lemma 3.2 karena ∆(Gi ) terbatas. Misalkan c bilangan bulat positif terbatas dan misalkan E1 , E2 , ..., Ej partisi dari E.
Gi = G[Ei ] adalah notasi dari subgraf G yang dengan himpunan sisi Ei .
E1 , E2 , ..., E3 dikatakan (∆(G), c) partisi dari E jika Gi = G[Ei ], 1 ≤ i ≤ j, memenuhi
33
BAB 3. HASIL UTAMA 1. ∆(G) = Σji=1 ∆(Gi ); dan 2. ∆(Gi ) = c untuk setiap i, 1 ≤ i ≤ j − 1, dan c ≤ ∆(Gj ) < 2c.
Jelas s(Gi ) ≤ s(G) untuk setiap i, 1 ≤ i ≤ j. Teorema 2.5 menyatakan bahwa χ′ (G) = ∆(G) jika ∆(G) ≥ 8s(G) > 2s(G). Pilih c = 43(G), maka ∆(Gi ) ≥ c = 4s(G) > 2s(Gi ) akibatnya χ′ (Gi ) = ∆(Gi ) untuk seitap i, 1 ≤ i ≤ j. Karena ∆(Gi ) < 2c = 8s(G) ≤ 16a′ (G) = O(1) dengan Lemma 2.2, ∆(Gi ) terbatas untuk 1 ≤ i ≤ j. Lebih jauh, dengan persamaan (2.2.4) dan (2.2.5) didapat ∆(Gi ) ≥ 4s(Gi ) ≥ 4a′ (Gi ). Maka dari itu, dengan Lemma 2.5 akan didapat sebuah pewarnaan sisi dari Gi dengan ∆(Gi ) warna dalam waktu yang telah diklaim. Karena ∆(G) = Σji=1 ∆(Gi ),
(3.1.13)
pewarnaan sisi dari Gi dengan ∆(Gi ) warna, 1 ≤ i ≤ j, dapat diperumum pada sebuah pewarnaan sisi dari G dengan ∆(G) warna. Lemma 3.3 Jika ∆(G) ≥ 2c ≥ 8s(G), maka sebuah (∆(G), c)-partisi dari E dapat dibentuk dalam waktu linier. Sehingga didapat algoritma di bawah ini untuk mewarnai sisi dari graf G dimana a′ (G) terbatas dan ∆(G) ≥ 4a′ (G). EDGE-COLOR(G); diasumsikan bahwa a′ (G) terbatas dan ∆(G) ≥ 4a′ (G) (mulai); Jika ∆(G) < 8s(G) maka ∆(G) terbatas 1. warnai sisi G dengan ∆(G) warna dengan Lemma 2.6; lainnya ∆(G) ≥ 8s(G) mulai 2. cari sebuah (∆, c)-partisi E1 , E2 , ..., Ej dari E
34
BAB 3. HASIL UTAMA 3. for i:=1 to j do warnai sisi dari Gi dengan ∆(Gi ) dimana Gi = G[Ei ];
4. perumum pewarnaan sisi optimal dari G1 , G2 , ..., Gj menjadi sebuah pewarnaan sisi optimal dari G dengan ∆(G) warna selesai (selesai) Bukti Teorema 3.1: Dengan Lemma 3.2 dan 3.3, jelas algoritma di atas menemukan pewarnaan sisi dari graf G dengan ∆(G) warna. Maka dari itu algoritma tersebut cukup untuk membuktikan kompleksitasnya. Dengan Lemma 2.6, baris dua dapat diselesaikan dengan waktu linier. Dengan Lemma 2.5 baris satu dapat diselesaikan dalam waktu O(n log n) karena ∆(G) < 8s(G) ≤ 16a′ (G) = O(1). Pada baris tiga, untuk setiap i, 1 ≤ 1 ≤ j dengan Lemma 2.5 kita dapat menemukan sebuah pewarnaan sisi dari Gi dengan ∆(Gi ) warna dalam O(n(Gi ) log n(Gi )). Karena Gi = G[Ei ], n(Gi ) ≤ 2m(Gi ). Maka dari itu, Σji=1 n(Gi ) ≤ 2Σji=1 m(Gi ) = 2m.
(3.1.14)
Karena bilangan unisiklis a′ (G) terbatas, m = O(n). Sehingga baris tiga dapat diselesaikan dalam O(n log n). Pada baris empat, karena ∆(G) = Σj i=1 ∆(Gi ), kita dapat memperumum pewarnaan sisi dari G1 , G2 , ..., Gj menjadi pewarnaan sisi dari G dengan ∆(G) warna. Sehingga algoritma menghabiskan waktu O(n log n).\\ Perhatikan bahwa algoritma EDGE-COLOR tidak perlu mengetahui dekomposisi dari G menjadi a(G) subgraf unisiklis.
3.1.4
Algoritma heuristik untuk pewarnaan sisi-f
Sebuah heuristik biasanya terdiri dari sebuah himpunan sederhana dari aturanaturan yang terpilih dengan baik yang diaplikasikan dalam pencarian solusi yang optimum. Dalam aplikasinya pada pewarnaan sisi, setiap warna yang diberikan pada
BAB 3. HASIL UTAMA
35
graf oleh heuristik haruslah sedekat mungkin ke solusi sebenarnya, yaitu sebesar ∆(G) atau ∆(G) + 1. Dalam tugas akhir ini, algoritma heuristik yang akan dibahas adalah garis, semut1 dan semut dan akan digunakan pada graf sederhana. garis Algoritma heuristik garis bekerja dengan cara mewarnai setiap sisi pada suatu graf G yang dinomori. Algoritma garis memulai pewarnaan sisi dari sisi yang terkait dengan titik yang berderajat terbesar. Sisi tersebut diwarnai dengan warna terkecil. Kemudian, berlanjut pada sisi dengan nomor yang lebih besar dan mewarnai sisi tersebut dengan warna sekecil mungkin. Setelah mewarnai sisi dengan nomor yang paling besar, algoritma garis mewarnai sisi dengan nomor awal dan bergerak ke nomor selanjutnya sampai semua sisi terwarnai. Sebagai contoh, graf dengan f (v) = 1 pada setiap v ∈ V pada Gambar 3.2 akan diwarnai menggunakan algoritma garis. Pertama-tama, sisi e2 diwarnai terlebih dahulu dengan warna 1 karena terkait dengan titik yang berderajat terbesar, yaitu v6 . Selanjutnya sisi e3 diwarnai dengan warna 1, karena kedua titik ujung dari sisie3 belum memiliki warna. Sisi e2 dan e3 terkait pada titik ujung dari e4 , sehingga e4 diberi warna 2. Selanjutnya algoritma akan terus mewarnai sampai sis e6 , setelah itu mewarnai sisi e1 . Pada pewarnaan diperiksa warna terkecil yang belum terdapat pada kedua titik ujung dari masing-masing sisi.
garis; diasumsikan setiap sisi telah dinomori (mulai);
1. cari titik derajat terbesar;
BAB 3. HASIL UTAMA
36
Gambar 3.2: Pewarnaan sisi menggunakan algoritma garis 2. cari sisi dengan nomor terkecil yang terkait dengan titik tersebut (misalkan sisike[nomor]); 3. untuk i:=1 sampai banyak-sisi lakukan; 4. (a) cek ketetanggaan dari sisike[nomor]; (b) warnai sisike[nomor] dengan warna sekecil mungkin; (c) nomor = nomor +1; (d) jika nomor > banyak-sisi maka nomor=1; (selesai);
semut Cara kerja algoritma ini, dianalogikan dengan cara kerja semut. Semut mengunjungi setiap titik yang telah dinomori secara berurut. Pada setiap kunjungannya, semut memberikan warna terkecil pada setiap sisi yang bertetangga titik yang dikunjungi.
BAB 3. HASIL UTAMA
37
Sebelum memberi warna pada suatu sisi, semut terlebih dahulu mengecek warna pada sisi-sisi yang bertetangga dengan sisi tersebut. Pertama-tama, semut mengunjungi titik yang berderajat terbesar. Setelah itu, semut mengunjungi titik dengan nomor yang lebih besar. Jika semut telah sampai pada titik bernomor terbesar, semut mengunjungi titik bernomor 1 dan berlanjut, sampai semua titik terkunjungi.
Gambar 3.3: Pewarnaan sisi menggunakan algoritma semut semut; diasumsikan setiap titik telah dinomori (mulai);
1. cari titik yang berderajat terbesar (Misalkan titikke[nomor]); 2. untuk i:=1 sampai banyak-titik lakukan
BAB 3. HASIL UTAMA
38
3. (a) cek ketetanggaan dari setiap sisi yang terkait dengan titikke[nomor]; (b) warnai sisi-sisi tersebut dengan warna sekecil mungkin; (c) nomor=nomor +1; (d) jika nomor > banyaktitik maka nomor=1; (selesai);
semutgaris Algoritma ini, mengambil analogi yang sama dengan algoritma semut. Tetapi, dalam algoritma ini, warna yang diperbolehkan untuk digunakan terbatas, yaitu sebanyak ∆f (G). Semut mulai dari titik yang memiliki derajat terbesar dan mewarnai semua sisi yang berkaitan dengan titik tersebut dengan warna yang berbeda. Kemudian semut mengunjungi tetangga dari titik tersebut. Jika titik memiliki sisi-sisi yang belum diwarnai, sisi tersebut akan diwarnai dengan warna terkecil yang tersedia, jika tidak mungkin, sisi diwarnai dengan warna terkecil yang telah ada pada titiktitik ujungnya. Jika semut menemui jalan buntu, semut loncat ke titik selanjutnya yaitu titik yang terdapat dalam daftar yang telah dikunjungi dan memiliki sisi yang belum diwarnai. Kemudian, untuk memperbaiki warna-warna yang salah digunakan adalah algoritma garis. semutgaris; (mulai);
1. cari titik yang berderajat terbesar (Misalkan v); 2. selama (semua sisi belum terwarnai) lakukan (a) jika warna > ∆ maka warnai dengan warna paling kecil yang muncul pada tetangga-tetanga sisi;
39
BAB 3. HASIL UTAMA masukkan sisi ke dalam daftar warna salah; lainnya
warnai sisi-sisi yang terkait dengan warna sekecil mungkin, (warna maksimal ∆); (b) jika semua tetangga dari v telah dikunjungi dan masih terdapat sisi yang belum diwarnai maka titik yang memiliki sisi yang belum terwarnai menjadi diberi nama v; lainnya tetangga dari v diberi nama v; 3. gunakan algoritma garis untuk membenarkan sisi dalam daftar warna salah; (selesai);
3.2
Implementasi Algoritma
Algoritma yang telah disusun, kemudian diimplementasikan ke dalam bahasa pemograman. Bahasa pemograman yang digunakan adalah JAVA.
Gambar 3.4: Tampilan awal
Langkah-langkah pengoperasian perangkat lunak adalah sebagai berikut:
BAB 3. HASIL UTAMA
40
1. pilih salah satu cara membuat graf; 2. jika memilih membuat graf menggunakan gambar, maka gambarlah graf yang diinginkan, jika memilih membuat graf menggunakan matriks maka akan muncul form pengisian jumlah titik dan matriks ketetanggaan yang diinginkan; 3. kemudian, atur f (v) di setiap titik pada graf G yang dibuat; 4. pilih algoritma untuk mengkonstruksi pewarnaan sisi-f pada graf yang dibuat; 5. jumlah warna yang dipakai dan derajat terbesar bisa dilihat pada form utama dan jika ingin melihat graf hasil reduksi dan graf hasil warna cukup tekan tombol yang tersedia.
Gambar 3.5: Konstruksi graf menggunakan gambar
41
BAB 3. HASIL UTAMA
Gambar 3.6: Mengatur f (v)
Gambar 3.7: Hasil reduksi
BAB 3. HASIL UTAMA
Gambar 3.8: Contoh hasil pewarnaan
Gambar 3.9: Contoh hasil pewarnaan
42
