Implementasi Algoritma Sequential dan Welch Powell pada pewarnaan graf (studi kasus pewarnaan peta kota Makassar)
Abstract
The aim of this research is how to implement Sequential algorithm and Welch Powell algorithm on graph coloring, especially on Makassar city map coloring. The research method used was a case study aimed at searching information in the form of a map of Makassar city. The first step is to take a colored map of Makassar city at the Dinas tata ruang kota makassar, then redraw it with the help of Corel Draw X7 software, so there are no colors. The next step is to represent the map in graph form by taking the region (sub-district) as a node and then doing graph coloring using Sequential algorithm and Welch Powell algorithm. The results of coloring the Makassar city map using Sequential algorithm and Welch Powell algorithm, both produce chromatic numbers χ (G) = 4 or the number of colors produced to color a graph there are 4 colors. The colors used are red, yellow, green and blue. Then from the results of coloring this graph can easily be applied to color the map of the city of Makassar based on the coloring requirements obtained. Because it has the same chromatic numbers, it can be concluded that the Sequential algorithm is no better than the Welch Powell algorithm, or vice versa the Welch Powell algorithm is no better than the Sequential algorithm for the case of coloring the Makassar city map. The previous Makassar city map coloring or without the algorithm, produces chromatic numbers χ (G) = 12 or the number of colors produced to color a graph there are 12 colors. So that the two algorithms are much better at coloring than the previous Makassar city map coloring or without the algorithm
References
[2] W. Kocay and D. L. Kreher, Graphs, algorithms, and optimization. 2017.
[3] Assma Laputty, “Penggunaan Metode Greedy Pada Pengaturan Lampu Lalu Lintas Jalan Di Perempatan Al-Fatah Ambon Dengan Teori Graph,” J. Pros. Konfrensi Nas. Ilmu Komput. (KONIK, Vol. 2, pp. 147–151, 2014.
[4] R. Munir, Matematika Disktrit. Bandung: Informatika Bandung, 2010.
[5] A. Kosowski and K. Manuszewski, “Classical coloring of graphs,” pp. 1–19, 2004.
[6] K. P. Sari, “Perbandingan Algoritma Pewarnaan LDO , SDO , dan IDO pada Graf Sederhana.”
[7] F. Ardiansyah and M. Syaifullah, “Implementasi Algoritma Greedy Untuk Melakukan Graph Coloring: Studi Kasus Peta Propinsi Jawa Timur,” J. Inform., 2012.
[8] A. M. Soimah and N. S. M. Mussafi, “Pewarnaan Simpul Dengan Algoritma Welch-Powell Pada Traffic Light Di Yogyakarta,” J. Fourier, vol. 2, no. 2, p. 73, 2013.
[9] Binti Ida Umaya, “Implementasi Algoritma Tabu Search Dalam Pewarnaan Simpul Graf (STUDI KASUS : Penjadwalan mata kuliah jurusan matematika fakultas sains dan teknologi UIN Alauddin Makassar),” Univ. Nusant. PGRI Kediri, vol. 1, pp. 1–7, 2017.
[10] H. Turosdiah, Armiati, and M. P. Dewi, “Penerapan Pewarnaan Titik pada Graf dalam Penyusunan Lokasi Duduk Menggunakan Algoritma Greedy Berbantuan Microsoft Visual Basic 6.0,” UNP J. Math., vol. 2, no. 1, 2014.
[11] N. Selma Karamy, “Pewarnaan Titik Pada Graf Dengan Menggunakan Algoritma Pewarnaan Barisan Sederhana Dalam Penataan Buku Perpustakaan,” in Conference on Research & Community Services, 2019, pp. 557–565.
[12] T. S. N. Anggraini, Lana Aristya, Rosyida, Isnaini ,Asih, “Penyelesaian Masalah Pewarnaan Graf Dengan Algoritma Genetika,” vol. 8, no. 1, pp. 30–39, 2019.
[13] R. J. Noor, H. Hendra, and W. Powell, “Implementasi Algoritma Baris dalam Pewarnaan Titik pada Graf Sederhana Implementation of Sequent Algorithm in Coloring Vertex on Simple Graph,” vol. 1, no. 1, pp. 19–22, 2013.
[14] P. Studi and T. Informatika, “Perbandingan Algoritma,” no. 13512025, pp. 1–13, 2014.
[15] M. Ammar, “Penyusunan Jadwal Ujian Mata Kuliah Semester V Jurusan Matematika Uin Alauddin Makassar,” pp. 299–303.
