PEWARNAAN GRAF

Ada tiga macam pewarnaan graf, yaitu pewarnaan simpul, pewarnaan sisi, dan pewarnaan wilayah (region). Yang akan dibahas adalah pewarnaan simpul Pewarnaan simpul adalah memberi warna pada simpul-simpul suatu graf sedemikian hingga tidak ada dua simpul bertetangga yang mempunyai warna yang sama. Kita dapat memberikan sembarang warna pada simpul-simpul asalkan berbeda dengan simpulsimpul tetangganya.

Dalam pewarnaan graf, kita tidak hanya sekedar mewarnai simpul-simpul dengan warna yang berbeda dengan warna simpul tetangganya saja, namun kita juga menginginkan agar jumlah warna yang digunakan sesedikit mungkin. Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul simpul disebut bilangan kromatik dari graf G, yang dinotasikan dengan χ(G)  . Gambar 1 memperlihatkan sebuah graf, dengan χ(G) = 3

  



Bilangan  kromatik dari G adalah jumlah warna minimum yang diperlukan untuk mewarnai graph G,  dilambangkan dgn χ (G) {  Ï‡ adalah  huruf Yunani chi } Berapa bilangan kromatik dari graph lengkap K6, K10 dan Kn ? Ï‡ (Kn) = n


6.2. Algoritma Welch-Powell
Algoritma Welch-Powell adalah suatu cara yang efisien untuk mewarnai sebuah graf G. namun algoritma ini hanya memberikan batas atas untuk ℵ(G). Jadi algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai G.
Menentukan ℵ(G) sebenarnya sangat sulit kecuali dalam kasus-kasus sederhana seperti pada contoh-contoh yang akan kita bahas dalam bab ini.

Langkah-langkah dalam algoritma Welch-Powell :
1. Urutkan simpul-simpul dari G dalam urutan derajat yang menurun. Urutan ini mungkin tidak unik karena beberapa simpul mungkin mempunyai derajat yang sama.
2. Gunakan satu warna tertentu untuk mewarnai simpul pertama. Secara berurut, setiap simpul dalam daftar yang tidak bertetangga dengan simpul sebelumnya diwarnai dengan warna ini.
3. Ulangi langkah 2 di atas untuk simpul dengan urutan tertinggi yang belum diwarnai.
4. Ulangi langkah 3 di atas sampai semua simpul dalam daftar terwarnai.


Contoh 1 .
Gunakan algoritma Welch-Powell untuk mewarnai graf G yang ditunjukkan pada gambar 2 dan tentukan bilangan kromatiknya.
  
Penyelesaian :
Simpul v1 v4 v5 v6 v2 v3 v7
Derajat 5 4 4 4 3 3 3
Warna a b c c b d a
Jadi, paling tidak ada 4 warna diperlukan untuk mewarnai graf G, sehingga ℵ(G) = 4.

Contoh 2.
Permasalahan sama dengan contoh 1, untuk graf H yang ditunjukkan pada gambar 3.

Penyelesaian :
  

  
Simpul v1 v6 v2 v3 v4 v5
Derajat 4 4 3 3 3 3
Warna a a b b c c
Jadi ℵ(G) = 3


  


Aplikasi pewarnaan graf yaitu mewarnai peta. Peta terdiri atas sejumlah wilayah. Wilayah dapat menyatakan kecamatan, kabupaten, provinsi, atau negara. Peta diwarnai sedemikian sehingga dua wilayah bertetangga mempunyai warna berbeda. Nyatakan wilayah sebagai simpul, dan batas antar dua wilayah bertetangga sebagai sisi. Mewarnai wilayah pada peta berarti mewarnai simpul pada graf yang berkoresponden. Setiap wilayah bertetangga harus mempunyai warna berbeda dan warna setiap simpul harus berbeda.





 


  
Gambar 4  
(a)  Peta
(b)  Peta dan graf yang merepresentasikannya,
(c)  Graf yang merepresentasikan peta,
(d)  Pewarnaan simpul, setiap simpul mempunai warna berbeda,
(e)  Empat warna sudah cukup untuk mewarnai 8 simpul