IMPLEMENTASI PEWARNAAN GRAF MENGGUNAKAN ALGORITMA WELSH-POWELL PADA PETA INDONESIA - Hariyani, Rizky; Misri, Muhamad Ali; Handoko, Hendri (Universitas Muhammadiyah Ponorogo, 2024)
Sebuah peta dikatakan ideal jika dilengkapi dengan pewarnaan wilayah sehingga dapat dengan mudah dipahami oleh pembaca. Pewarnaan peta lebih efektif jika dapat memberikan warna seminimum mungkin agar wilayah-wilayah yang berbatasan dapat diberikan warna yang berbeda. Pewarnaan peta yang seperti ini dapat diselesaikan dengan pewarnaan graf. Algoritma Welsh-Powell dapat digunakan untuk mewarnai simpul pada graf sehingga mampu memberikan jumlah warna minimum. Selain itu, algoritma Welsh-Powell juga dapat menentukan wilayah strategis dari sebuah peta atau wilayah. Penelitian ini menggunakan desain studi pustaka dilakukan dengan mengkaji berbagai sumber referensi yang berkaitan dengan pewarnaan graf. Tujuan penelitian yaitu untuk mengetahui implementasi algoritma Welsh-Powell dalam pewarnaan graf pada peta Indonesia, jumlah warna minimum untuk mewarnai peta Indonesia, dan wilayah provinsi yang paling strategis di Indonesia. Penelitian ini menghasilkan sebuah peta dengan tata warna minimum berjumlah 4 warna, yakni merah, biru, kuning, dan hijau dengan bilangan kromatikÂ Ï‡(G)=4. Pewarnaan peta Indonesia menggunakan algoritma Welsh-Powell menghasilkan wilayah Provinsi Jambi sebagai provinsi strategis karena memiliki derajat tertinggi, yaitu 6 atau d(v6)=6.