Pewarnaan
graph menggunakan ALGORITMA WELCH-POWELL dalam kasus ini kita akan
mengaplikasikan ALGORITMA WELCH-POWELL pada graph yang telah kita buat
sebelumnya tapi sebelum itu kita perlu tahu apa itu ALGORITMA WELCH-POWELL.
ALGORITMA WELCH-POWELL : pewarnaan titik (vertex coloring) dengan warna
minimal dengan berpedoman pada derajat tertinggi
Setelah kita
tau apa itu ALGORITMA WELCH-POWELL sekarang kita timbul pertanyaan
bagaimana caranya menggunakannya
ALGORITMA WELCH-POWELL
1. Urutkan semua titik berdasarkan derajatnya dari
derajat besar sampai yang kecil
2. Ambil warna pertama. Warnai titik dengan derajat
tertinggi dengan warna tersebut dan cari titik lain yang tak terhubung langsung
dan berderajat maksimal lalu warnai dengan warna yang sama dan cari titik lain
yang tak terhubung langsung. Setelah itu cari titik dengan derajat tinggi
lainnya lalu beri warna yang beda
Ulangi langkah 2 sampai semua titik telah di beri
warna setelah itu STOP
Sekarang kita
akan gunakan ALGORITMA WELCH-POWELL untuk mewarnai Graph kita
Langkah 1:
Kita urutkan derajat titiknya
Titik
|
Derajat
|
Titik
|
Derajat
|
Sidoarjo
|
5
|
Prambon
|
3
|
Tulangan
|
4
|
Krian
|
3
|
Wonoayu
|
4
|
Taman
|
3
|
Sukodono
|
4
|
Waru
|
3
|
Gedangan
|
4
|
Sedati
|
3
|
Krembung
|
3
|
Candi
|
2
|
Tanggulangin
|
3
|
Porong
|
2
|
Dari tabel di atas maka urutannya:
Sidoarjo, Tulangan,
Wonoayo, Sukodono , Gedangan, Krembung, tanggulangin, Prambon, Krian, Taman,
Waru, Sedati, Candi, Porong
Langkah 2 :
Ø Ambil warna pertama Hijau beri warna Hijau pada Sidoarjo karena punya derajat
maksimal yaitu 5, cari titik lain yang tak terhubung langsung dengan Sidoarjo (yaitu : Wonoayo, Krembung, tanggulangin, Prambon,
Krian, Taman, Waru, Porong)
Ø dari titik tersebut cari yang punya drajat maksimal
yaitu Wonoayu di beri warna
sama yaitu Hijau dan cari yang tak terhubung langsung dengan Wonoayu
Ø dengan cara yang sama kita dapat Krembung, Tanggulangin dan Waru lalu
beri warna Hijau
Ø Sehingga urutan Titik yang belum di warnai
Tulangan, Sukodono ,
Gedangan, Prambon, Krian, Taman, Sedati,
Candi, Porong
Ø Ambil warna kedua Merah karena Tulangan, Sukodono, Gedangan
berderajat sama yaitu 4 maka pilih salah satu misal kita beri warna Merah pada Tulangan cari titik lain yang tak
terhubung langsung dengan Tulangan(yaitu
: Sukodono , Gedangan, Prambon, Krian,
Taman, Sedati, Candi, Porong)
Ø Dari titik tersebut cari yang berderajat maksimal
yaitu Sukodono di beri warna
sama yaitu Merah dan cari yang tak terhubung langsung dengan Sukodono
Ø Dengan cara yang sama kita dapat Prambon, Sedati, Candi, dan Porong lalu beri warna Merah
Ø Sehingga
urutan Titik yang belum di warnai
Gedangan, Krian, Taman
Ø Ambil warna ketiga Kuning karena Gedangan
berderajat paling besar( yaitu : 4) maka cari titik yang tak terhubung langsung
dengan Gedangan (yaitu: Krian, Taman)
Ø Dari titik tersebut cari yang berderajat maksimal
karena Krian, Taman berderajat
sama (yaitu : 3) pilih salah satu yaitu Taman
lalu beri warna yang sama yaitu Kuning
Ø Karena tinggal Krian maka kita beri warna yang ke empat Biru ke Krian
Ø Pewarnaan Graph selesai, Graph bewarna 4 . Jadi K(G)=4
Hasil pewarnaan bisa di lihat di halaman
Selanjutnya.
