7/21/2019 Pembahasan latihan soal 1.pdf

http://slidepdf.com/reader/full/pembahasan-latihan-soal-1pdf 1/2

1. Berilah warna pada graf di bawah ini dengan menggunakan algoritma Welch-Powell.

Penyelesaian:

Langkah 1 : menulis derajat semua titik dan diurutkan

deg (V5) = 5; deg (V3) = 5; deg (V1) = 4; deg (V2) = 4; deg (V6) = 4; deg (V4) = 2

Daftar titik yang berdekatan

V5 : V1, V2, V3, V4, V6

V3 : V1, V2, V3, V4, V5

V1 : V2, V3, V5, V6

V2 : V1, V3, V5, V6

V6 : V1, V2, V3, V5

V4 : V3, V5

Langkah 2 : Warnai titik pertama pada daftar tersebut dan titik-titik belum

berwarna yang tidak berdekatan dengan titik itu.

V5 : V1, V2, V3, V4, V6 (BIRU)

V3 : V1, V2, V4, V5, V6

V1 : V2, V3, V5, V6

V2 : V1, V3, V5, V6

V6 : V1, V2, V3, V5

V4 : V3, V5

Langkah 3 : Warnai titik berikutnya yang belum berwarna dengan warna yang

belum digunakan pada titik pertama pada daftar titik itu dan titik-titik yang tidak

berdekatan pada titik berikutnya tersebut.

V5 : V1, V2, V3, V4, V6 (BIRU)

V3 : V1, V2, V4, V5, V6 (HIJAU)

V1 : V2, V3, V5, V6

7/21/2019 Pembahasan latihan soal 1.pdf

http://slidepdf.com/reader/full/pembahasan-latihan-soal-1pdf 2/2

V2 : V1, V3, V5, V6

V6 : V1, V2, V3, V5

V4 : V3, V5

Langkah 4 : Lakukan hal itu pada semua titik dalam daftar secara terurut,

berikan warna baru ini pada setiap titik berikutnya yang belum terwarna sampai

semua titik pada graf terwarnai.

V5 : V1, V2, V3, V4, V6 (BIRU)

V3 : V1, V2, V4, V5, V6 (HIJAU)

V1 : V2, V3, V5, V6 (KUNING)

V2 : V1, V3, V5, V6 (MERAH)

V6 : V1, V2, V3, V5 (HITAM)

V4 : V3, V5 (KUNING)

Dari keempat langkah di atas, titik V1 diberi warna biru, titik V3 diberi warna hijau,

titik V1 dan V4 diberi warna kuning, titik V2 diberi warna merah, dan titik V6 diberi warna

hitam. Dengan demikian graf pada gambar dapat diwarnai dengan lima warna.