Aplikasi Teori Graf Dalam Menyusun Jadwal Perkuliahan Tadris Matematika Universitas Al Falah Assunniyah Menggunakan Algoritma Welch-Powell
Keywords:
Teori graf, pewarnaan graf, algoritma Welch-Powell, penjadwalan mata kuliahAbstract
Dalam paper ini, dibahas tentang penerapan algoritma Welch-Powell dalam proses penyusunan jadwal mata kuliah di Program Studi Tadris Matematika, Universitas Al Falah Assunniyah. Teori graf memiliki banyak terapan dalam kehidupan sehari-hari seperti penentuan frekuensi radio, kriptografi, penentuan rute terpendek, penentuan jadwal, dan lain-lain. Salah satu topik graf yaitu pewarnaan graf yang merupakan pelabelan graf dengan memberikan warna pada elemen graf. Pewarnaan graf dibedakan menjadi pewarnaan titik, pewarnaan sisi, dan pewarnaan daerah. Pewarnaan titik adalah memberi warna pada titik graf sedemikian sehingga titik yang bertatangga memiliki warna yang berbeda. Dalam konsep pewarnaan titik berfokus mencari minimal warna yang dapat digunakan yang disebut bilangan kromatik. Algoritma Welch-Powell merupakan salah satu algoritma pewarnaan titik yang berdasarkan pada derajat tertinggi titik. Pewarnaan titik graf dapat diaplikasikan dalam proses penyusunan jadwal kuliah yang merupakan suatu hal yang sangat kompleks dan sering terjadi bentrok dalam proses penyusunannya. Metode penelitian yang digunakan adalah metode deduktif aksiomatik dengan mengkaji teorema, lemma, atau definisi sebelumnya yang kemudian diterapkan pada representasi graf dari penjadwalan mata kuliah di Program Studi Tadris Matematika, Universitas Al Falah Assunniyah. Berdasarkan penelitian yang dilakukan, diperoleh bahwa terdapat 12 kelompok mata kuliah yang dapat dilaksanakan dalam waktu bersamaan di Program Studi Tadris Matematika, Universitas Al Falah Assunniyah.
References
Apriyanto, A. (2018). Pewarnaan Graph Berbasis Algoritma Welch Powell Dalam Pengaturan Jadwal
Praktikum. Proximal: Jurnal Penelitian Matematika dan Pendidikan Matematika, 1(2), 11-21.
https://e-journal.my.id/proximal/article/view/193/155
Augusty, F. R., Riti, Y. F., & Herawan, S. T. (2023). Penerapan Algoritma Welch-Powell Dalam Pewarnaan
Graf Menentukan Menu Makan Siang Karyawan. Digital Transformation Technology, 3(1), 58-
https://doi.org/10.47709/digitech.v3i1.2427
Brooks, R. L. (1941, April). On colouring the nodes of a network. In Mathematical Proceedings of the
Cambridge Philosophical Society (Vol. 37, No. 2, pp. 194-197). Cambridge University Press.
https://doi.org/10.1017/S030500410002168X
Chartrand, G., & Zhang, P. (2019). Chromatic graph theory. Boca Raton : Chapman and Hall/CRC.
Christofides, N. (1971). An algorithm for the chromatic number of a graph. The computer journal, 14(1),
-39. https://doi.org/10.1093/comjnl/14.1.38
Hasanah, L. G., Sripatmi, S., & Amrullah, A. (2022). Penerapan Konsep Pewarnaan Graf Dalam
Penyusunan Jadwal Kegiatan Belajar Mengajar Di SMKN. Griya Journal of Mathematics
Education and Application, 2(2), 504-516. https://doi.org/10.29303/griya.v2i2.177
Komarullah, H. (2023, December). Nilai Minimum Span pada Graf Gurita, Graf Siput, dan Graf UburUbur. In Prossiding Galuh Mathematics National Conference (Vol. 3, No. 1, pp. 56-62).
https://jurnal.unigal.ac.id/GAMMA-NC/article/view/12952/6999
Liowardani, A. P., Dafik, D., & Fatahillah, A. (2018). Keterampilan Berpikir Kreatif pada Pewarnaan Titik
R-Dinamis Graf Hasil Operasi Edge Corona Graf Lintasan. Kadikma, 9(3), 31-41.
https://doi.org/10.19184/kdma.v9i3.10748
Mahmudah, M., & Irawati, T. N. (2018). Aplikasi Pewarnaan Graf Terhadap Pembuatan Jadwal Ujian
Semester di Jurusan Pendidikan Matematika Universitas Islam Jember. Mathematics, 1, 1-10.
https://doi.org/10.19184/kdma.v9i2.8530
Maulani, A., & Wulandari, D. (2023). Implementasi Pewarnaan Graf Pada Pengelompokan Siswa/i
Rumah Belajar Azalea Dengan Algoritma Welch-Powell. Jurnal Siger Matematika, 37-42.
https://doi.org/10.23960/jsm.v4i2.11829
Puspasari, D. T., Dafik, D., & Slamin, S. (2014). Pewarnaan Titik pada Graf Khusus: Operasi dan
Aplikasinya. In Prosiding Seminar Matematika dan Pendidikan Matematika (pp. 50-58).
https://jurnal.unej.ac.id/index.php/psmp/article/view/907/711
Rahadi, A. P. (2019). Penjadwalan Mata Kuliah Menggunakan Pewarnaan Graf Dengan Algoritma
Largest First. Jurnal Padegogik, 2(1), 1-13. https://doi.org/10.35974/jpd.v2i1.1067
Sari, R. F., Fibri., & Lela, N. (2023). Implementasi pewarnaan graf menggunakan metode algoritma tabu
search pada penjadwalan kerja perawat. G-Tech: Jurnal Teknologi Terapan, 7(1), 298-304.
https://doi.org/10.33379/gtech.v7i1.2021
Sunarni, T., Bendi, R., & Alfian, A. (2018). Penerapan Teknik Pewarnaan Simpul Graf pada Permasalahan
Penjadwalan Kuliah. Prosiding Ritektra, 8(1), 84-91.
https://core.ac.uk/download/pdf/161705785.pdf
Yusuf, R., Dewi, F. P., & Mujib, A. (2022). Generalisasi Bilangan Kromatik Pada Beberapa Kelas Graf
Korona. Jurnal Derivat: Jurnal Matematika dan Pendidikan Matematika, 9(2), 192-201.
Downloads
Published
Issue
Section
License

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