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:
Posting Komentar