TEORI GRAF PART 2

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)

contoh :

 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