Penerapan Algoritma Welch Powell untuk Melakukan Graph Colouring pada Peta Kabupaten Serdang Bedagai

Abstract

Terapan ilmu matematika banyak digunakan untuk menyelesaikan masalah dalam kehidupan sehari-hari. Teori graf merupakan salah satu pokok bahasan matematika diskrit yang telah lama dikenal dan banyak diterapkan pada berbagai bidang dalam kehidupan sehari-hari, misalnya pada penyusunan jadwal mata kuliah. Contoh tersebut merupakan penerapan pewarnaan graf. Selain contoh tersebut terapan penting pewarnaan graf adalah mewarnai peta (colouring of map). Pewarnaan peta dengan menggunakan Algoritma Welch Powell dilakukan untuk mendapatkan warna minimum. Tujuan dalam penelitian ini adalah untuk mengetahui cara menentukan bilangan kromatik dan menentukan jumlah bilangan kromatik (warna minimum) peta kabupaten Serdang Bedagai berbasis kecamatan berdasarkan Algoritma Welch Powell. Hasil penelitian didapat ada 17 kecamatan pada kabupaten Serdang Bedagai. Dengan menggunakan Algoritma Welch Powell ada empat tahap yang dilakukan untuk mewarnai 17 kecamatan kabupaten Serdang Bedagai. Tahap pertama ada lima simpul kecamatan yang diberi warna sama yaitu warna merah. Tahap kedua ada lima simpul kecamatan yang diberi warna sama yaitu warna orange. Tahap ketiga ada empat simpul kecamatan yang diberi warna sama yaitu warna hijau. Tahap keempat ada tiga simpul kecamatan yang diberi warna sama yaitu warna biru. maka untuk 17 kecamatan cukup menggunakan empat warna saja dan tidak ada simpul kecamatan yang bertetangga memiliki warna yang sama. Jadi, ada empat jumlah bilangan kromatik atau  (G)=4 pada graf peta kabupaten Serdang Bedagai dengan menggunakan Algoritma Welch Powell.