IMPLEMENTASI PEWARNAAN GRAF MENGGUNAKAN ALGORITMA WELSH-POWELL PADA PETA INDONESIA

Rizky Hariyani -  , Indonesia
Muhamad Ali Misri* -  Universitas Islam Negeri (UIN) Siber Syekh Nurjati Cirebon, Indonesia
Hendri Handoko -  Universitas Islam Negeri (UIN) Siber Syekh Nurjati Cirebon, Indonesia

DOI : 10.24269/silogisme.v9i2.9409

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.


Supplement Files

Keywords
Pewarnaan Graf; Algoritma Welsh-Powell; Peta Indonesia
  1. Afriantini, A., Helmi, H., & Fran, F. (2019). Pewarnaan Simpul, Sisi, Wilayah pada Graf dan Penerapannya. Bimaster: Buletin Ilmiah Matematika, Statistika Dan Terapannya, 8(4), 773–782. https://doi.org/10.26418/bbimst.v8i4.36037
  2. Ammar, M. (2019). Implementasi Algoritma Sequential dan Welch Powell pada Pewarnaan Graf (Studi Kasus Pewarnaan Peta Kota Makassar). Jurnal Varian, 3(1), 28–35. https://doi.org/10.30812/varian.v3i1.488
  3. Ardianto, S., Monim, H. O. L., Widjajanti, T., & Sesa, J. (2022). Aplikasi Pewarnaan Graf dalam Penentuan Distrik yang Strategis di Kabupaten Manokwari dengan Algoritma Welch Powell. Prosiding Seminar Nasional MIPA UNIPA, 126–141. https://doi.org/10.30862/psnmu.v7i1.18
  4. Aslan, M., & Baykan, N. A. (2016). A Performance Comparison of Graph Coloring Algorithms. International Journal of Intelligent Systems and Applications in Engineering (IJISAE), 4(Spesial Issue), 1–7.
  5. Buhaerah, B., Busrah, Z., & Sanjaya, H. (2022). Teori Graf dan Aplikasinya (Pertama). Living Spiritual Quotient.
  6. Daniel, F., & Taneo, P. N. L. (2019). Teori Graf. Deepublish.
  7. Franconeri, S. L., Padilla, L. M., Shah, P., Zacks, J. M., & Hullman, J. (2021). The Science of Visual Data Communication: What Works. Psychological Science in The Public Interest, 22(3), 110–161. https://doi.org/10.1177/15291006211051956
  8. Gani, R. R. (2018). Penerapan Pewarnaan Titik pada Graf untuk menyusun Jadwal Pelajaran (Studi Kasus MI Al Wathoniyyah 02 Semarang). Universitas Negeri Semarang.
  9. Himayati, A. I. A., Firdaus, E. M., & Findasari, F. (2023). Pewarnaan Graf pada Peta Wilayah Kota Semarang dengan Algoritma Greedy. Jurnal Ilmu Komputer Dan Matematika, 4(1), 9–16.
  10. Hutasoit, W. L. (2018). Analisa Pemindahan Ibukota Negara. Dedikasi: Jurnal Pengabdian Kepada Masyarakat, 19(2), 108–128. https://doi.org/10.31293/ddk.v39i2.3989
  11. Jofie, M. Z., Bahri, S., & Baqi, A. I. (2020). Aplikasi Algoritma Greedy untuk Pewarnaan Wilayah pada Peta Kota Padang Berbasis Teorema Empat Warna. Jurnal Matematika UNAND, 9(4), 294–301. https://doi.org/10.25077/jmu.9.4.294-301.2020
  12. Jufri, K. Al, & Agustiani, R. (2023). Implementasi Algoritma Greedy pada Pewarnaan Wilayah Peta Kecamatan Gelumbang Muara Enim. DJMA: Diophantine Journal of Mathematics and Its Aplications, 2(1), 37–44. https://doi.org/10.33369/diophantine.v2i01.28347
  13. Lestari, R. M. A. (2014). Perbandingan Algoritma Welch Powell dengan Algoritma Greedy pada Pewarnaan Peta Provinsi Sumatera Utara. Universitas Islam Negeri Sultan Syarif Kasim Riau.
  14. Maftukhah, U., Amiroch, S., & Pradana, M. S. (2020). Implementasi Algoritma Greedy pada Pewarnaan Wilayah Kecamatan Sukodadi Lamongan. UJMC: Unisda Journal of Mathematics and Computer Science, 6(2), 29–38. https://doi.org/doi.org/10.52166/ujmc.v6i2.2391
  15. Meilani, S., Permanasari, Y., & Sukarsih, I. (2016). Pewarnaan Titik pada Graf Menggunakan Algoritma Baris dan Implementasinya dalam Matlab. Prosiding Matematika, 2(1), 1–4. https://doi.org/10.29313/.v0i0.2712
  16. Mussafi, N. S. M. (2015). Penerapan Greedy Coloring Algorithm pada Peta Kotamadya Yogyakarta berbasis Four-colour Theorem. Kaunia: Integration Dan Interconnection Islam and Science Journal, 11(1), 19–26.
  17. Nasir, A. M., Faisal, F., & Setyawan, D. (2022). Optimalisasi Penjadwalan Mata Kuliah Menggunakan Teori Pewarnaan Graf. Proximal: Jurnal Penelitian Matematika Dan Pendidikan Matematika, 5(1), 57–69. https://doi.org/10.30605/proximal.v5i1.1398
  18. Qomaruddin, M., Alawy, M. T., & Sugiono, S. (2017). Perancangan Aplikasi Penentu Rute Terpendek Perjalanan Wisata di Kabupaten Jember Menggunakan Algoritma Dijkstra. Science Electro, 6(2), 31–39.
  19. Qomaruddin, M., Bismi, W., & Hariyanto, D. (2022). Pewarnaan Graf pada Peta Provinsi Jawa Barat menggunakan Algoritma Welch-Powell. Justin: Jurnal Sistem Dan Teknologi Informasi, 10(2), 258–263. https://doi.org/10.26418/justin.v10i2.53829
  20. Rahma, A. N., Rahmawati, R., & Zukrianto, Z. (2021). Aplikasi Pewarnaan Graf pada Peta Provinsi Riau menggunakan Algoritma Greedy. Square: Journal of Mathematics and Mathematics Education, 3(1), 41–55. https://doi.org/10.21580/square.2021.3.1.7410
  21. Rusli, M., & Sutopo, H. (2014). Pengembangan Aplikasi Pewarnaan Graf Berbasis Multimedia pada Mata Kuliah Matematika Distrit. Kalbi Scientia: Jurnal Sains Dan Teknologi, 1(1), 1–12.
  22. Schloss, K. B., Gramazio, C. C., Silverman, A. T., Parker, M. L., & Wang, A. S. (2019). Mapping Color to Meaning in Colormap Data Visualizations. IEEE Transactions on Visualization and Computer Graphics, 25(1), 810–819. https://doi.org/10.1109/TVCG.2018.2865147
  23. Sunarni, T., Bendi, R. K. J., & Alfian, A. (2018). Penerapan Teknik Pewarnaan Simpul Graf pada Permasalahan Jadwal Kuliah. Prosiding Ritekra, 83–91.
  24. Undang-Undang Republik Indonesia Nomor 20 Tahun 2012 tentang Pembentukan Provinsi Kalimantan Utara.
  25. Undang-Undang Republik Indonesia Nomor 29 Tahun 2022 tentang Pembentukan Provinsi Papua Barat Daya.
  26. Yahya, H. M. (2018). Pemindahan Ibu Kota Negara Maju dan Sejahtera. Jurnal Studi Agama Dan Masyarakat, 14(1), 21–30. https://doi.org/10.23971/jsam.v14i1.779

Full Text: Supp. File(s):
Surat pernyataan keaslian naskah
Subject
Type Other
  Download (B)    Indexing metadata
Article Info
Submitted: 2024-05-29
Published: 2024-12-15
Section: Artikel
Article Statistics: