Pewarnaan Graf — Bilangan Kromatik & Penerapannya

Pewarnaan graf biasanya berarti pewarnaan simpul: memberi warna pada setiap simpul sehingga simpul-simpul yang bertetangga tidak memiliki warna yang sama. Jumlah warna paling sedikit yang berhasil digunakan disebut bilangan kromatik, ditulis $\chi(G)$.

Jika ingin intuisi cepatnya, warna hanyalah label yang bebas konflik. Dua simpul dapat memakai warna yang sama tepat ketika tidak ada sisi di antara keduanya.

Definisi pewarnaan graf dalam satu menit

Dalam pewarnaan yang benar, setiap sisi menghubungkan dua simpul dengan warna berbeda. Itulah seluruh aturannya.

Jadi jika $\chi(G)=3$, dua fakta berikut benar secara bersamaan:

• ada pewarnaan yang benar dengan $3$ warna
• tidak ada pewarnaan yang benar hanya dengan $2$ warna

Itulah sebabnya bilangan kromatik adalah nilai minimum, bukan sekadar jumlah warna yang kebetulan Anda pakai pada satu gambar.

Kecuali disebutkan lain, pewarnaan graf dalam mata kuliah pengantar berarti mewarnai simpul-simpul dari graf sederhana tak berarah. Pewarnaan sisi adalah masalah yang berbeda dengan aturan yang berbeda pula.

Apa yang sebenarnya diukur oleh bilangan kromatik

Nama warna tidak penting. Anda bisa memakai merah, biru, dan hijau, atau label $1$, $2$, dan $3$.

Yang penting adalah pengelompokannya. Semua simpul dengan warna yang sama membentuk himpunan yang tidak memiliki sisi di dalamnya, sehingga kelompok itu tidak memiliki konflik.

Sudut pandang inilah yang membuat pewarnaan graf berguna dalam masalah penjadwalan dan alokasi. Satu warna sering berarti "item-item ini bisa berbagi slot yang sama."

Contoh dikerjakan: mengapa siklus 5 membutuhkan 3 warna

Perhatikan graf siklus $C_5$ dengan sisi $AB, BC, CD, DE,$ dan $EA$.

Coba $2$ warna terlebih dahulu. Beri $A$ warna $1$ dan $B$ warna $2$. Lalu pewarnaannya menjadi terpaksa mengelilingi siklus:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Sekarang perhatikan $E$. Simpul ini bertetangga dengan $D$ dan $A$, jadi ia tidak bisa memakai warna $2$ karena $D$, dan tidak bisa memakai warna $1$ karena $A$.

Jadi $2$ warna gagal.

Namun, $3$ warna berhasil. Salah satu pewarnaan yang benar adalah

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

sehingga

$$\chi(C_5)=3$$

Contoh ini layak diingat karena menunjukkan pola penting: untuk graf siklus, siklus genap dapat diwarnai dengan $2$ warna, tetapi siklus ganjil membutuhkan $3$.

Cara menalar pewarnaan graf pada graf kecil

Ada dua pemeriksaan cepat yang membantu.

Pertama, cari konflik yang terpaksa muncul. Pada contoh di atas, pergantian dua warna secara selang-seling di sepanjang siklus ganjil membuat simpul terakhir berbenturan dengan kedua pilihan warna yang tersedia.

Kedua, cari batas bawah. Jika sebuah graf memuat segitiga, maka ketiga simpul itu saling bertetangga sepasang demi sepasang, sehingga mereka sudah membutuhkan $3$ warna berbeda. Ini tidak selalu memberi jawaban tepatnya, tetapi membuktikan bahwa bilangan kromatik setidaknya $3$.

Kesalahan umum dalam soal pewarnaan graf

Salah satu kesalahan umum adalah menganggap simpul-simpul bertetangga hanya karena digambar berdekatan. Hanya sisi yang benar-benar ada yang menciptakan batasan pewarnaan.

Kesalahan lain adalah menganggap setiap simpul membutuhkan warnanya sendiri. Simpul yang tidak bertetangga dapat memakai ulang warna yang sama, dan pewarnaan yang efisien biasanya memakai ulang warna sebanyak mungkin.

Mahasiswa juga kadang mencampuradukkan pewarnaan simpul dan pewarnaan sisi. Pada halaman ini, aturannya adalah tentang simpul yang bertetangga, bukan sisi yang bertetangga.

Kesalahan terakhir adalah melaporkan jumlah warna yang kebetulan Anda gunakan, bukan jumlah minimum yang diperlukan. Menggunakan $4$ warna pada suatu graf tidak membuktikan bahwa bilangan kromatiknya adalah $4$.

Di mana pewarnaan graf digunakan

Penerapan yang umum adalah penjadwalan. Misalkan setiap simpul adalah ujian, dan sebuah sisi berarti dua ujian memiliki mahasiswa yang sama sehingga tidak bisa dijadwalkan pada waktu yang sama. Maka satu warna dapat mewakili satu slot waktu.

Dalam model itu, bilangan kromatik memberi tahu jumlah slot waktu paling sedikit yang mungkin. Jika $\chi(G)=4$, maka tidak ada jadwal valid yang hanya memakai $3$ slot.

Gagasan yang sama juga muncul pada pewarnaan peta, ketika wilayah yang bertetangga harus berbeda, dan dalam perancangan compiler, ketika variabel yang dibutuhkan secara bersamaan tidak dapat berbagi register yang sama.

Coba soal pewarnaan graf serupa

Gambarlah graf dengan simpul $P,Q,R,S,T$ dan sisi $PQ, QR, RS, ST, TP,$ dan $PR$.

Mulailah dengan mencari segitiga untuk mendapatkan batas bawah. Lalu cobalah mewarnai graf dengan sesedikit mungkin warna dan periksa apakah ada simpul bertetangga yang warnanya sama. Jika ingin melangkah lebih jauh, coba buat versi Anda sendiri pada graf yang lebih besar dan lihat apakah Anda bisa membuktikan bahwa pewarnaan Anda memang minimal, bukan sekadar valid.