PERBANDINGAN TIGA ALGORITMA PEWARNAAN GRAF DALAM MEWARNAI GAMBAR MOZAIK GEOMETRIS

Raden Gunawan Santosa, Junius Karel Tampubolon

Abstract


This study compares three graph coloring algorithms (Greedy, Welch–Powell (WP), and Marble–Matula–Isaacson (MMI)) applied to geometric mosaic images in the form of undirected graphs. Each vertex represents a region in the image, while edges connect neighboring regions. Two graphs are used as research objects, namely graph (a) with |V(GA)| = 56, |E(GA)| = 96, D(GA) = 0.062234, δ(GA) = 2, Δ(GA) = 7, and graph (b) with |V(GB)| = 55, |E(GB)| = 115, D(GB) = 0.0174, δ(GB) = 3, Δ(GB) = 6. The three algorithms are tested through 15 experiments to minimize the number of colors so that no two neighboring vertices have the same color. The Wilcoxon Rank-Sign statistical test shows that WP and MMI are significantly more efficient than Greedy, with p-values of 0.0006269 and 0.01073 (<0.05), respectively. The theoretical reason why the Greedy algorithm is not optimal compared to the other two algorithms is because the Greedy algorithm colors the vertices according to the input order without a vertex selection strategy based on degree or graph structure. These results confirm that WP and MMI are able to approach the theoretical limit of planar graph coloring as stated by the Four Color Theorem, which states that every planar graph can be colored with no more than four colors.


Keywords


Graph Coloring, Greedy, Matula-Marble-Isaacson, Welch-Powell, Wilcoxon Rank-Sign

Full Text:

PDF

References


Bahri, S., Novrial, G. M., & Narwen, N. (2023). Pemrograman Pewarnaan Graf Pada Penjadwalan Mata Kuliah Jurusan Matematika. Jurnal Lebesgue : Jurnal Ilmiah Pendidikan Matematika, Matematika dan Statistika. Vol. 4(1), 417–431. https://doi.org/10.46306/lb.v4i1.260

Diestel, R. (2017). Graph Theory, 5th edition 2017. Springer-Verlage.

Enot, F. M., Seto, S. B., & Bantas, M. G. D. (2024). Eksplorasi Bentuk Anyaman Rotan pada Usaha Kerajinan Masyarakat Desa Sita. Jupika: Jurnal Pendidikan Matematika. Vol. 7(2), 79–85. https://doi.org/10.37478/jupika.v7i2.3172

Ewens, W. J., & Brumberg, K. (2023). Introductory Statistics for Data Analysis. Springer International Publishing.

Fadilah, A. N., Subarkah, P., Pramudya, R. S., & Syabani, A. (2024). A Comparison of Welch Powell Algorithm and Greedy Algorithm in Odd Semester Lecture Room Scheduling Optimization Faculty of Computer Science. JTAM (Jurnal Teori Dan Aplikasi Matematika). Vol. 8(4), 1169–1182. http://journal.ummat.ac.id/index.php/jtam

John, Clark, & Allan, H.D (1995). Firstlook_Graphtheory. Allied Publishers LTD and World Scientific.

Kraleva, R., Kralev, V., & Katsarski, T. (2025). An Analysis Between The Welsh-Powell and DSatur Algorithms for Coloring of Sparse Graphs. International Journal of Electrical and Computer Engineering (IJECE). Vol. 15(4), 3867–3875.

https://doi.org/10.11591/ijece.v15i4.pp3867-3875

Latif, S. A., Hasan, I. K., Achmad, N., Wungguli, D., & Nashar, L. O. (2024). Utilizing the Welch-Powell Algorithm and the IDO (Incident Degree Ordering) Algorithm in Traffic Light Settings. Vol. 21(1), 62–70. https://doi.org/10.31851/sainmatika.v21i1.9630

Lubis, H., & Nuraini, S. (2024). Eksplorasi Pewarnaan Graf dalam Identifikasi Destinasi Kuliner Menggunakan Algoritma Welch Powell di Kota Serang. Jurnal Ilmiah Matematika Realistik. Vol. 5(2), 390–396. https://doi.org/10.33365/ji-mr.v5i2.5996

Manullang, L. H., & Marpaung, F. (2024). Penerapan Pewarnaan Graf Menggunakan Algoritma Welch-Powell Untuk Keefektifan Lampu Lalu Lintas di Kota Medan. ULIL ALBAB : Jurnal Ilmiah Multidisiplin. Vol. 3(8), 694–703.

Maro, L. (2022). Application of the Welch-Powell Algorithm on Graph Coloring in Mapping Village Area in Alor Island, East Nusa Tenggara Landerius Maro Dosen Universitas Tribuana Kalabahi. Jurnal Ilmiah Wahana Pendidikan. Vol. 8(23), 569–575. https://doi.org/10.5281/zenodo.7421798

Matula, D. W., & Beck, L. L. (1983). Smallest-Last Ordering and Clustering and Graph Coloring Algorithms. Vol. 30(3), 417–427. https://doi.org/10.1145/2402.322385

Maulani, A., & Wulandari, D. (2023). Implementasi Pewarnaan Graf pada Pengelompokan Siswa/i Rumah Belajar Azalea dengan Algoritma Welch-Powell. Jurnal Siger Matematika. Vol. 04(02), 37–42.

Mirdayanti, M., Nur, F., & Abrar, A. I. P. (2024). Eksplorasi Geometri dalam Motif Batik Lontara Bugis: Pendekatan Etnomatematika pada Pembelajaran. Jupika: Jurnal Pendidikan Matematika. Vol. 7(2), 195–202. https://doi.org/10.37478/jupika.v7i2.5134

Nasir, M., Faisal, & Setyawan, D. (2022). 1398-Article Text-3993-1-10-20220210. Jurnal Penelitian Matematika dan Pendidikan Matematika. Vol. 5, 57–69.

Nuryatma, N., Wasono, W., Deny, F., & Amijaya, T. (2024). Aplikasi Pewarnaan Graf untuk Optimalisasi Distribusi Beras di Badan Usaha Logistik (BULOG) Kota Samarinda. BASIS Jurnal Ilmiah Matematika. Vol. 3(1), 38–53. http://jurnal.fmipa.unmul.ac.id/index.php/Basis

Syukron, A. I. S., Siregar, R. A. B., Sitohang, Y. A. A., & Harliana, P. (2024). Pemanfaatan Algoritma Pewarnaan Graf untuk Efisiensi Penjadwalan Dosen. AR-RUMMAN: Journal of Education and Learning Evaluation. Vol. 1(2), 650–654. https://doi.org/10.57235/arrumman.v1i2.4287

Yusak, M. Y., Putri, D. F., & Syaripuddin, S. (2024). Penerapan Pewarnaan Graf Menggunakan Algoritma Welch-Powell pada Penjadwalan Mata Pelajaran. Journal of Mathematics Education and Science. Vol. 7(2), 177–183. https://doi.org/10.32665/james.v7i2.2272




DOI: https://doi.org/10.20527/epsilon.v19i2.16712

Refbacks

  • There are currently no refbacks.


Copyright (c) 2025 EPSILON: JURNAL MATEMATIKA MURNI DAN TERAPAN (EPSILON: JOURNAL OF PURE AND APPLIED MATHEMATICS)

Indexed by: 

      

 

EDITORIAL OFFICE 

           

 

 

 

Creative Commons License
All articles published in "Epsilon: Jurnal Matematika Murni dan Terapan" are licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0). Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.