BacktrackingMenengahFase D–FE1E5

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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Graf
·Backtracking

Real-World Uses

·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

Complexity O(warna^V) pada kasus terburuk