Download Makalah Pewarnaan Graph

PEWARNAAN GRAPH

1.    Pewarnaan Titik / Simpul

Pewarnaan titik / simpul adalah memberikan warna pada titik – titik pada graph sedemikian sehingga setiap dua titik yang bertetangga (berhubungan langsung) mempunyai warna yang berbeda. Dua titik yang bertetangga (berhubungan langsung) adalah dua titik yang dihubungkan oleh sebuah sisi.

Titk v₁  bertetangga dengan titik v₂ dan v₄ dan tidak bertetangga dengan titik v₃, berarti titik titik v₁ tidak boleh berwarna sama dengan titik v₂ dan v₄ tetapi boleh berwarna sama dengan titik v₃. Dalam pewarnaan graph, kita tidak hanya sekedar mewarnai titik – titik dengan warna yang berbeda dari warna titik yang bertetangga saja, tetapi kita juga menginginkan jumlah macam warna yang digunakan seminimum mungkin. Dan pewarnaan titik di sisi dibatasi pada graph sederhana atau graph yang tidak mempunyai sisi rangkap atau gelung.

Jumlah warna minimum yang dapat  digunakan untuk mewarnai titik pada  suatu graph G disebut bilangan khromatik graph G, yang dilambangkan dengan χ(G). Suatu graph yang mempunyai bilangan kromatis k dilambangkan dengan χ(G) = k. Berarti graph pada gambar 2 di atas mempunyai bilangan khromatik = 3 atau  χ(G) = 3

Graph pada gambar 3(a) memiliki bilangan khromatik 2 karena titik V₁, V₃, dan V₅ dapat diwarnai dengan satu warna (misalkan merah) dan tiga titik lainnya dengan warna kedua (misalkan biru), seperti yang terlihat pada Gambar 3(b). Secara umum, jika suatu sikel memiliki titik yang banyaknya genap, maka sikel itu dapat diwarnai menggunakan dua warna.

Baca Selengkapnya........