8/15/2019 04 Pewarnaan Graf.pdf

1/9

Pewarnaan Graf Sistem Informasi

Universitas Gunadarma2012/2013

8/15/2019 04 Pewarnaan Graf.pdf

2/9

Pewarnaan Graf 

 Pewarnaan graf adalah pemberian warnaterhadap simpul-simpul graf dimana 2

buah simpul yang berdampingan tidakboleh 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.

8/15/2019 04 Pewarnaan Graf.pdf

3/9

Pewarnaan Graf 

 Algoritma yang digunakan untukmendapatkan bilangan kromatis dari

suatu graf adalah Algoritma Welch-Powell,langkah-langkahnya adalah :

1.  Urutkan simpul-simpul berdasarkan

derajatnya, dari besar ke kecil.2.  Warnai.

8/15/2019 04 Pewarnaan Graf.pdf

4/9

Pewarnaan Region

 Pewarnaan region dapat dilakukan dengancara membuat dual dari map.

 Pewarnaan daerah dilakukan dengan terlebihdahulu membentuk graph tersebut menjadigraph planar kemudian melakukanpewarnaan untuk tiap daerah yang berbedapada daerah yang berdekatan. Jumlah warnadiambil yang paling minimum.

 Pewarnaan rusuk adalah mewarnai rusuk-rusuk suatu graph, sedemikian hingga rusuk-rusuk yang insiden warna berlainan dan

banyak warna minimum.

8/15/2019 04 Pewarnaan Graf.pdf

5/9

Masalah Pewarnaan Graf 

 Masalah Pewarnaangraph (graphcoloring) adalahmasalah pemberianwarna pada setiapdaerah dari graph,dengan daerahyang berdampingantidak boleh diberiwarna yang sama

 Penggunaan warnaminimal

8/15/2019 04 Pewarnaan Graf.pdf

6/9

Masalah Pewarnaan Graf 

Definisi:

 Pewarnaan sebuah graph sederhana

adalah pewarnaan setiap verteks padagraph demikian sehingga tidak ada duaverteks yang terhubung memiliki warna

yang samaBilangan Kromatik

 Adalah jumlah warna minimal yangdibutuhkan untuk mewarnai sebuah graph

8/15/2019 04 Pewarnaan Graf.pdf

7/9

Masalah Pewarnaan Graf 

Hijau Coklat

Hijau

Kuning

Coklat

Hijau

Merah

Kuning

Coklat

8/15/2019 04 Pewarnaan Graf.pdf

8/9

Contoh Soal

 Berapa banyak jadual UAS dapat dibuatagar setiap mahasiswa dapat mengikuti

UAS tanpa pernah ada jadual yangbentrok

2

1

3

5

6

7

4

8/15/2019 04 Pewarnaan Graf.pdf

9/9