ALGORITMA UNTUK MENGKONSTRUKSI PEWARNAAN SISI-f PADA GRAF
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Sidang Sarjana Program Studi Matematika ITB
Oleh: Ismail Hasbullah 10103010
Program Studi Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung 2008
ALGORITMA UNTUK MENGKONSTRUKSI PEWARNAAN SISI-f PADA GRAF
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Sidang Sarjana Program Studi Matematika ITB
Oleh:
Ismail Hasbullah 10103010
Telah Diperiksa dan Disetujui, Bandung, Februari 2008 Dosen pembimbing
Dr. M Salman A.N. NIP.132084478
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2008
iii (Dan janganlah kamu mengikuti apa yang kamu tidak mempunyai pengetahuan tentangnya. Sesungguhnya pendengaran, penglihatan dan hati, semuanya itu akan diminta pertanggungjawabannya) (Al Isra : 26)
Abstract An f -coloring of a simple graph G = (V, E) is to color each edge in G so that, each color appears at each vertex v at most f (v) times where f : V → ℵ. Since f -coloring where f (v) = 1 for each vertex v ∈ V is NP-complete problem, then in general, f -coloring is NP-complete problem. Therefore, it is very unlikely that there exists an exact algorithm which solves the edge-coloring problem in polynomial time. This final project gives efficient algorithms to find edge-coloring and f -coloring for various classes of graphs such as wheel graphs, fan graphs and graphs with particular degeneracy, aboricity, and unicyclic index . Then, for other classes of graphs, we used heuristic algorithm. Key words: f-coloring, wheel graphs, fan graphs, degeneracy, arboricity, unicyclic index, thickness, heuristic.
iv
Abstrak Misalkan f adalah fungsi dari himpunan titik ke bilangan asli. Pewarnaan sisif dari suatu graf G = (V, E) adalah mewarnai setiap sisi pada graf G dengan warna sesedikit mungkin sehingga pada setiap v ∈ V , paling banyak f (v) sisi yang berkaitan, berwarna sama. Hoyler membuktikan bahwa pewarnaan sisi-f pada kasus f (v) = 1 merupakan masalah NP-complete sehingga secara umum, pewarnaan sisi-f merupakan masalah NP-complete. Akibatnya, tidak terdapat algoritma dalam waktu polinom yang dapat mengkonstruksi pewarnaan sisi-f pada graf. Dalam tugas akhir ini, dilakukan beberapa pendekatan untuk mengkonstruksi pewarnaan sisi-f pada graf, diantaranya dengan mengkonstruksi algoritma yang efisien untuk beberapa kelas pada graf. Kelas-kelas graf yang dibahas adalah graf roda, graf kipas dan graf yang memiliki degeneracy, arboricity, dan bilangan unisiklis tertentu. Untuk menyelesaikan kelas graf lainnya, digunakan algoritma heuristik. Sehingga dalam tugas akhir ini didapat algoritma yang dapat mengkonstruksi pewarnaan sisif pada seluruh kelas dari graf. Kata kunci: pewarnaan sisi-f, graf roda, graf kipas, degeneracy, arboricity, bilangan unisiklis, heuristik.
v
Prakata Alhamdulillah segala puji dan syukur ke hadirat Allah SWT, karena berkat rahmat dan karunia-Nya penulis dapat menyelesaikan tugas akhir pada waktunya. Tugas akhir dengan topik ”Algoritma Untuk Mengkonstruksi Pewarnaan Sisi-f Pada Graf” ini disusun atas dasar ketertarikan penulis terhadap masalah NP -complete. Banyak pihak yang telah memberikan bantuan kepada penulis dalam pengerjaan tugas akhir ini baik secara langsung maupun tidak langsung. Oleh karena itu, pada kesempatan ini penulis ingin mengucapkan terima kasih kepada: 1. Bapak dan Ibu , Dr. Sudradjat dan Dra Deti Sudiarti, atas segala doa, semangat, kesabaran, pengorbanan dan kasih sayang mereka kepada penulis. Ikhsan, Fitri dan keluarga tercinta yang terus memberi semangat dan mendoakan penulis. 2. Dr. M. Salman A.N. selaku dosen pembimbing yang dengan sabar membimbing serta memberikan bantuan dan arahan sehingga tugas akhir ini dapat diselesaikan. 3. Dr. Janny Lindriani selaku dosen wali akademik yang telah memperhatikan dan memberikan motivasi selama penulis menempuh proses pendidikan di ITB. 4. Dr.
Rinovia Simanjuntak dan Dr.
R. A. D. Kooswinarsinindyah selaku
dosen penguji yang telah memberikan banyak saran dan kritik sehingga tugas ahir ini menjadi lebih baik dan seluruh staf pengajar di kampus Institut Teknologi Bandung yang telah memberikan banyak kesempatan bagi penulis vi
vii
PRAKATA untuk mengembangkan potensi selama berada di kampus ini.
5. Bu Dyah beserta staf tata usaha Program Studi Matematika yang selalu mengingatkan penulis agar menunaikan kewajiban adminstratif selama menempuh pendidikan di kampus ini. 6. Amru, Syahril, iQs, Indro, Dede, Sam, Angga, Alan, Asenk, Fiska, Mega selaku teman seperjuangan penulis yang senantiasa memberikan pertolongan, nasihat, dan saran. 7. Hendra, Dani, Gustian, Adit, Adan, Opik, Dona, Onta, Riti, Anggun, Novi, Ani dan teman-teman 2003 lainnya selaku teman yang memberikan warna persahabatan selama penulis berada di kampus. 8. Kawan - kawan HIMATIKA ITB selaku sahabat yang senantiasa menemani perjuangan dalam membangun HIMATIKA. 9. Kawan-kawan pengembang open source dan free software (Java, TEX, Winamp, dll) selaku pendukung penulis dalam penyusunan tugas akhir sehingga produknya dapat digunakan penulis dalam penyusunan tugas akhir ini. Penulis menyadari bahwa masih banyak keterbatasan pengetahuan yang dimiliki dan kekurangan pada tugas akhir ini. Oleh karena itu, saran dan kritik dari berbagai pihak sangat penulis nantikan. Akhir kata, penulis persembahkan tugas akhir yang sangat sederhana ini. Mudah - mudahan memberikan manfaat bagi para pembaca sekalian umumnya dan bagi penulis khususnya.
Bandung, Februari 2008 Penulis
Ismail Hasbullah
Daftar Isi Halaman Pengesahan
ii
Abstract
iv
Abstrak
v
Prakata
vi
Daftar Isi
viii
1 PENDAHULUAN
1
1.1
Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Rumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3
Sistematika Pembahasan . . . . . . . . . . . . . . . . . . . . . . . . .
3
2 LANDASAN TEORI
5
2.1
Definisi Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2
Beberapa Kelas Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3
Pewarnaan Sisi-f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4
Reduksi Pewarnaan Sisi-f
2.5
Kompleksitas Komputasi . . . . . . . . . . . . . . . . . . . . . . . . . 22
. . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.1
Analisis algoritma . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.2
Teori kompleksitas . . . . . . . . . . . . . . . . . . . . . . . . 24
viii
ix
Daftar Isi 3 HASIL UTAMA 3.1
3.2
27
Penyusunan Algoritma . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.1
Algoritma Reduksi . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.2
Algoritma warna-sisi-roda-kipas . . . . . . . . . . . . . . . . . 29
3.1.3
Algoritma EDGE-COLOR [7] . . . . . . . . . . . . . . . . . . 30
3.1.4
Algoritma heuristik untuk pewarnaan sisi-f
. . . . . . . . . . 34
Implementasi Algoritma . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 KESIMPULAN
43
Daftar Pustaka
44
Daftar Tabel 2.1
Matriks ketetanggaan dari graf pada Gambar 2.3 . . . . . . . . . . .
8
2.2
Matriks keterkaitan dari graf pada Gambar 2.3 . . . . . . . . . . . . .
8
x
Daftar Gambar 2.1
Graf G1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
Graf yang memuat loop . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3
Graf sederhana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.4
Graf 2-teratur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.5
G4 [v4 ] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.6
(a) Graf terhubung (b) Graf tak terhubung . . . . . . . . . . . . . . . 10
2.7
(a) K4 (b) Graf trivial (c) Graf bipartit . . . . . . . . . . . . . . . . . 11
2.8
Graf hutan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.9
(a) Graf roda (b) Graf lintasan (c) Graf kipas . . . . . . . . . . . . . 12
2.10 Graf 2-degenerate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.11 Pengurutan titik pada graf kipas dan graf roda . . . . . . . . . . . . . 14 2.12 a(G9 ) = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.13 Graf G dengan a′ (G) = 2 . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.14 Graf G dengan χ′f (G) = 4 . . . . . . . . . . . . . . . . . . . . . . . . 17 2.15 Reduksi graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.16 Algoritma RataRataPrefix1 . . . . . . . . . . . . . . . . . . . . . . . 22 3.1
Algoritma umum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2
Pewarnaan sisi menggunakan algoritma garis . . . . . . . . . . . . . . 36
3.3
Pewarnaan sisi menggunakan algoritma semut . . . . . . . . . . . . . 37
3.4
Tampilan awal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5
Konstruksi graf menggunakan gambar . . . . . . . . . . . . . . . . . . 40
3.6
Mengatur f (v) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 xi
DAFTAR GAMBAR
xii
3.7
Hasil reduksi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.8
Contoh hasil pewarnaan . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.9
Contoh hasil pewarnaan . . . . . . . . . . . . . . . . . . . . . . . . . 42
