ANALISIS PERBANDINGAN ALGORITMA GREEDY DENGAN ALGORITMA WELCH POWELL PADA PEWARNAAN PETA KELURAHAN KABUPATEN MAROS

Pewarnaan pada teori graf terdiri atas tiga macam yaitu pewarnaan simpul,
pewarnaan sisi, dan pewarnaan wilayah. Pada pewarnaan simpul, setiap simpul
diberi warna sedemikian sehingga setiap simpul yang bertetangga memiliki warna
yang berbeda. Tujuan utama dari pewarnaan simpul adalah mendapatkan
banyaknya warna minimum yang dibutuhkan untuk mewarnai suatu graf, yang
biasa disebut bilangan kromatik. Salah satu penerapan pewarnaan simpul adalah
pewarnaan suatu peta sedemikian sehingga setiap daerah yang bersebelahan harus
diberi warna yang berbeda. Algoritma yang digunakan pada tugas akhir ini ialah
algoritma Greedy dan algoritma Welch Powell. Kedua algoritma ini akan
digunakan untuk mewarnai peta kelurahan kabupaten Maros. Pewarnaan peta
kelurahan kabupaten Maros dengan kedua algoritma tersebut, mendapatkan
bilangan kromatik yang sama yaitu X(G) ≤ 5. Kemudian dari hasil pewarnaan peta
kelurahan kabupaten Maros dapat disimpulkan bahwa algoritma Welch Powell
lebih efisien dibandingkan algoritma Greedy karena jumlah operasi Algoritma Welch
Powell lebih kecil dibandingkan Algoritma Greedy yaitu Algoritma Welch Powell 106
operasi sedangkan Algoritma Greedy 108 operasi.

Kata Kunci : Algoritma Greedy, Algoritma Welch Powell, Bilangan Kromatik