PEWARNAAN GRAF
Pewarnaan graf adalah
kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan
warna pada titik-titik pada batas tertentu. Ada tiga macam pewarnaan graf,
yaitu :
1.
Pewarnaan titik atau simpul
2.
Pewarnaan sisi
3.
Pewarnaan wilayah (region)
Nah sekarang kita akan
bahas satu persatu tentang pewrnaan tersubut,
A. Pewarnaan Titik atau 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. Kita dapat memberikan sembarang warna pada
simpul-simpul asalkan
berbeda dengan simpul-simpul tetangganya.
Sebuah pewarnaan yang menggunakan
beberapa n buah warna biasanya disebut dengan n-coloring.
Jumlah warna minimum yang dapat
digunakan untuk mewarnai titik pada
suatu graph G disebut bilangan
kromatik graph G, yang dilambangkan dengan χ(G).
Suatu graph yang mempunyai bilangan
kromatis k dilambangkan dengan χ(G) = k.
Graph
G pada contoh di atas mempunyai bilangan kromatik = 3 atau χ(G)
= 3.
B. Pewarnaan
Sisi
Pewarnaan sebuah sisi graf, pewarnaan
sisi-sisinya secara tepat berarti cara pemberian warna pada garis sedemikian
rupa sehingga setiap garis yang bertumpuan pada titik yang sama diberi warna
yang berbeda. Pewarnaan sisi dengan warna-warna (sebut saja dengan variabel k)
dinamakan sebagai pewarnaan sisi k. Angka terkecil dari warna- warna yang
dibutuhkan untuk pewarnaan sisi graf G disebut sebagai indeks kromatik atau
angka kromatik sisi, χ’(G).
Contoh :
Gambar : pewarnaan sisi pada graf.
C. Pewarnaan
Wilayah
Pewarnaan wilayah adalah pemberian warna
pada setiap wilayah pada graf sehingga tidak ada wilayah bersebelahan
yang memiliki warna yang sama. Pewarnaan wilayah ini diterapkan pada
pewarnaan peta. Pada pewarnaan peta, diberikan warna yang berbeda
pada setiap propinsi yang saling bersebelahan. Dalam mengerjakan
pewarnaan wilayah, kita dapat menggunakan prinsip pewarnaan simpul
pada graf. Misalnya adalah masalah pewarnaan peta. Tiap wilayah pada peta
dinyatakan sebagai simpul graf. Sedangkan sisi menyatakan bahwa terdapat dua wilayah
yang berbatasan langsung (disebut juga bertetangga). Oleh karena itu, graf yang
terbentuk merupakan graf planar. Graf planar ialah graf yang dapat digambarkan
pada bidang datar sedemikian sehingga tidak ada sisi-sisinya yang saling berpotongan
. Bilangan kromatik pada graf planar tidak lebih dari empat. Sehingga dalam
pewarnaan sebuah peta, cukup hanya menggunkan empat warna saja. Warna yang
digunakan dalam pewarnaan peta adalah hijau, kuning, merah, dan biru.
Gambar : Peta
merupakan contoh pewarnaan wilayah pada graf
TEOREMA – TEOREMA PEWARNAAN GRAF
1. Jika
ada sebuah pewarnaan – k pada graph G, maka χ (G) ≤ k
Bukti
:
·
Jika ada pewarnaan – k pada graph G
berarti semua titik pada graph G dapat diwarnai dengan menggunakan k warna.
·
Karena bilangan kromatik merupakan
minimum banyaknya warna yang digunakan untuk mewarnai semua titik pada graph G,
sedemikian sehingga syarat pewarnaan terpenuhi. Maka χ (G) ≤ k
Contoh :
dengan
demikian χ (G) = 2 berarti χ (G) ≤ k.
1 2. Jika H sebuah graph bagian dari
graph G, maka χ
(H) ≤ χ
(G) Bukti :
·
Misalkan H sebuah graph bagian dari
graph G. Berarti V(H) bagian dariV(G) dan E(H) bagian dari E(G)
·
Karena setiap pewarnaan titik H dapat
diperluas ke sebuah pewarnaan titik di G, maka χ (H) ≤ χ (G)
diperoleh χ (G) = 3 dan χ (H) = 2 berarti χ (H) ≤ χ (G)
3.
Jika
graph G adalah graph kosong, maka χ (G) = 1
Bukti
:
Karena graph kosong
hanya terdiri dari titik – titik dan tidak ada sisi yang menghubungkan dua
titik, berarti setiap titik boleh mempunyai warna yang sama.
contoh :
graph G dengan χ (G) = 1
