Sabtu, 30 Juni 2007

Pewarnaan Graph

Ada tiga macam persoalan pewarnaan graph (graph colouring), yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan wilayah (region). Pembahasan kali ini hanya dibatasi pada pewarnaan simpul saja.

Pewarnaan simpul adalah memberi warna pada simpul-simpul di dalam graph sedemikian sehingga setiap dua simpul bertetanga mempunyai warna yang berbeda. Salah satu terapan penting pewarnaan graph adalah mewarnai peta (colouring of map). Di dalam persoalan pewarnaan graph, tidak hanya sekedar mewarnai simpul-simpul dengan warna berbeda dari warna simpul tetangganya saja, namun juga menginginkan jumlah macam warna yang digunakan sesedikit mungkin.

Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik graph G.

Tidak ada komentar: