PEWARNAAN GRAF PADA PETA OHOI LANGGUR MENGGUNAKAN ALGORITMA GREEDY

Zikri Alkatiri; Shafriaty Kepa; Ernawati

doi:10.51135/7s2mzg33

Authors

Zikri Alkatiri Universitas Banda Naira
Shafriaty Kepa Universitas Banda Naira
Ernawati Universitas Banda Naira

DOI:

https://doi.org/10.51135/7s2mzg33

Keywords:

Pewarnaan Wilayah, Graf, Algoritma Greedy

Abstract

Pewarnaan wilayah bukanlah hanya sekedar memberikan warna yang berbeda pada suatu wilayah. Tetapi juga untuk menentukan jumlah jenis warna yang optimal pada pewarnaa tersebut. Pada penelitian ini, digunakan teori graf dengan algoritma Greedy untuk menentukan jenis warna yang optimal pada peta ohoi/desa Langgur, Algoritma Greedy merupakan salah satu bentuk algoritma yang berkembang untuk menyelesaikan masalah pewarnaan graf sehingga dihasilkan warna minimal yang harus digunakan tanpa adanya Lingkungan yang saling berbatasan menggunakan warna yang sama. Metode penelitian yang digunakan pada penelitian ini adalah metode penelitian studi literatur. Peneliti menggumpulkan referensi melalui artikel ilmiah dan data-data dari Pangkalan Data Langgur (PDL). Berdasarkan hasil penelitian diperoleh jumlah warna minimum pada pewarnaan peta ohoi Langgur adalah 4 jenis warna sebagai solusi warna minimal yang digunakan untuk mewarnai semua wilayah ohoi Langgur.

Downloads

Download data is not yet available.

References

[1] Bustan, A. W., & Salim, M. R. (2019). Penerapan Pewarnaan Graf Menggunakan Algoritma Welch Powell untuk Menentukan Jadwal Bimbingan Mahasiswa. Jurnal THEOREMS (The Original Research of Mathematics), 4(1), 79–86.

[2] Brun, Yuriy. (2002). The Four-Color Theorem. Undergraduate Journal of Mathematics. 21–28.

[3] Golumbic, M. C. (2018). Total coloring of rooted path graphs. Information Processing Letters, 135, 73–76. https://doi.org/10.1016/j.ipl.2018.03.002

[4] Himayati, A. I. A., Alfiana, K., Putra, M. A. J. D., & Utami, R. (2020). Aplikasi Pewarnaan Graf Dengan Metode Welch Powell Pada Pembuatan Jadwal Ujian Proposal Skripsi Program Studi Farmasi Universitas Muhammadiyah Kudus Ade Ima Afifa Himayati. Jurnal Ilmu Komputer Dan Matematika, 1(1), 32–39.

[5] Li, Yu., Lucet Corinne., Moukrim, Aziz., Sghiouer, Kaoutar., Greedy Algorithms for the Minimum Coloring Problem, Logistique et transport, Sousse: Tunisia (2009), Page-00451266, Volume I, 28 Januari 2010

[6] Mohamed, T. M. (2018). Enhancing The Performance of the Greedy Algorithm Using Chicken Swarm Optimization: An Application to Exam Scheduling Problem Watermarking View project Feature Selection View project Enhancing The Performance of the Greedy Algorithm Using Chicken Swarm Op. Egyptian Computer Science Journal, 42(1), 1–17. https://www.researchgate.net/publication/322682948

[7] Mamahit, J. A., Aloysius, D. C., & Suwono, H. (2020). Efektivitas Model Project- Based Learning Terintegrasi STEM (PjBL-STEM) terhadap Keterampilan Berpikir Kreatif Siswa Kelas X. Jurnal Pendidikan: Teori, Penelitian, Dan Pengembangan, 5(9), 1284. https://doi.org/10.17977/jptpp.v5i9.14034

[8] Maftukhah, U., Amiroch, S., & Pradana, M. S. (2020). Implementasi Algoritma Greedy Pada Pewarnaan Wilayah Kecamatan Sukodadi Lamongan. Unisda Journal of Mathematics and Computer Science (UJMC),6(2), 29–38. https://doi.org/10.52166/ujmc.v6i2.2391

[9] Nasution, R. R., & Sitompul, P. (2018). Aplikasi Pewarnaan Graf Pada Penyusunan Jadwal Mata Kuliah Jurusan Matematika Di Fakultas Matematika Dan Ilmu Pengetahuan Alam Universitas Negeri Medan. Karismatika, 6(2), 11–29.

[10] Sánchez-Oro, J., & Duarte, A. (2018). Iterated Greedy algorithm for performing community detection in social networks. Future Generation Computer Systems, 88, 785–791.

[11] Supiyandi, M. E. (2018). Penerapan Teknik Pewarnaan Graph Pada Penjadwalan Ujian Dengan. Jurnal Ilmu Komputer Dan Informatika, 03(01), 58–63.

[12] Widiyatni, W., Rafida, V., Sibali, H. E., & Kusuma, H.A.(2020). Penerapan Pewarnaan Graf Untuk Menentukan Wisata Kuliner Di Samarinda. Jurnal Ilmiah Matrik, 22(2), 177–186. https://doi.org/10.33557/jurnalmatrik.v2 2i2.988