BacktrackingMenengahFase D–FE1E5

Pewarnaan Graf (Graph Coloring)

Graph Coloring memberi warna pada setiap simpul graf sehingga tidak ada dua simpul bertetangga yang berwarna sama, menggunakan pendekatan backtracking. Untuk tiap node dicoba warna dari palet; jika aman (tidak bentrok dengan tetangga) lanjut ke node berikutnya, jika buntu warna dibatalkan dan mundur untuk mencoba pilihan lain. Visualisasi menampilkan simpul yang diwarnai bergantian, konflik yang ditandai, hingga solusi valid terkunci.

Contoh kasus

Penjadwalan ujian agar mata kuliah dengan mahasiswa yang sama tidak dijadwalkan pada slot waktu bersamaan.

Silabus

Graph Coloring memberi warna tiap simpul agar tak ada tetangga berwarna sama, memakai backtracking saat menemui jalan buntu.

Tujuan Belajar

·Memahami aturan dua simpul bertetangga tak boleh sewarna
·Menjelaskan cara backtracking membatalkan warna yang gagal
·Menerapkan pewarnaan graf untuk masalah penjadwalan

Cara Kerja

·Ambil satu simpul yang belum diwarnai
·Coba beri warna dari palet yang tersedia
·Cek aman: warna itu tidak sama dengan tetangga manapun
·Bila aman lanjut ke simpul berikutnya secara rekursif
·Bila buntu, batalkan warna (backtrack) dan coba pilihan lain sampai valid

Prasyarat

·Graf
·Backtracking

Contoh Nyata

·Penjadwalan ujian agar mata kuliah dengan siswa sama tak bentrok slot
·Mengalokasikan frekuensi pemancar agar stasiun berdekatan tak saling ganggu
·Mewarnai peta wilayah agar daerah bersebelahan beda warna

Kompleksitas O(warna^V) pada kasus terburuk