TEKNIK PEWARNAAN GRAF PADA PENJADWALAN PIKET OSIS DENGAN ALGORITMA WELCH-POWELL PADA SMP 01 ISLAM JEMBER

Abstract

Teori graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antar objek tersebut. Representasi visual dari sebuah graf adalah dengan menyatakan objek dengan sebuah titik, sedangkan hubungan antar objek dinyatakan dengan garis. Dalam kehidupan sehari-hari penggunaan teori graf salah satunya menentukan penjadwalan menggunakan pewarnaan graf. Pewarnaan yang dimaskud adalah pewarnaan simpul. Hal tersebut dipadukan dengan Algoritma Welch-Powell. Algoritma Welch-Powell dapat digunakan untuk menentukan sebuah penjadwalan berdasarkan derajat tertinggi dari simpul-simpulnya. Keunggulan algoritma tersebut dapat menyelesaikan secara efisien, tidak terjadi kesamaan jadwal antar siswa pada satu kelas yang sama. Cara penentuannya dengan melihat jumlah derajat dari sebuah simpul yang terbesar sebagai pewarnaan pertama.