Penerapan Pewarnaan Graf pada Peta Kecamatan di Kabupaten Karawang Menggunakan Algoritma Welch-Powell
Keywords:
Algoritma Welch-Powell, Bilangan Kromatik, Pewarnaan GrafAbstract
Penelitian ini bertujuan menerapkan Algoritma Welch–Powell untuk menentukan jumlah warna minimum pada peta administratif Kabupaten Karawang sehingga tidak terjadi konflik warna antarwilayah yang saling berbatasan. Penelitian menggunakan pendekatan deskriptif kuantitatif dengan metode studi kasus terhadap 30 kecamatan di Kabupaten Karawang. Data penelitian bersumber dari peta administratif yang diperoleh dari Badan Informasi Geospasial (BIG) dan Dinas Tata Ruang Kabupaten Karawang. Peta tersebut direpresentasikan ke dalam graf tidak berarah dengan kecamatan sebagai simpul (vertex) dan batas wilayah sebagai sisi (edge). Proses analisis dilakukan melalui pengurutan simpul berdasarkan derajat tertinggi, pewarnaan graf menggunakan Algoritma Welch–Powell, serta validasi hasil pewarnaan untuk memastikan tidak ada dua simpul bertetangga yang memiliki warna sama. Hasil penelitian menunjukkan bahwa graf peta Kabupaten Karawang dapat diwarnai secara optimal menggunakan empat warna, yaitu merah, kuning, hijau, dan biru, sehingga bilangan kromatik graf adalah χ(G) = 4. Hasil ini menunjukkan bahwa Algoritma Welch–Powell mampu menghasilkan pewarnaan graf yang efisien dan konsisten pada pemodelan wilayah administratif. Simpulan penelitian ini adalah bahwa Algoritma Welch–Powell dapat digunakan sebagai pendekatan matematis yang praktis dalam pewarnaan peta, khususnya untuk mendukung visualisasi data spasial dan pengembangan sistem informasi geografis di Indonesia.
Downloads
References
Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. London: Springer.
Diestel, R. (2017). Graph Theory (5th ed.). Berlin: Springer
Hariyani, S., Nugroho, A., & Setiawan, B. (2022). Penerapan Algoritma Welch–Powell dalam Pewarnaan Peta Provinsi Jawa Barat untuk Penentuan Bilangan Kromatik. Jurnal Matematika dan Aplikasinya, 15(2), 115–123.
Malviya, A., Agrawal, B., & Kumar, S. (2024). Graph Coloring Algorithm for Course Timetable Scheduling Problem. ShodhKosh: Journal of Visual and Performing Arts, 5(3), 452–460.
Maro, F. A. (2022). Analisis Pewarnaan Graf pada Peta Pulau Alor Menggunakan Algoritma Welch–Powell. Jurnal Ilmu Komputer dan Sistem Informasi, 10(1), 45–53.
Maro, L., Ena, M., & Klaping, E. (2022). Application of the Welch–Powell Algorithm on Graph Coloring in Mapping Village Area in Alor Island, East Nusa Tenggara. Jurnal Ilmiah Wahana Pendidikan, 8(23), 569–575.
Munir, R. (2016). Algoritma dan Pemrograman dalam Teori Graf. Bandung: Informatika.
Pratama, R., & Kurniawan, D. (2021). Implementasi Algoritma Welch–Powell pada Jaringan Transportasi Menggunakan Model Graf. Jurnal Sains dan Teknologi Informasi, 7(4), 230–238.
Qomaruddin, M., Bismi, M., & Hariyanto, A. (2022). Penerapan Algoritma Welch–Powell untuk Pewarnaan Graf pada Peta Wilayah Administratif. Jurnal Ilmiah Komputer dan Informatika (KOMPUTA), 11(2), 85–93.
Rosen, K. H. (2019). Discrete Ma thematics and Its Applications (8th ed.). New York: McGraw-Hill Education.
Sugiyono. (2022). Metode Penelitian Kuantitatif, Kualitatif, dan R&D. Bandung: Alfabeta.
Surbakti, N. M. (2023). Implementation of Graph Coloring Using the Welch–Powell Algorithm in Scheduling Thesis Proposal Seminars in the Mathematics Study Program at Universitas Negeri Medan. Jurnal Digital Sistem Informasi, 2(2), 45-46.
Sutadi, D. (2023). Analisis Implementasi Algoritma Welch–Powell pada Pewarnaan Graf untuk Penjadwalan dan Pemetaan. Jurnal Teknologi dan Sains Komputasi, 9(1), 44–52.
Svarcmajer, M., Ivanović, D., Rudec, T., & Lukić, I. (2025). Application of Graph Theory and Variants of Greedy Graph Coloring Algorithms for Optimization of Distributed Peer-to-Peer Blockchain Networks. Technologies, 13(1), 33-45.
West, D. B. (2001). Introduction to Graph Theory (2nd ed.). NJ: Prentice Hall.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Wirda Ardayanti, Desi Rahmawati, Sofi Nadea Putri, Rikayanti
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
