Pewarnaan Titik Dengan Algoritma Welch-Powel Untuk Penentuan Jadwal Kuliah
Abstract
Graph theory has many applications to help solve problems. One form of application of graph theory is graph coloring in this research, coloring graph points with the help of the Welsh-powel algorithm. Determining the study schedule for a study program takes a lot of time and this is routine work that must be determined by the study program each semester before learning is carried out. The aim of this research is to determine the class schedule for the odd semester of the 2023/2024 academic year for the mathematics education study program at Tamansiswa Padang University. The method used is the deductive method, which begins with collecting literacy related to the problem, followed by collecting lecturer and course data, which is then modeled using a graph. The problem model that has been obtained is applied to coloring with the help of an algorithm, so that a solution is obtained which is the result of the research. The results obtained from coloring the points on the graph which represent courses, lecturers and existing obstacles, obtained ten different colors for the graph points. These ten colors are distributed, namely 3 colors in semester I, 4 colors in semesters 3 and 5. This means, for semester I students, they study for 3 days, semesters III and V study for 4 days. So for all courses in the odd semester it takes 4 days, namely Monday, Tuesday, Wednesday and Thursday.
Keywords: dot coloring, welch-powel algorithm, lecture schedule.
References
[2] M. Mahmudah dan T. N. Irawati, “Aplikasi Pewarnaan Graf Terhadap Pembuatan Jadwal Ujian Semester di Jurusan Pendidikan Matematika Universitas Islam Jember”, Kadikma: Jurnal Matematika dan Pendidikan Matematika, vol. 9, no. 2, Agustus. 2018.
[3] M. Rinaldi, “Matematika Diskrit”, Edoso 3, Bandung. Informatika. 2010.
[4] N. Santi dan Mulyani, “Optimasi Biaya Jalur Tercepat Indarung – Unitas Menggunakan Algoritma Greedy”, Menara Ilmu, vol. XIII, no. 11, pp. 60 – 69, Oktober. 2019.
[5] P. S. Wicaksono dan Kartono, “Analisis Penjadwalan Mata Pelajaran Menggunakan Algoritma Welch-Powel”, Prismatika: Jurnal Pendidikan dan Riset Matematika, vol. 3, no. 1, pp. 1 - 21, 2020.
[6] R. Diestel, “Graph Theory”, 4nd, Springer. 2010.
[7] R. F. Rohmawati, M. I. A. Fathoni, dan Ismanto, “Penerapan Algoritma Welch-Powel Pada Penyusunan Jadwal Perkuliahan diProgram Studi Pendidikan Matematika”, EULER: Jurnal Ilmiah Matematika, Sains dan Teknologi, vol. 10, no. 2, pp. 200 – 210, Desember. 2022.
[8] S. Hizriani, “PENERAPAN ALGORITMA WELCH POWELL UNTUK MELAKUKAN GRAPH COLOURING PADA PETA KABUPATEN SERDANG BEDAGAI”, http://repository.umsu.ac.id/. 2017.
[9] Y. C. Oktaviani dan Y. F. Riti, “Perbandingan Algoritma Welch-Powel dan Algoritma Greedy dalam Optimasi Penjadwalan Ruang Kuliah Semester Genap Fakultas Teknik”, JIMP: Jurnal Informatika Merdeka Pasuruan, vol. 7, no. 3, pp. 87 - 95, Desember. 2022.
[10] Y. V. Ermanto dan Y. F. Riti, “Perbandingan Implementasi Algoritma Welch-Powel Dan Recursive Largest First Dalam Penjadwalan Mata Kuliah”, Jurnal Teknologi Dan Sistem Informasi Bisnis, vol. 4, no. 1, pp. 204 - 212, 2022.
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
