PEMANFAATAN PEWARNAAN GRAF MENGGUNAKAN ALGORITMA WELCH-POWELL DALAM MENYUSUN JADWAL RONDA

Abstract

Penyusunan jadwal ronda malam sering kali menghadapi berbagai kendala, seperti ketidaksesuaian waktu antarwarga, relasi sosial tertentu, dan ketimpangan pembagian tugas. Penelitian ini bertujuan untuk mengatasi permasalahan tersebut dengan menerapkan teori graf, khususnya teknik pewarnaan graf menggunakan algoritma Welch-Powell. Penelitian dilakukan di RT 01 RW 02 Dusun Langsatan, Desa Sukamakmur, Kabupaten Jember, dengan melibatkan 32 kepala keluarga yang aktif dalam kegiatan ronda malam. Metode yang digunakan adalah deduktif aksiomatik, dimulai dari pengumpulan data melalui observasi, wawancara, pencatatan data warga, hingga representasi graf dan pewarnaan titik. Titik pada graf merepresentasikan warga, sedangkan sisi menunjukkan konflik penjadwalan. Pewarnaan graf dilakukan dengan algoritma Welch-Powell yang menyusun titik berdasarkan derajat tertinggi. Hasil pewarnaan menunjukkan bahwa dengan 12 warna, seluruh warga dapat dijadwalkan ronda tanpa terjadi konflik penjadwalan. Hal ini menunjukkan bahwa algoritma Welch-Powell mampu menghasilkan jadwal yang adil, efisien, dan sesuai dengan kondisi sosial masyarakat. Penelitian ini membuktikan bahwa konsep matematika diskrit dapat diimplementasikan secara nyata dalam menyelesaikan permasalahan sosial di tingkat lokal.