Page 80 - Modul Graf fix kali ya allaah

J. Pewarnaan Graf (Graph Colouring)

Pewarnaan graf adalah pemberian warna pada graf.

Terdapat 3 jenis perwarnaan graf,yaitu:

1) Pewarnaan simpul

2) Pewarnaan jalur

3) Pewarnaan wilayah

Dalam modul ini, kita hanya membahas pewarnaan simpul

saja.

Dalam memberi warna pada simpul, tentu saja yang paling

mudah adalah dengan memberi warna-warna berbeda untuk

setiap simpul-simpulnya. Artinya, dengan cara ini, kita akan

menggunakan warna yakni sebanyak n, n adalah banyak

simpul pada graf.

Namun, persoalannya adalah kita membutuhkan banyak

warna yang paling minimum yang kita gunakan untuk

memberi warna simpul-simpul graf. Dengan catatan bahwa

simpul yang bertetangga tidak memiliki warna yang sama.

Penggunaan warna yang paling minimum yang digunakan

untuk mewarnai simpul-simpul pada graf ini akan membuat

P a g e 77 | 88