Pewarnaan Graf dan Algoritma Welch-Powell dalam Penyusunan Jadwal Perkuliahan di FMIPA Matematika Universitas Jember

Abstract

Pewarnaan graf adalah teknik yang berguna untuk memodelkan banyak situasi pada dunia nyata yang melibatkan benturan kepentingan. Pewarnaan graf mempunyai penerapan yang cukup luas, diantaranya adalah penjadwalan perkuliahan di program studi matematika Universitas Jember. Prodi matematika memiliki beberapa tingkatan semester mulai dari semester satu hingga semester delapan, yang terdiri dari 4 angkatan yaitu angkatan 2019 hingga 2022. Penelitian ini membahas tentang pewarnaan graf dan algoritma WelchPowell dalam penyusunan jadwal perkuliahan di FMIPA matematika Universitas Jember. Algoritma Welch-Powell merupakan algoritma yang tergolong dalam algoritma Greedy. Algoritma Greedy yaitu algoritma yang pada setiap langkah penyelesaian terdapat banyak pilihan solusi yang perlu dieksplorasi. Langkahlangkah pada penelitian ini yaitu membentuk tabel matriks yang berisikan hasil relasi antara mata kuliah dan dosen, mengubah data dalam tabel matriks ke dalam bentuk graf, membentuk tabel derajat simpul kemudian mengurutkannya dari derajat tertinggi hingga terendah. Selanjutnya mewarnai graf dimulai dari simpul dengan derajat tertinggi hingga menghasilkan bilangan kromatik, menyusun jadwal kuliah berdasarkan hasil coloring dan memperhatikan setiap batasanbatasan yang berlaku. Berdasarkan penelitian yang telah dilakukan terbukti bahwa pewarnaan pada graf menggunakan algoritma Welch-Powell efektif dalam penyusunan jadwal kuliah di FMIPA Matematika Universitas Jember.