Pertemuan 4

Pewarnaan pada Graf






Obyektif :


1. Memahami pewarnaan simpul graf


2. Memecahkan permodelan masalah pewarnaan simpul graf




Pewarnaan Graf


Pewarnaan graf adalah pemberian warna terhadap simpul-simpul graf dimana


2 buah simpul yang berdampingan tidak boleh mempunyai warna yang sama. G berwarna n artinya graf tersebut menggunakan n warna.

Bilangan kromatis dari G = K(G) adalah jumlah minimum warna yang dibutuhkan.



Algoritma yang dapat digunakan untuk mendapatkan bilangan kromatis dari sebuah graf adalah Algoritma Welch-Powell.

Adapun langkah-langkahnya adalah :


1. Urutkan simpul-simpul berdasarkan derajatnya. Dari besar ke kecil.


2. Warnai.




Contoh :


               


Langkah 1 :


urutan simpulnya dari besar ke kecil adalah : E, C, G, A, B, D, F, H




Langkah 2 :


mewarnai :


warna Merah : E, A warna Putih : C, D, H warna Biru : G, B, F



Sehingga bilangan kromatis graf di atas adalah 3.






Teorema :


Pernyataan berikut adalah ekivalen : (1) G berwarna 2

(2) G adalah bipartisi


(3) Setiap sirkuit dalam G mempunyai panjang genap




Graf Lengkap  k dengan n simpul membutuhkan n warna


Teorema :


Suatu graf planar G adalah berwarna 5




Pewarnaan Region


Pewarnaan region dapat dilakukan (seperti pemberian warna pada wilayah- wilayah di peta) dengan cara membuat dual dari map tersebut. Gambarkan sebuah simpul baru pada masing-masing region suatu map M, kemudian buat sebuah ruas yang menghubungkan  simpul pada 2 buah region yang berdampingan bila terdapat ruas sebagai batas / persekutuan kedua region tersebut. Buatlah tanpa adanya ruas baru yang berpotongan,  maka akan terbentuk suatu map M*, yang disebut dual dari map M. Setelah Dualnya terbentuk, dapar dilakukan pewarnaan terhadap simpul- simpulnya. Simpul-simpul tersebut mewakili region sebelumnya, sehingga warna yang digunakan untuk suatu simpul berarti warna yang dapat digunakan  untuk pewarnaan region yang diwakilinya.


Teorema :  suatu map M adalah berwarna 5


Setiap graf planar adalah berwarna (simpul) 4


Dibuktikan oleh Apple & Haken (1976) 2000 Graf, jutaan kasus.

Copyright 2010, iLab Universitas Gunadarma

Created with the Freeware Edition of HelpNDoc: Easily create PDF Help documents