Pewarnaan Graf Jumi [PDF]

Citation preview

PEWARNAAN GRAF A. Pewarnaan Titik Misalkan G graf tanpa loop. Suatu pewarnaan-k (k-colouring) untuk graf G adalah suatu penggunaan sebagian atau semua k warna untuk mewarnai semua titik di G sehingga setiap pasang titik yang bertetangga (adjacent) diberi warna yang berbeda. Jika G mempunyai pewarnaan-k, maka dikatakan titik-titik di G dapat diwarnai dengan k warna (k-colourable). Biasanya warna-warna yang digunakan untuk mewarnai titik-titik suatu graf dinotasikan dengan dengan huruf Yunani. Sebagai contoh dapat dilihat pada gambar berikut.



Bilangan khromatik (chromatic number) dari graf G, dinotasikan χ(G), adalah bilangan k terkecil sehingga G dapat diwarnai dengan k warna. Jadi, χ(G) = min{k/ ada pewarnaan-k pada G}. Jelas bahwa χ(G) ≤ |V(G)|. Sedangkan cara yang mudah untuk menentukan batas bawah dari χ(G) adalah dengan mencari graf bagian lengkap yang terbesar di G. Misalkan dipunyai graf G, H, dan K berikut.



K







Untuk graf G, karena |V(G)| = 3, maka χ(G) ≤ 3. Pada graf G memuat graf lengkap k 3 , maka χ(G) ≥ 3. Akibatnya χ(G) = 3.







Untuk graf H, karena |V(H)| = 4, maka χ(H) ≤ 4. Pada graf H memuat graf lengkap k 4 , maka χ(H) ≥ 4. Akibatnya χ(H) = 4.







Untuk graf J, karena |V(J)| = 5, maka χ(J) ≤ 5. Tetapi, J dapat diwarnai dengan 3 warna, maka χ(J) ≤ 3. Karena graf J memuat graf lengkap k 3 , maka χ(J) ≥ 3. Akibatnya χ(J) = 3.



Teorema 7 Jika G graf sederhana dengan derajat titik maksimum ∆(G ), maka χ(G) ≤ ∆(G) + 1.



Teorema 8 (Teorema Brooks) Misalkan G graf sederhana, terhubung, dan derajat titik maksimum adalah ∆(G). Jika G bukan graf komplit dan bukan graf sikel dengan banyak titik ganjil, maka χ(G) ≤ ∆(G).



Pada pewarnaan titik, ada beberapa algoritma untuk melakukan pewarnaan dengan banyak warna yang minimum pada sebuah graf. Salah satu algoritma untuk pewarnaan titik tersebut adalah algoritma Welch-Powell. Berikut langkah-langkah pewarnaan titik pada graf dengan menggunakan algoritma Welch-Powell. 1. Urutkan titik-titik dari graf dalam derajat yang menurun (urutan seperti ini mungkin tidak unik karena beberapa titik mungkin berderajat sama). 2. Gunakan warna 𝛼 untuk mewarnai titik pertama (yang mempunyai derajat tertinggi) dan titik-titik lain (dalam urutan yang berurut) yang tidak bertetangga dengan titik pertama ini. 3. Mulai lagi dengan titik derajat tertinggi berikutnya di dalam daftar terurut yang belum diwarnai dan ulangi proses pewarnaan. 4. Ulangi penambahan warna-warna sampai semua titik telah diwarnai. Contoh Diketahui graf dengan 7 titik sebagai berikut. Tentukan bilangan khromatiknya.



Penyelesaian: Derajat titik di G disajikan pada Tabel berikut Titik



a



b



Derajat titik



5



4



c



d



4



4



e



f



3



g



3



3



Langkah-langkah pewarnaan graf dengan menggunakan algoritma Welch-Powell adalah sebagai berikut. 1. Jumlah titik graf adalah 7 buah dan urutan titik dari derajat yang tertinggi hingga yang terendah seperti tabel 2. Karena a berderajat tertinggi, sehingga titik a dapat diwarnai dengan warna pertama, yaitu warna 𝛼, dan titik g yang tidak bertetangga dengan titik a dapat diwarnai dengan warna 𝛼 . 3. Titik berderajat tertinggi berikutnya yang belum diwarnai yaitu titik b. Warnai titik b dengan warna kedua, yaitu warna 𝛽. Titik yang belum diwarnai dan tidak bertetangga dengan titik b , yaitu titik c sehingga titik c mendapatkan warna 𝛽. 4. Titik berderajat tertinggi berikutnya yang belum diwarnai yaitu titik d. Warnai titik d dengan warna ketiga, yaitu warna 𝛾. 5. Titik terakhir yang belum diwarnai yaitu titik e dan f, karena titik e dan f tidak bertetangga maka boleh diwarnai dengan warna yang sama, yaitu warna 𝛿.



Jadi dengan menggunakan algoritma Welch-Powell ada 4 warna yang diperlukan untuk mewarnai graf G, sehingga𝜒(G) = 4. Hasil pewarnaan titik graf diberikan pada gambar berikut.



B. Polinomial Kromatik Misalkan G adalah graf sederhana, dan misalkan 𝑃𝐺 (𝑘) adalah jumlah cara mewarnai titik G dengan k warna sehingga tidak ada dua titik berdampingan yang berwarna sama. 𝑃𝐺 disebut fungsi kromatik (chromatic function) dari G. sebagai contoh perhatikan gambar berikut. Contoh 1



Karena titik tengah dapat diwarnai dengan k cara dan titik ujung-ujungnya dapat diwarnai dengan (𝑘 − 1) cara sehingga 𝑃𝐺 (𝑘) = 𝑘(𝑘 − 1)2 . Misalkan banyak warna yang digunakan 2 warna maka 𝑃𝐺 (2) = 2(2 − 1)2 = 2 cara, tetapi jika warna yang digunakan 3 warna maka 𝑃𝐺 (3) = 3(3 − 1)2 = 3(4) = 12 cara. Hasil ini dapat diperluas untuk menunjukkan bahwa, jika G adalah sembarang pohon dengan n titik, maka 𝑷𝑮 (𝒌) = 𝒌(𝒌 − 𝟏)𝒏−𝟏 Contoh 2



Jika gambar di atas merupakan graf lengkap 𝐾3 , maka 𝑃𝐺 (𝑘) = 𝑘(𝑘 − 1)(𝑘 − 2). Hasil ini dapat diperluas menjadi 𝑃𝐺 (𝑘) = 𝑘(𝑘 − 1)(𝑘 − 2) … … (𝑘 − 𝑛 + 1), jika G adalah graf lemgkap 𝐾𝑛



TEOREMA 5.6 Misalkan G adalah sebuah graf sederhana dan 𝐺 − 𝑒 dan 𝐺/𝑒 adalah graf-graf yang didapatkan dari G dengan menghilangkan dan mengkontraksikan sebuah garis e. Maka 𝑃𝐺 (𝑘) = 𝑃𝐺−𝑒 (𝑘) − 𝑃𝐺/𝑒 (𝑘) Sebagai contoh perhatikan graf berikut



Maka berdasarkan teorema 𝑃𝐺 (𝑘) = 𝑃𝐺−𝑒 (𝑘) − 𝑃𝐺/𝑒 (𝑘) 𝑘(𝑘 − 1)(𝑘 − 2)(𝑘 − 3) = {𝑘(𝑘 − 1)(𝑘 − 2)2 } − {𝑘(𝑘 − 1)(𝑘 − 2)} KONSEKUENSI 5.7 Fungsi kromatik dari sebuah graf sederhana adalah sebuah polynomial Dan berdasarkan konsekuensi di atas polinomial kromatik dari graf tersebut adalah 𝑃𝐺 (𝑘) = 𝑃𝐺−𝑒 (𝑘) − 𝑃𝐺/𝑒 (𝑘) 𝑃𝐺 (𝑘) = {𝑘(𝑘 − 1)(𝑘 − 2)2 } − {𝑘(𝑘 − 1)(𝑘 − 2)} 𝑃𝐺 (𝑘) = {𝑘(𝑘 − 1)(𝑘 − 2)}{(𝑘 − 2) − 1} 𝑃𝐺 (𝑘) = 𝑘(𝑘 − 1)(𝑘 − 2)(𝑘 − 3) 𝑃𝐺 (𝑘) = 𝑘 4 − 6𝑘 3 + 11𝑘 2 − 6𝑘



LATIHAN 1. Carilah bilangan kromatik dari setiap graf berikut a)



c)



b)



d)



2. Misalkan seorang kimiawan ingin menyimpan lima bahan kimia a, b, c, d,dan e ditempat yang berbeda dalam sebuah gudang. Beberapa dari bahan kimia tersebut bereaksi dengan keras jika berinteraksi, sehingga harus disimpan di tempat yang berbeda. Dalam tabel berikut ini, tanda bintang mengindikasikan pasangan bahan kimia yang harus dipisahkan. Berapa banyak tempat yang dibutuhkan? 3. Tentukan banyak cara graf-graf berikut yang diwarnai dengan tujuh warna a. Graf lengkap 𝐾6 b. Graf lengkap bipartite 𝐾1.5 4. Tentukan polinomial kromatik dari graf G berikut



Kunci Jawaban : 1. a)



𝛽



𝛼



𝛽



𝛼



𝛼



𝛽



Sehingga 𝜒(𝑎) = 2 b)



𝛼



𝛽



𝛽



𝛿



𝛾



Sehingga 𝜒(𝑏) = 4 c)



𝛼 𝛽 𝛼



𝛾



𝛿



𝛼 𝛾



Sehingga 𝜒(𝑐) = 4



𝛽 𝛾 𝛽



d)



𝛼



𝛼



𝛾



𝛽



𝛾



𝛽 𝛿



𝛽



𝛾



𝛽



𝛼



2.



Jadi, banyak tempat yang dibutuhkan untuk menyimpan bahan kimia tersebut adalah 4 tempat 3. 𝑘 = 7 a. 𝐾𝑛 = 𝐾6 𝑃𝑎 (𝑘) = 𝑘(𝑘 − 1)(𝑘 − 2)(𝑘 − 3)(𝑘 − 4)(𝑘 − 5) 𝑃𝑎 (7) = 7(7 − 1)(7 − 2)(7 − 3)(7 − 4)(7 − 5) 𝑃𝑎 (7) = 7(6)(5)(4)(3)(2) 𝑃𝑎 (7) = 5.040 Jadi, banyak cara untuk mewarnai graf lengkap 𝐾6 dengan tujuh warna adalah 5.040 cara b. 𝐾1.5 𝑛=5 𝑃𝑏 (𝑘) = 𝑘(𝑘 − 1)𝑛 𝑃𝑏 (7) = 7(7 − 1)5



𝑃𝑏 (7) = 7(6)5 𝑃𝑏 (7) = 54.432 Jadi, banyak cara untuk mewarnai graf bipartit 𝐾1.5 dengan tujuh warna adalah 54.432 cara 4.



𝑃𝐺 (𝑘) = 𝑘(𝑘 − 1)4 − 3𝑘(𝑘 − 1)3 + 2𝑘(𝑘 − 1)2 + 𝑘(𝑘 − 1)(𝑘 − 2)



𝑃𝐺 (𝑘) = 𝑘 5 − 7𝑘 4 + 18𝑘 3 − 20𝑘 2 + 8𝑘 Jadi, polinomial kromatik dari G adalah 𝑘 5 − 7𝑘 4 + 18𝑘 3 − 20𝑘 2 + 8𝑘



C. Pewarnaan Peta Sebelum membahas pewarnaan peta, terlebih dahulu akan dibahas pengertian graf planar dan graf dual. 1.



Graf Planar dan Graf Bidang Graf yang dapat digambarkan pada bidang datar dengan garis-garis tidak saling memotong disebut sebagai graf planar, jika tidak, ia disebut graf tak-planar. Perlu di perhatikan bahwa belum tentu suatu graf yang secara kasat mata terlihat garisgarisnya saling berpotongan tidak planar. Graf tersebut mungkin saja planar, karena graf tersebut dapat digambarkan kembali dengan cara berbeda yang garis-garisnya tidak saling berpotongan.



Graf yang termasuk planar antara lain :  Tree / Pohon  Kubus  Bidang Empat  Bidang Delapan Beraturan Representasi gerak planar yang digambarkan dengan garis-garis yang tidak saling berpotongan disebut graf bidang (plane graf) .



Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang 2. Graf Dual Misalkan kita mempunyai sebuah graf planar G yang direprentasikan sebagai graf bidang. Kita dapat membuat suatu graf G* yang secara geometris merupakan dual dari graf planar tersebut dengan cara sebagai berikut: (a) Pada setiap wilayah atau muka (face) f di G, buatlah sebuah titik v* yang merupakan titik untuk G*. (b) Untuk setiap garis e di G tariklah garis e* ( yang menjadi garis untuk G*) yang memotong garis e tersebut. Garis e* menghubungkan dua buah titik v1* dan v2* ( titik-titik di G*) yang berada di dalam muka f1 dan f2 yang dipisahkan oleh garis e di G. Untuk salah satu titiknya merupakan titik berderajat 1 (jadi, garis e seluruhnya terdapat di dalam sebuah muka), maka garis e* adalah berupa garis gelang. Graf G* yang terbentuk dengan cara penggambaran demikian disebut graf dual (atau tepatnya dual geometri) dari



graf G. Antara “unsur-unsur” graf G dan G* terdapat



korespondensi satu-satu sebagai berikut: (a) Sebuah “muka” G berkorespondensi dengan sebuah titik G*. Ini berakibat |F(G)| = |V(G*)|. (b) Sebuah garis G berkorespondensi dengan sebuah garis G*. Jadi |E(G)| =|E(G*)|. (c) Sebuah muka berderajat k di G berkorespondensi dengan sebuah titik berderajat k di G* sehingga ∑𝑓∈𝐹(𝐺) 𝑑(𝑓) = ∑𝑣∈𝑉(𝐺 ∗) 𝑑(𝑣) (d) Sebuah garis yang terkait dengan sebuah titik yang berderajat satu di G, berkorespondensi dengan sebuah loop di G*. (e) Sebuah titik berderajat dua di G, berkorespondensi dengan sepasang garis rangkap di G* Salah satu aplikasi graf dual yang penting untuk mempresentasikan peta (map). Setiap peta pada bidang terdiri dari sejumlah wilayah (region). Wilayah pada peta dapat menyatakan suatu Negara, provinsi, atau kabupaten. Tiap wilayah pada peta dinyatakan sebagai sebuah titik, sedangkan garis menyatakan bahwa dua wilayah berbatasan langsung (bertetangga). Dalam pewarnaan peta, muncul pertanyaan: Paling sedikit berapa warna yang diperlukan untuk mewarnai sebarang peta sehingga daerah yang bertetangga diwarnai berbeda? Jika pada peta masing-masing



daerah dipandang sebagai titik dan titik-titik yang mewakili dua daerah yang bertetangga dihubungkan oleh satu garis, maka yang terjadi adalah graf dual dari peta tersebut. Pertanyaan di atas ekivalen dengan: Untuk peta, berapakah nilai k terkecil sehingga G dapat diwarnai dengan k warna. Sehingga langkah-langkah pewarnaan peta adalah: a. Buat suatu graf G* yang secara geometris merupakan dual dari peta. b. Warnai titik pada graf dual tersebut menggunakan Algoritma Welch-Powell



Teorema 1 Misalkan G adalah graf bidang datar tanpa loop dan G* adalah dual geometri dari G, maka G adalah k-colourable –(f) jika dan hanya jika G* adalah k-colorable – (v)



Teorema Empat Warna Teorema empat warna menyatakan bahwa untuk sebarang peta dapat diwarnai dengan k ≤ 4 warna sedemikian hingga tidak ada dua wilayah yang berdekatan yang memiliki warna yang sama.



Contoh 1 : Warnai peta pada Gambar 1, kemudian tentukan bilangan khromatiknya.



Gambar 1



Penyelesaian : a. Buat suatu graf G* yang secara geometris merupakan dual dari peta.



Gambar 2 b. Warnai titik pada graf dual tersebut menggunakan Algoritma Welch-Powell (a) Pengurutan derajat titik Titik



E



F



B



A



C



I



D



G



H



Derajat titik



6



5



4



3



3



3



2



2



2



(b) Pewarnaan titik Pertama tandailah titik E dengan angka 1. Telusuri daftar titik tadi dan amati gambar grafnya, ternyata titik C adalah titik pertama yang tidak berdekatan dengan E. Kembali ke daftar titik, tandai titik F dengan angka2, dan juga titik A dan H, karena tidak berdekatan dengan F. Penelusuran ketiga kalinya terhadap daftar titik akan menandai titik B dengan angka3, lalu tandai pula titik I, D, dan G dengan angka 3. Dengan demikian bilangan khromatik graf tersebut adalah 3. Langkah-langkah tersebut dirangkum dalam bentuk tabel berikut. Titik



E



F



B



A



C



I



D



G



H



Derajat titik



6



5



4



3



3



3



2



2



2



Warna



1



3



2



1



2



3



3



3



2



Contoh 2 Gambar 3 (a) merupakan bagian dari peta Amerika Serikat. Grafnya beserta warna (label) diperlihatkan pada Gambar 3 (b) dengan menggunakan algoritma Welsh dan Powell.



Gambar 3 (a)



Gambar 3 (b)



Berikut ini tabel yang menunjukkan hubungan antara titik, derajat titik dan warna. Titik Derajat titik Warna



AZ



UT



NV



CO



NM



CA



WY



TX



4



4



3



3



3



2



2



1



(1)



(2)



(3)



(1)



(2)



(2)



(3)



(1)



Peta pada Gambar 3 (a) dapat diwarnai dengan 3 warna



D. Pewarnaan Garis Pewarnaan garis pada suatu graf adalah penentuan warna garis suatu graf sehingga setiap garis yang berdekatan mendapatkan warna yang berbeda. Ukuran keberwarnaan suatu graf didefinisikan sama dengan ukuran keberwarnaan titik, yaitu mengacu kepada banyaknya warna yang memungkinkan sehingga setiap garis yang berdekatan mendapat warna yang berbeda. Jumlah warna minimal yang dapat digunakan untuk mewarnai garis-garis dalam suatu graf G disebut bilangan khromatik G. Misalkan G graf tanpa loop. Suatu pewarnaan garis-k (k-edge colouring) untuk graf G adalah suatu penggunaan sebagian atau semua k warna untuk mewarnai semua garis di G sehingga setiap pasang garis yang mempunyai titik persekutuan diberi warna yang berbeda. Jika G mempunyai pewarnaan garis-k, maka dikatakan garis-garis di G dapat diwarnai dengan k warna (k-edge colourable). Indeks khromatik (chromatic index) dari graf G, dinotasikan χ’(G), adalah



Indeks k terkecil sehingga garis-garis di G dapat diwarnai dengan k warna. Biasanya warna-warna yang digunakan untuk mewarnai garis-garis suatu graf dinyatakan dengan 1, 2, 3, …, k.



Teorema 1 (Teorema Vizing) Jika G adalah graf sederhana dengan derajat titik maksimum ∆(G), maka ∆(G) ≤ χ’(G) ≤ ∆(G) + 1. Contoh 1



Derajat maksimum titik dari graf G1, G2, dan G3 adalah 3. Sehingga berdasarkan Teorema Vizing, maka 3 ≤ χ’(G) ≤ 4. Indeks khromatiknya adalah 3.



Teorema 2 (Perluasan Teorema Vizing) Jika G adalah graf dengan derajat titik maksimum ∆(G), dan h adalah banyak maksimum garisgaris yang menghubungkan sepasang titik, maka ∆(G) ≤ χ’(G) ≤ ∆(G) + h Contoh 2



G Tentukan Indeks khromatik pada graf G!



Penyelesaian : 1



2 3



3



1 Pada graf G, ∆(G) = 3 dan h = 2, maka 3 ≤ χ’(G) ≤ 5. Dari gambar di atas, Indeks khromatik graf G adalah 3.



Teorema 3 (Teorema Konig) Jika G adalah graf bipartit dengan derajat titik maksimum ∆(G), maka χ’(G) = ∆(G). Contoh 3



Akibat 4 𝜒 ′ (𝐾𝑟,𝑠 ) = maks (r,s) Contoh 4



Untuk graf lengkap berlaku : Teorema 5 𝜒 ′ (𝐾𝑛 ) = 𝑛 jika n adalah ganjil (n ≥ 3) dan 𝜒 ′ (𝐾𝑛 ) = 𝑛 − 1 jika n adalah genap Contoh 5 Tentukan Indeks khromatik untuk graf G, H, dan J di bawah ini.



G



H



J



Penyelesaian: Perhatikan pewarnaan garis untuk graf G, H, dan J berikut. 3



1



2 2 1



2



1



1



4



2



31



3 3 G



3 H



2 4 J







Untuk graf G, jelas bahwa χ’(G) = 3.







Untuk graf H, diketahui n = 4 (genap) sehingga 𝜒 ′ (𝐾𝑛 ) = 4 − 1 = 3







Untuk graf J, χ’(J) ≥ 4 karena ∆(G) = 4 dan χ’(J) ≤ 4 karena garis-garis di J dapat diwarnai dengan 4 warna seperti pada gambar. Jadi χ’(J) = 4.



Untuk graf sikel berlaku: Teorema 6 𝜒 ′ (𝐶𝑛 ) = 3 jika n adalah ganjil dan 𝜒 ′ (𝐶𝑛 ) = 2 jika n adalah genap Contoh 6



G



Tentukan Indeks khromatik pada graf G! Penyelesaian : Diketahui n = 8 (genap) maka 𝜒 ′ (𝐶8 ) = 2



1 2



2



1



1



2



2 1 G



Sehingga, Indeks khromatik graf G adalah 2. Contoh 7



G Tentukan Indeks khromatik pada graf G! Penyelesaian : Diketahui n = 3 (ganjil) maka 𝜒 ′ (𝐶3 ) = 3



1



2



3 Sehingga, Indeks khromatik graf G adalah 3.



Latihan 1.



Berapa banyak warna yang dibutuhkan untuk mewarnai peta dari negara-negara pada gambar di samping?



2. Perhatikan graf berikut ini!



Garis graf tersebut dapat diwarnai minimal dengan .... warna 3.



Sisi (rusuk) dari graf berikut dapat diwarnai minimal dengan .... warna



4. Graf bipartit lengkap K7,4 sisinya (rusuknya) dapat diwarnai minimal .... warna 5. Graf lengkap K10 rusuknya dapat diwarnai minimal dengan .... warna 6. Graf lengkap K15 rusuknya dapat diwarnai minimal dengan .... warna



Kunci Jawaban :



1.



Titik



A



C



G



S



P



H



Sl



I



Sw



Derajat titik



7



4



4



4



3



3



3



3



3



Warna



1



2



3



3



1



2



3



2



4



2.



Sehingga dapat disimpulkan bahwa garis graf tersebut dapat diwarnai minimal dengan 3 warna



3.



Sehingga dapat disimpulkan bahwa garis graf tersebut dapat diwarnai minimal dengan 5 warna



4. Indeks khromatik sisi (rusuk) K7,4 = max (7,4) = 7. 5. Indeks khromatik rusuk K10 = 10 - 1 = 9.



6. Indeks khromatik rusuk K15 = 15.