Pewarnaan Graf & Presentasi Proyek — menutup kelas dengan menyelesaikan proyek akhir Peta Jaringan Kota lewat pewarnaan graf.
Coba bayangin kamu mewarnai peta negara-negara di dunia. Aturannya simpel: dua negara yang berbatasan langsung TIDAK BOLEH diwarnai sama, supaya batas antar negaranya kelihatan jelas di peta. Prinsip yang sama persis berlaku di teori graf, namanya pewarnaan graf.
Dalam graf: dua titik yang bertetangga (terhubung langsung oleh satu sisi) TIDAK BOLEH diberi warna yang sama. Warna di sini cuma "label" — bisa berupa warna beneran, angka, atau kategori apapun.
Ini bukan cuma teori doang — pewarnaan graf dipakai buat masalah nyata, misalnya penjadwalan ujian: kalau dua mata kuliah punya peserta yang sama, keduanya tidak boleh dijadwalkan di slot waktu yang sama (dianggap "bertetangga" di graf jadwal).
Ada 4 istilah kunci soal pewarnaan graf:
Dua titik bertetangga (terhubung sisi) tidak boleh sewarna.
Jumlah warna PALING SEDIKIT yang dibutuhkan supaya pewarnaan sah. Mencari nilai optimalnya rumit (di luar cakupan kelas ini) — cukup tahu konsepnya dulu.
Kalau ada 3 titik yang saling terhubung semua (segitiga), minimal butuh 3 warna.
Pewarnaan graf dipakai untuk menjadwalkan ujian/acara supaya tidak ada dua acara "bertabrakan" yang dijadwalkan bersamaan.
Ini penyelesaian proyek akhir kita! Masih pakai Peta Jaringan Kota yang sama dari P10-P11, sekarang kita coba warnai tiap lokasi lalu validasi apakah pewarnaannya sah (tidak ada dua tetangga sewarna).
Coba ubah pewarnaan default jadi A-Merah,B-Merah,... (samain A dan B) — kalkulator harus mendeteksi pelanggaran karena A dan B bertetangga (ada sisi A-B).
Ini langkah terakhir proyek akhir kamu:
1. p AND q bernilai Benar hanya ketika...
2. Kontraposisi dari p→q adalah...
3. Jika A={1,2,3} dan B={3,4,5}, maka A∩B = ?
4. Fungsi f(x)=x² pada domain {1,2,3} bersifat injektif karena...
5. Ada 3 jenis kemeja dan 4 jenis celana. Berapa total kombinasi outfit (satu kemeja + satu celana) yang bisa dibuat?
6. Premis: "Jika n habis dibagi 4 maka n genap" dan "n habis dibagi 4". Kesimpulan valid apa yang bisa ditarik?
7. Graf dengan semua titik berderajat genap dan terhubung pasti memiliki...
8. Pewarnaan graf dikatakan SAH jika...