Progres sesi
0 / 4
Sheet 12 · Materi Detail

Warnai Petanya

Pewarnaan Graf & Presentasi Proyek — menutup kelas dengan menyelesaikan proyek akhir Peta Jaringan Kota lewat pewarnaan graf.

Durasi: 120 menit Prasyarat: Pertemuan 10-11 — Graf, Euler & Pohon Merentang Tools: kalkulator validasi pewarnaan graf di halaman ini
1

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).

Ini pertemuan terakhir! Hari ini kita menyelesaikan proyek akhir Peta Jaringan Kota — dari graf dasar (P10), Euler & pohon merentang (P11), sampai pewarnaan (P12 hari ini).
2

Aturan & Aplikasi Pewarnaan

Ada 4 istilah kunci soal pewarnaan graf:

Syarat Utama

Aturan Pewarnaan

Dua titik bertetangga (terhubung sisi) tidak boleh sewarna.

Nilai Optimal

Bilangan Kromatik

Jumlah warna PALING SEDIKIT yang dibutuhkan supaya pewarnaan sah. Mencari nilai optimalnya rumit (di luar cakupan kelas ini) — cukup tahu konsepnya dulu.

Kasus Khusus

Graf Berisi Segitiga

Kalau ada 3 titik yang saling terhubung semua (segitiga), minimal butuh 3 warna.

Dunia Nyata

Aplikasi Penjadwalan

Pewarnaan graf dipakai untuk menjadwalkan ujian/acara supaya tidak ada dua acara "bertabrakan" yang dijadwalkan bersamaan.

3

Coba Langsung: Kalkulator Validasi Pewarnaan Graf

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).

Kalkulator Validasi Pewarnaan Graf
Klik Validasi untuk melihat hasilnya…

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).

4

Latihan Mandiri / Penyelesaian Proyek Akhir

Ini langkah terakhir proyek akhir kamu:

  • Ambil Peta Jaringan Kota rancangan sendiri dari Pertemuan 10-11, buat pewarnaan sendiri untuk tiap lokasi (usahakan pakai sesedikit mungkin warna).
  • Validasi pewarnaanmu pakai kalkulator di atas — kalau masih ada pelanggaran, ubah warnanya sampai SAH.
  • Review checklist proyek akhir: pastikan sudah lengkap — graf + derajat tiap lokasi (dari P10), cek Euler + pohon merentang (dari P11), dan pewarnaan yang sah (dari P12 hari ini).
  • Siapkan hasilnya untuk dipresentasikan ke teman sekelas!
5

Kuis Tantangan Akhir

1. p AND q bernilai Benar hanya ketika...

AND adalah syarat ganda — butuh keduanya Benar.

2. Kontraposisi dari p→q adalah...

Kontraposisi menukar sekaligus menegasikan p dan q, dan selalu ekuivalen secara logis dengan implikasi aslinya.

3. Jika A={1,2,3} dan B={3,4,5}, maka A∩B = ?

Hanya angka 3 yang muncul di kedua himpunan.

4. Fungsi f(x)=x² pada domain {1,2,3} bersifat injektif karena...

Tidak ada dua input berbeda di domain ini yang menghasilkan output sama.

5. Ada 3 jenis kemeja dan 4 jenis celana. Berapa total kombinasi outfit (satu kemeja + satu celana) yang bisa dibuat?

Ini aturan perkalian — dua tahap berurutan yang independen (pilih kemeja LALU pilih celana): 3 × 4 = 12.

6. Premis: "Jika n habis dibagi 4 maka n genap" dan "n habis dibagi 4". Kesimpulan valid apa yang bisa ditarik?

Ini pola Modus Ponens: p → q dan p benar, maka q pasti benar. "n habis dibagi 4" (p) benar, jadi "n genap" (q) pasti benar.

7. Graf dengan semua titik berderajat genap dan terhubung pasti memiliki...

Ini syarat pasti untuk sirkuit Euler — semua derajat genap + graf terhubung.

8. Pewarnaan graf dikatakan SAH jika...

Inti pewarnaan graf adalah memastikan dua titik yang "berdekatan langsung" tetap bisa dibedakan.
Skor: 0 / 8 terjawab benar
6

Ringkasan Pertemuan 12

  • Pewarnaan graf: dua titik bertetangga (terhubung sisi) tidak boleh sewarna. Diterapkan misalnya untuk penjadwalan ujian.
  • Bilangan kromatik adalah jumlah warna paling sedikit yang bisa dipakai — kalau ada segitiga (3 titik saling terhubung), minimal butuh 3 warna.
  • Peta Jaringan Kota kita (A,B,C,D,E dengan rute A-B,B-C,C-D,D-E,E-A,A-C) bisa diwarnai sah dengan pewarnaan A-Merah, B-Biru, C-Hijau, D-Merah, E-Biru — total 3 warna, 0 pelanggaran.
  • Proyek akhir Peta Jaringan Kota selesai: derajat titik (P10), Euler & pohon merentang (P11), dan pewarnaan graf (P12) — satu graf yang sama, dianalisis dari berbagai sudut pandang.
Selesai!

Selamat, 12 pertemuan Matematika Diskrit sudah tuntas — dari logika dasar sampai proyek akhir Peta Jaringan Kota. Saatnya presentasikan hasilnya ke teman sekelas!

made by boflyeta.dev