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.
