04 Pewarnaan Graf PDF [PDF]

Citation preview

Pewarnaan Graf Sistem Informasi Universitas Gunadarma 2012/2013







 



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.



Pewarnaan Graf



Algoritma yang digunakan untuk mendapatkan bilangan kromatis dari suatu graf adalah Algoritma Welch-Powell, langkah-langkahnya adalah : 1. Urutkan simpul-simpul berdasarkan derajatnya, dari besar ke kecil. 2. Warnai. 



Pewarnaan Graf



Pewarnaan region dapat dilakukan dengan cara membuat dual dari map.  Pewarnaan daerah dilakukan dengan terlebih dahulu membentuk graph tersebut menjadi graph planar kemudian melakukan pewarnaan untuk tiap daerah yang berbeda pada daerah yang berdekatan. Jumlah warna diambil yang paling minimum.  Pewarnaan rusuk adalah mewarnai rusukrusuk suatu graph, sedemikian hingga rusukrusuk yang insiden warna berlainan dan banyak warna minimum. 



Pewarnaan Region



Masalah Pewarnaan graph (graph coloring) adalah masalah pemberian warna pada setiap daerah dari graph, dengan daerah yang berdampingan tidak boleh diberi warna yang sama  Penggunaan warna minimal 



Masalah Pewarnaan Graf



Definisi:  Pewarnaan sebuah graph sederhana adalah pewarnaan setiap verteks pada graph demikian sehingga tidak ada dua verteks yang terhubung memiliki warna yang sama Bilangan Kromatik  Adalah jumlah warna minimal yang dibutuhkan untuk mewarnai sebuah graph



Masalah Pewarnaan Graf



Hijau



Coklat Hijau



Kuning Coklat



Merah Kuning



Hijau Coklat



Masalah Pewarnaan Graf







Berapa banyak jadual UAS dapat dibuat agar setiap mahasiswa dapat mengikuti UAS tanpa pernah ada jadual yang 1 bentrok 7



2



6



3



5



4



Contoh Soal



TERIMA KASIH