Aplikasi Teori Graf Dalam Menyusun Jadwal Perkuliahan Tadris Matematika Universitas Al Falah Assunniyah Menggunakan Algoritma Welch-Powell

Authors

  • Hafif Komarullah Tadris Matematika, Universitas Al-Falah As-Sunniyah, Kencong-Jember
  • Finka Afdhilatul Jannah Im Tadris Matematika, Universitas Al Falah As Sunniyah
  • Sarifatul Masruroh Tadris Matematika, Universitas Al Falah As Sunniyah

Keywords:

Teori graf, pewarnaan graf, algoritma Welch-Powell, penjadwalan mata kuliah

Abstract

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.

https://doi.org/10.31316/jderivat.v9i2.3780

Published

2025-06-26