APLIKASI PEWARNAAN GRAF PADA PENJADWALAN MATA KULIAH MENGGUNAKAN ALGORITMA WELCH-POWELL

Penjadwalan mata kuliah merupakan suatu kegiatan rutin yang dilakukan oleh setiap kampus sebelum dimulainya tahun ajaran baru, maka disusunlah jadwal mata kuliah sedemikian rupa, sehingga tidak ada jadwal yang sama atau bentrok dan tidak ada dosen yang mengajar di jam dan kelas yang sama. Penyusunan jadwal mata kuliah semester ganjil tahun ajaran 2024/2025 di Prodi Matematika Universitas Dharma Andalas (UNIDHA) merupakan salah satu persoalan yang ada pada pewarnaan graf, persoalan ini akan diselesaikan menggunakan algoritma Welch-Powell. Penyusunan ini dilakukan dengan merepresentasikan data ke dalam bentuk graf, sehingga diperoleh simpul-simpul yang bertetangga. Selanjutnya, menerapkan algoritma Welch-Powell pada pewarnaan simpul graf untuk memperoleh bilangan kromatik, yang artinya simpul-simpul dengan warna yang sama dapat dijadwalkan bersamaan, sehingga untuk susunan jadwal mata pelajaran dapat dijadwalkan pada hari dan kelas yang sama.

Kata kunci : Graf, Pewarnaan Graf, Simpul, Penjadwalan Mata Kuliah, Algoritma Welch-Powell, Bilangan Kromatik