APLIKASI ALGORITMA GREEDY UNTUK PEWARNAAN WILAYAH PADA PETA KOTA PADANG BERBASIS TEOREMA EMPAT WARNA

Abstract

. Kecamatan-kecamatan pada peta kota Padang diwarnai dengan menggunakan algoritma Greedy. Pewarnaan wilayah yang mengasumsikan sebuah kecamatan sebagai simpul dan sisi sebagai penghubung antar kecamatan yang bertetangga tersebut, menggunakan teorema empat warna yang menyatakan banyak warna minimum yang akan digunakan dalam mewarnai peta. Sebelum algoritma Greedy digunakan, graf dual peta tersebut dikonstruksi dan derajat tiap simpul ditentukan. Pada penggunaan algoritma Greedy, himpunan kandidat warna dan inisialisasi solusi dibuat. Selanjutnya, dilakukan pewarnaan pertama kali untuk simpul dengan derajat terbesar, dengan cara memilih secara sebarang warna pada himpunan kandidat. Kemudian, periksa kelayakan dari warna dengan menggunakan prinsip bahwa dua simpul yang bertetangga tidak boleh memiliki warna yang sama. Warna yang dihasilkan kemudian merupakan elemen dari himpunan solusi. Proses pewarnaan tersebut diulangi hingga semua wilayah kecamatan pada peta tersebut diwarnai.

Kata Kunci: Algoritma Greedy, Pewarnaan Wilayah, Teorema Empat Warna.