Page 81 - Modul Graf fix kali ya allaah

kita menemukan sebuah nilai tertentu yang disebut dengan

bilangan kromatik.

Jadi, bilangan kromatik adalah bilangan yang menunjukkan

banyak warna minimum yang digunakan untuk mewarnai

simpul graf.

Bilangan kromatik disimbolkan dengan ( ).

Terdapat sebuah algoritma untuk menentukan bilangan

kromatik ini, yakni Algoritma Welch-Powell.

Algoritma Welch-Powell:

1. Urutkan simpul pada G dengan urutan sesuai

derajatnya dari tinggi ke rendah.

2. Gunakan warna pertama untuk mewarnai simpul

pertama dan simpul-simpul lain dalam urutan (dengan

ketentuan: tidak bertetangga dengan simpul pertama)

3. Beri warna kedua untuk simpul yang belum diberi

warna pada urutan tersebut dan setiap simpul lain

yang tidak bertetangga dengan simpul di awal langkah

ini.

4. Ulangi langkah (3) sampai semua simpul diberi warna.

P a g e 78 | 88