Pewarnaan Graf: Cara Gampang Biar Nggak Bentrok 

Pernah lihat peta yang tiap daerahnya beda warna, atau jadwal ujian yang disusun supaya nggak bentrok? Itu pakai konsep pewarnaan graf. Tenang, di sini kita pakai bahasa santai biar gampang paham dan langsung bisa dipraktikkan di sekolah.

Apa Itu Graf & Pewarnaan Graf?

Graf itu gambar yang terdiri dari titik (disebut vertex) dan garis penghubung (disebut edge). Pewarnaan graf adalah memberi warna pada tiap titik supaya dua titik yang terhubung garis tidak punya warna yang sama.

Kenapa Harus Diwarnai Berbeda?

• Biar mudah dibedakan.
• Biar nggak bentrok (contoh: dua pelajaran dengan murid yang sama jangan di jam ujian yang sama).
• Memakai warna sesedikit mungkin supaya rapi dan efisien.

Contoh Nyata di Sekolah

• Jadwal Ujian: Setiap mata pelajaran jadi titik. Kalau ada murid yang ambil dua mapel, hubungkan kedua titiknya. Warna yang sama = ujian di jam yang sama. Jadi, titik yang terhubung harus beda warna.
• Denah Ruang: Ruang yang bersebelahan diberi warna beda supaya mudah dilihat.
• Peminjaman Lab: Kelas/ekstrakurikuler yang memakai lab di waktu sama tak boleh bentrok—warnai supaya terlihat kelompok waktu yang aman.

Aturan Singkat yang Penting

1. Titik yang terhubung garis wajib beda warna.
2. Pakai jumlah warna paling sedikit yang masih memenuhi aturan.
3. Untuk graf “rata” (garis tidak saling silang), seringnya maksimal 4 warna sudah cukup.

Cara Praktis Mewarnai (Metode Greedy)

Metode greedy itu simpel dan cepat. Langsung coba langkah ini:

1. Tulis daftar titik (misal: A, B, C, D, E).
2. Mulai dari satu titik (A), kasih warna 1.
3. Pindah ke titik berikutnya:
   • Kalau bertetangga dengan warna 1, kasih warna 2.
   • Kalau aman, tetap pakai warna 1.
4. Ulangi sampai semua titik punya warna dan tidak ada tetangga yang warnanya sama.

Catatan: Urutan titik bisa memengaruhi jumlah warna yang dipakai. Coba beberapa urutan untuk hasil lebih hemat warna.

Latihan Kecil (Bisa Buat Tugas Kelas)

1. Gambar 5 titik: A, B, C, D, E.
2. Hubungkan: A–B, A–C, B–D, C–D, C–E.
3. Warnai dengan metode greedy. Berapa warna minimal yang kamu dapat?

Hint: Coba urutan A, B, C, D, E lalu bandingkan dengan urutan C, A, D, B, E.

Istilah Penting (Versi Singkat)

• Vertex (titik): simpul pada graf.
• Edge (garis): penghubung dua titik.
• Graf planar: graf yang bisa digambar tanpa garis saling silang.
• Bilangan warna minimum: jumlah warna paling sedikit yang berhasil dipakai tanpa ada tetangga sebidang warna.

Tips Biar Makin Paham

• Mulai dari titik yang punya tetangga paling banyak (sering bikin hasil warna lebih hemat).
• Pakai pensil warna berbeda saat latihan di kertas.
• Coba bandingkan beberapa urutan penomoran titik.

Penutup

Pewarnaan graf itu sebenarnya cara “ngakalin” bentrokan dengan warna. Dengan aturan sederhana—tetangga harus beda warna—kita bisa menyusun jadwal ujian, pemakaian lab, atau denah ruang jadi lebih rapi dan efisien. Cocok banget buat anak SMK yang sering ketemu proyek nyata di sekolah.