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

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.