Penerapan Pewarnaan Graf dalam Menentukan Jumlah Hari Minimum pada Penjadwalan Kunjungan Destinasi Wisata Populer di Sumatera Barat

Abstract

Sumatera Barat memiliki banyak destinasi wisata populer yang tersebar di berbagai wilayah sehingga wisatawan sering mengalami kesulitan dalam menyusun jadwal perjalanan yang efisien. Penelitian ini bertujuan menerapkan metode pewarnaan graf untuk menentukan jumlah hari minimum kunjungan destinasi wisata di Sumatera Barat. Destinasi wisata direpresentasikan sebagai simpul, sedangkan hubungan antar destinasi yang memiliki waktu tempuh lebih dari dua jam direpresentasikan sebagai sisi. Data penelitian terdiri atas 13 destinasi wisata populer di Sumatera Barat. Hasil pewarnaan graf menunjukkan bahwa graf memiliki bilangan kromatik sebesar 4, yang berarti seluruh destinasi wisata dapat dikelompokkan ke dalam empat hari kunjungan. Dengan demikian, metode pewarnaan graf dapat digunakan sebagai alternatif dalam penyusunan jadwal perjalanan wisata yang lebih efektif dan efisien.

Kata Kunci: pewarnaan graf, bilangan kromatik, penjadwalan wisata, teori graf, Sumatera Barat