# PENERAPAN KONSEP PEWARNAAN GRAF DALAM PENJADWALAN PEMBELAJARAN DI SMAN 1 KOPANG

## Authors

• Reksa Haniantara Universitas Mataram
• Amrullah Pendidikan Matematika FKIP Universitas Mataram
• Ulfa Lu’luilmaknun Pendidikan Matematika FKIP Universitas Mataram
• Nani Kurniati Pendidikan Matematika FKIP Universitas Mataram

## Keywords:

Learning Scheduling, Graph Theory, Wellch Powell Algorithm, VBA Excel

## Abstract

Scheduling is a way to determine the time and place an activity will be carried out. A learning schedule that is free from overlapping scheduling problems needs to be available before teaching and learning activities begin so that the early teaching and learning activities can take place effectively. One way that can be used to overcome the problem of overlapping learning scheduling is to use the concept of graph coloring contained in the topic of graph theory. Therefore, the goal to be achieved in this study is to obtain a schedule of teaching and learning activities that are free from overlapping scheduling at SMAN 1 Kopang by applying the concept of graph coloring. The type of research used is applied research. Based on the scheduling data, we get a neighboring matrix with a size of 224×224 and a chromatic number of 22. The determination of neighboring matrices using the help of the Excel VBA programming language. The schedule-making begins by creating a scheduling conflict graph based on the lesson schedule data, then the graph obtained will be colored using Welch Powell's algorithm. After the coloring results are obtained, a learning schedule can be arranged based on the coloring results. Subjects of the same color can be scheduled at the same time and vice versa. The lesson schedule produced in this study requires six additional time slots so that the lesson schedule is free from scheduling overlap because the chromatic number obtained in graph coloring is greater than the available time slots at SMAN 1 Kopang.

## References

Abubakar, R. (2021). Pengantar Metodologi Penelitian. In Antasari Press. https://idr.uin-antasari.ac.id/10670/1/Pengantar Metodologi Penelitian.pdf

Amrullah, A. (2011). Aplikasi Graf Pohon Pada Algoritma Huffman. Jurnal Pijar Mipa, 6(1), 24–27. https://doi.org/10.29303/jpm.v6i1.122

Astuti, S. (2011). Penyusunan Jadwal Ujian Mata Kuliah dengan Algoritma Pewarnaan Graf Welch Powell. In Jurnal Dian (Vol. 11, Issue 1, pp. 68–74). publikasi.dinus.ac.id

Daswa, & Riyadi, M. (2017). Aplikasi Pewarnaan Graf Pada Masalah Penyusunan Jadwal Perkuliahan Di Universitas Kuningan. JES-MAT (Jurnal Edukasi Dan Sains Matematika), 3(2), 217. https://doi.org/10.25134/jes-mat.v3i2.695

Mahmudah, M., & Irawati, T. N. (2018). Aplikasi Pewarnaan Graf Terhadap Pembuatan Jadwal Ujian Semester Di Jurusan Pendidikan Matematika Universitas Islam Jember. Kadikma, 9(2), 12–21.

Momongga, D., & Nataliani, Y. (2013). Matematika Diskrit (edisi pert). Kencana Prenada Media Group.

Niarma, Pramono, B., & Tajidun, L. (2018). Aplikasi penjadwalan menggunakan algoritma welch powell (studi kasus : sma muhammadiyah kendari). SemanTIK, 4(1), 1–6.

Susilo Putro, A., Rochmad, & Alamsyah. (2012). Penerapan Pewarnaan Graf Pada Penjadwalan Ujian Menggunakan Algoritma Welsh Powel. UNNES Journal of Mathematics, 1(2), 1110–1115.

Wibisono, S. (2019). Matematika Diskrit Edisi 2 (A. Rizky Rachmawati (ed.); 2nd ed.).Graha Ilmu. https://ine2011042063.files.wordpress.com/2014/11/e-book-matematika-diskrit.pdf