Pewarnaan Graf.pptx

Pewarnaan Graf Oleh: Mulyono & Isnaini Rosyida

Pewarnaan Graf

04

03 01

Pewarnaan Titik (VertexColoring)

02

Pewarnaan Sisi (EdgeColoring)

Pewarnaan Peta (Coloring Map)

Aplikasi Pewarnaan Graf

Pewarnaan Titik (Vertex-Coloring)

Misalkan G graf tanpa loop. Suatu pewarnaan-k (k-coloring) 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-colorable). Bilangan khromatik (chromatic number) dari graf G, dinotasikan χ(G), adalah bilangan k terkecil sehingga G dapat diwarnai dengan k warna. Jadi, 𝜒 𝐺 = min{𝑘/ ada pewarnaan-𝑘 pada 𝐺}. Biasanya warna-warna yang digunakan untuk mewarnai titik-titik suatu graf dinyatakan dengan 1, 2, 3, …, k. Jelas bahwa χ(G) ≤ |V(G)|. Sedangkan cara yang mudah untuk menentukan batas bawah dari χ(G) adalah dengan mencari subgraf komplit yang terbesar di G.

Pewarnaan Titik (Vertex-Coloring) Misalkan dipunyai graf G, H, dan K berikut.

• Untuk graf G, karena |V(G)| = 3, maka χ(G) ≤ 3. Pada graf G memuat graf komplit K3, maka χ(G) ≥ 3. Akibatnya χ(G) = 3. • Untuk graf H, karena |V(H)| = 4, maka χ(H) ≤ 4. Pada graf H memuat graf komplit K4, 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 komplit K3, maka χ(J) ≥ 3. Akibatnya χ(J) = 3.

Pewarnaan Titik (Vertex-Coloring) Teorema 7

Jika G graf sederhana dengan derajat titik maksimum d, maka χ(G) ≤ d + 1. Teorema Brooks berikut sedikit lebih baik dari Teorema 1.

Pewarnaan Titik (Vertex-Coloring) Teorema 8

Misalkan G graf sederhana, terhubung, dan derajat titik maksimum adalah d. Jika G bukan graf komplit dan bukan sikel dengan banyak titik ganjil, maka χ(G) ≤ d. Pada pewarnaan titik, belum ada algoritma yang efisien untuk melakukan pewarnaan dengan banyak warna yang minimum pada sebuah graf. Hal ini berakibat, belum ada algoritmaa yang efisien untuk menentukan bilangan khromatik. Jadi beberapa algoritma yang ada hanyalah merupakan algoritma pendekatan dan tidak menjamin diperolehnya pewarnaan dengan banyak warna minimum. Salah satu algoritma untuk pewarrnaan titik adalah algoritma Welch-Powell.

Pewarnaan Titik (Vertex-Coloring) langkah-langkah pewarnaan titik pada graf 𝐺 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 1 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.

Pewarnaan Sisi (Edge-Coloring)

Misalkan G graf tanpa loop. Suatu pewarnaan sisi-k (k-edge-coloring) untuk graf G adalah suatu penggunaan sebagian atau semua k warna untuk mewarnai semua sisi di G sehingga setiap pasang sisi yang mempunyai titik persekutuan diberi warna yang berbeda. Jika G mempunyai pewarnaan sisi-k, maka dikatakan sisi-sisi di G dapat diwarnai dengan k warna (k-edge colorable). Indeks khromatik (chromatic index) dari graf G, dinotasikan χ’(G), adalah bilangan k terkecil sehingga sisi-sisi di G dapat diwarnai dengan k warna. Biasanya warna-warna yang digunakan untuk mewarnai sisi-sisi suatu graf dinyatakan dengan 1, 2, 3, …, k. Jelas χ’(G) ≤ |V(G)|, dan jika derajat titik maksimum di G adalah d, maka χ’(G) ≥ d.

Pewarnaan Peta (Coloring Map)

Cara mengkonstruksi graf dual G* dari G: Pandang sebuah graf bidang G. Konstruksi suatu graf G* sedemikian hingga 1. setiap titik G* berkorespondensi dengan sebuah “muka” dari G; 2. jika sebuah sisi e membatasi muka f1 dan f2 di G maka titik-titik G* yang berkorespondensi dengan f1 dan f2 dihubungkan dengan sebuah sisi.

Pewarnaan Peta (Coloring Map) Antara “unsur-unsur” graf G dan G* terdapat korespondensi satu-satu sebagai berikut: 1. Sebuah “muka” G berkorespondensi dengan sebuah titik G*. Ini berakibat |F(G)| =|V(G*)|. 2. Sebuah sisi G berkorespondensi dengan sebuah sisi G*. Jadi |E(G)| =|E(G*)|. 3. Sebuah muka berderajat k di G berkorespondensi dengan sebuah titik berderajat k di G* sehingga

 d(f)   d(v)

f F(G)

vV(G*)

4. Sebuah sisi yang terkait dengan sebuah titik yang berderajat satu di G, berkorespondensi dengan sebuah loop di G*. 5. Sebuah titik berderajat dua di G, berkorespondensi dengan sepasang sisi rangkap di G*.

Pewarnaan Peta (Coloring Map)

Peta adalah graf bidang yang tidak memuat jembatan. Pewarnaan peta itu ekivalen dengan pewarnaan titik pada graf dual dari peta tersebut.

Aplikasi Pewarnaan Graf 1. Penempatan Bahan-bahan Kimia

Berapa minimum banyaknya wadah yang diperlukan untuk menyimpan bahan kimia agar tidak terjadi ledakan?

Bagaimana membuat jadwal ujian agar banyaknya tahap yang digunakan minimum.

2. Penjadwalan Ujian