Pertemuan 06 - Algoritma Pewarnaan Bidang
Teori Pewarnaan Graf
Pewarnaan graf adalah penugasan label (warna) ke elemen-elemen graf (simpul, sisi, atau wilayah) dengan batasan tertentu. Pada pertemuan ini, fokus kita adalah pewarnaan simpul (vertex coloring) dengan algoritma Welch-Powell.
Algoritma Welch-Powell
- Urutkan simpul-simpul dalam derajat menurun (simpul dengan derajat tertinggi pertama)
- Gunakan warna pertama untuk mewarnai simpul pertama
- Warnai simpul berikutnya yang tidak bertetangga dengan simpul sebelumnya yang telah diwarnai dengan warna yang sama, secara berurutan
- Ulangi langkah 2 dan 3 dengan warna baru untuk simpul yang belum diwarnai hingga semua simpul terwarnai
Implementasi Interaktif
Hasil Pewarnaan (Algoritma Welch-Powell)
| Simpul | Derajat | Warna | Nilai Warna |
|---|