Penerapan Pewarnaan Graf Pada Penjadwalan Mata Kuliah Program Studi Matematika UIN Imam Bonjol Padang

Novita Hasanah, Raudhatul Jannah, Mohamad Syafii, Lilis Harianti Hasibuan

Abstract


A graph is a discrete structure consisting of vertices and edges connecting these vertices. One of the discussions in graph theory is graph coloring. In this research, graph coloring will be applied in making the schedule for the Mathematics study program at UIN Imam Bonjol Padang by assuming the subject as a vertice and the lecturer as an edge. One of the benefits of applying graph coloring in scheduling makes scheduling arrangements easier. The graph coloring algorithm use the Welsh Powell Algorithm. Based on the application of graph coloring with the Welsh Powell Algorithm obtained the lecturer's teaching schedule according to the SKS, time and classroom given.

Keywords


graph, coloring graph, Welsh Powell, class schedule

Full Text:

PDF


DOI: https://doi.org/10.15548/jostech.v2i2.4349
Abstract views : 531 times
PDF : 323 times

References


S. Gunawan, “Perancangan Aplikasi Penjadwalan Mata Kuliah Menggunakan Metode Constraint Programming,” Jurnal Petir, vol. 9, no. 1, pp. 38–41, 2016.

S. Astuti, “Penyusunan Jadwal Ujian Mata Kuliah dengan Algoritma Pewarnaan Graf Welch Powell,” Jurnal Dian, vol. 11, no. 1, pp. 68–74, 2011.

M. Syafii, D. M. Putri, and A. Rahman, “Nullitas maksimum matriks hermitian digambarkan oleh graf g,” MAp (Mathematics and Applications) Journal, vol. 3, no. I, pp. 53–61, 2021, doi: https://doi.org/10.15548/map.v3i1.2784.

M. Sam and Yuliani, “Penerapan Algoritma Prim Untuk Membangun Pohon Merentang Minimum (Minimum Spanning Tree) Dalam Pengoptimalan Jaringan Transmisi Nasional Provinsi Sulawesi Selatan,” Jurnal Dinamika, vol. 7, no. 1, pp. 50–61, 2016, [Online]. Available: www.djlpe.go.id

S. E. Irwan, “Aplikasi Pewarnaan Graf pada Penempatan Kamar Mahasiswa (Studi Kasus: Asrama Institut Teknologi Sumatera),” Sainmatika: Jurnal Ilmiah Matematika dan Ilmu Pengetahuan Alam, vol. 17, no. 1, p. 17, Apr. 2020, doi: 10.31851/sainmatika.v17i1.3137.

R. Munir, Matematika Diskrit, Edisi 3. Bandung: Informatika Bandung, 2010.

A. P. Rahadi, “Graf Dengan Algoritma Largest First,” Jurnal Padegogik, vol. 2, pp. 1–13, 2019.

O. I. R. Farisi, S. Maysyaroh, and E. F. Dewi, “Penerapan Pewarnaan Graf pada Penjadwalan Mengajar Dosen Pendidikan Matematika Universitas Nurul Jadid,” Jurnal Matematika, vol. 11, no. 1, p. 10, 2021, doi: 10.24843/jmat.2021.v11.i01.p132.

P. W. Sari, L. Yulianti, and . N., “Penjadwalan Kuliah Dengan Algoritma Welsh-Powell (Studi Kasus: Jurusan Matematika FMIPA UNAND),” Jurnal Matematika UNAND, vol. 6, no. 1, p. 134, 2017, doi: 10.25077/jmu.6.1.134-141.2017.

Pasnur, “Implementasi Algoritma Welch Powell Dalam Pembuatan Jadwal Ujian Akhir Semester,” Inspiration: Jurnal Teknologi Informasi dan Komunikasi, vol. 2, no. 1, pp. 35–44, 2012.

J. L. Gross, J. Yellen, and P. Zhang, Handbook of Graph Theory, Second Edi. New York: CRC Press.

Y. Rusdiana and A. Maulani, “Algoritma Welch-Powell Untuk Pewarnaan Graf pada Penjadwalan Perkuliahan,” Science and Physics Education Journal (SPEJ), vol. 3, no. 1, pp. 37–47, 2019, doi: 10.31539/spej.v3i1.915.

M. Abdy, R. Syam, and T. Tina, “Bilangan Kromatik Pewarnaan Titik pada Graf Dual dari Graf Roda,” Journal of Mathematics Computations and Statistics, vol. 4, no. 2, p. 95, 2021, doi: 10.35580/jmathcos.v4i2.24443.

Apriyanto, “Pewarnaan Graph Berbasis Algoritma Welch Powell dalam Pengaturan Jadwal Praktikum,” Jurnal Penelitian Matematika dan Pendidikan Matematika, vol. 1, no. 2, pp. 11–21, 2018.

D. D. Setyowidi and L. Ratnasari, “Energi Derajat Maksimal pada Graf Terhubung,” Jurnal Matematika, vol. 1, no. 1, pp. 46–55, 2012.


Refbacks

  • There are currently no refbacks.


Copyright (c) 2022 JOSTECH: Journal of Science and Technology

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.