Pewarnaan Graf

1. Persoalan Pewarnaan Graf (Graph Coloring)

Ada 3 macam persoalan pewarnaan graf, yaitu pewarnaan titik (vertex coloring), pewarnaan sisi (edge) coloring, dan pewarnaan wilayah (face coloring). Disini kita hanya membahas pewarnaan titik saja, karena pewarnaan sisi maupun wilayah dapat diubah ke persoalan pewarnaan titik.

Pewarnaan titik adalah pemberian warna pada titik-titik di dalam graf, sehingga titik-titik yang adjacent berbeda warna.

Di dalam persoalan pewarnaan graf, kita tidak hanya mewarnai titik-titik dengan warna berbeda untuk titik-titik yang adjacent, namun kita juga ingin menggunakan warna sesedikit mungkin.

Sebagai contoh, perhatikan

Kita bisa saja memberi warna berbeda untuk setiap titik sebagai berikut:

Akan tetapi 8 warna terlalu banyak, padahal 4 warna sudah mencukupi

2. Bilangan Kromatik

A. Definisi

Bilangan kromatik dari graf G, disimbolkan χ(G), adalah banyak warna minimum yang dapat digunakan untuk mewarnai titik-titik pada graf G, sehingga titik-titik yang  adjacent berbeda warna.

B. Beberapa Kasus Khusus

• χ(G) = 1 jika dan hanya jika G graf kosong.

Ini benar karena titik-titik pada graf kosong tidak adjacent, sehingga semua titik boleh diberi warna sama. Begitu juga pewarnaan dengan 1 warna, hanya memungkinkan untuk graf yang titik-titiknya tidak adjacent.

• Bilangan kromatik dari graf lengkap adalah sesuai banyak titiknya, disimbolkan χ(Kₙ) = n.

Setiap dua titik berbeda pada graf lengkap selalu adjacent, sehingga warnanya harus dibedakan. Oleh karena itu, diperlukan warna sama dengan banyak titik.

• Bilangan kromatik dari graf bipartit adalah 2.

Misal G = (V, E) graf bipartit, kita dapat mempartisi V menjadi V₁ dan V₂. Titik-titik di dalam partisi yang sama tidak adjacent sehingga boleh diberi warna yang sama. Oleh karena itu kita cukup menentukan 1 warna untuk V₁ dan 1 warna untuk V₂, ini berarti 2 warna sudah mencukupi.

• Bilangan kromatik graf lingkaran dengan banyak titik genap adalah 2, karena graf lingkaran dengan banyak titik genap merupakan graf bipartit.

• Bilangan kromatik graf lingkaran dengan banyak titik ganjil adalah 3.

Warna pertama diberikan ke titik-titik bernomor ganjil selain titik terakhir (karena titik terakhir adjacent dengan titik nomor 1), warna kedua diberikan ke titik-titik bernomor genap, dan warna ketiga diberikan ke titik terakhir yang adjacent dengan titik sebelumnya yang bernomor genap dan adjacent dengan titik bernomor 1.

• Misal derajat terbesar dari titik-titik pada graf G adalah Δ(G), berlaku hubungan χ(G) ≤ Δ(G) + 1.

Perhatikan bahwa Δ(Kₙ) = n – 1, ingat kembali bahwa χ(Kₙ) = n =  Δ(Kₙ) + 1, sehingga untuk G graf lengkap berlaku χ(G) = Δ(G) + 1.

Sedangkan untuk G bukan graf lengkap, jelas bahwa ada dua titik yang tidak adjacent sehingga boleh diberi warna sama, sehingga berlaku χ(G) ≤ Δ(G). Kecuali untuk G graf lingkaran dengan banyak titik ganjil, yang mana χ(G) = 3 = 2 + 1 = Δ(G) + 1.

Jadi, untuk graf lengkap maupun graf lingkaran bertitik ganjil berlaku χ(G) = Δ(G); sedangkan untuk graf lainnya berlaku χ(G) ≤ Δ(G).

• Bilangan kromatik graf pohon adalah 2.

Misal G merupakan graf pohon, kita dapat menentukan salahsatu titik sebagai akar. Titik-titik pada G hanya adjacent dengan orangtuanya dan anaknya yang berbeda 1 aras, ini berarti titik-titik yang searas tidak adjacent, juga titik-titik yang berbeda 2 aras juga tidak adjacent, sehingga boleh berwarna sama.

Oleh karena itu, kita dapat menentukan 1 warna untuk titik-titik dengan nomor aras ganjil dan 1 warna untuk titik-titik dengan nomor aras genap. Jadi, 2 warna sudah cukup.

• Hubungan subgraf

Jika G' subgraf dari G, maka χ(G') ≤ χ(G).

• Untuk G graf planar, berlaku χ(G) ≤ 4

Bentuk paling sederhana dari graf non-planar bisa berupa K₃,₃ yang cukup diwarnai dengan 2 warna maupun K₅ yang cukup diwarnai dengan 5 warna. Dikarenakan G graf planar, tidak ditemukan subgraf yang isomorfik dengan K₅ maupun yang lebih rumit, sehingga 4 warna selalu cukup untuk mewarnainya. Jadi, bilangan kromatik graf planar tidak lebih dari 4.

C. Kasus Umum

Secara umum, tidak ada algoritma yang efisien untuk mewarnai graf dengan banyak warna minimum. Meskipun demikian, ada algoritma pendekatan (approximate algorithms) untuk menyelesaikan masalah tersebut.

3. Algoritma Welsh-Powell untuk Pewarnaan Graf

Salah satu algoritma yang memberikan solusi yang baik untuk masalah pewarnaan titik (vertex-coloring) adalah algoritma Welsh-Powell. Algoritma ini mungkin tidak selalu memberikan solusi terbaik, tetapi biasanya akan bekerja lebih baik daripada hanya mewarnai simpul-simpul tanpa rencana.

Algoritma Welsh-Powell terdiri dari langkah-langkah berikut:

a. Tentukan derajat untuk setiap titik.

b. Daftar titik-titik berdasarkan urutan derajat yang menurun (Anda dapat memecahkan ikatan dengan cara apa pun yang Anda inginkan).

c. Warnai titik pertama dalam daftar (simpul dengan derajat tertinggi) dengan warna 1.

d. Lanjutkan ke bawah daftar dan warnai setiap titik yang tidak terhubung dengan titik-titik yang sudah diwarnai di atas dengan warna yang sama. Kemudian, coret semua titik yang sudah diwarnai dari daftar.

e. Ulangi proses pada titik-titik yang belum diwarnai dengan warna baru — selalu bekerja dalam urutan derajat yang menurun hingga semua titik telah diwarnai.

Idenya adalah, dengan memulai dari titik-titik yang memiliki derajat tertinggi, Anda akan dapat menangani titik-titik dengan banyak konflik terbesar sesegera mungkin.

Sebagai contoh perhatikan peta berikut:

Dengan menggunakan algoritma Welsh-Powell, lakukan pewarnaan area pada peta tersebut agar setiap area yang bertetangga/berbatasan langsung tidak memiliki warna yang sama dan menggunakan sesedikit mungkin warna.
Untuk mewarnainya, anggap area pada peta sebagai titik pada graf dan berbatasannya area sebagai sisi. Berikut daftar titik-titik beserta adjacency dan derajatnya:

Titik	Adjacent	Derajat	Titik	Adjacent	Derajat
A	B, C, D, H	4	H	A, B, D, E, I, L	6
B	A, C, E, F, H	5	I	E, H, J, L	4
C	A, B, F, G	4	J	E, F, G, I, K, L, M	7
D	A, H, L	3	K	G, J, M	3
E	B, F, H, I, J	5	L	D, H, I, J, M	5
F	B, C, E, G, J	5	M	J, K, L	3
G	C, F, J, K	4

Urutkan dari derajat terbesar, lalu warnai, selama tidak adjacent boleh diberi warna sama, dan beri warna berbeda untuk titik-titik yang adjacent

Titik	Derajat	Warna	Titik	Derajat	Warna
J	7	1	C	4	1
H	6	1	G	4	2
B	5	2	I	4	4
E	5	3	D	3	4
F	5	4	K	3	3
L	5	2	M	3	4
A	4	3

Telah diperoleh data warna untuk setiap titik. Sebagai contoh, berikut gambar peta yang diwarnai:

Secara umum, peta merupakan graf planar, sehingga 4 warna pasti cukup untuk mewarnainya, perhatikan peta Amerika Serikat berikut:

Meski ada sebanyak 50 negara bagian, ternyata 4 warna sudah cukup untuk mewarnainya, karena peta merupakan graf planar.

4. Aplikasi Pewarnaan Graf

Pewarnaan graf memiliki bermacam-macam aplikasi, tidak hanya pewarnaan peta. Contoh aplikasi lainnya diantaranya penjadwalan dan penempatan.

Berikut ini contoh aplikasi pewarnaan graf:

1. Penjadwalan

Sebuah SMA program hybrid ingin membuat jadwal ujian untuk sembilan mata pelajaran di hari yang sama, adapun mata pelajaran lainnya diujikan di hari lain, sehingga jadwalnya tidak akan menabrak hari tersebut.

Tentu saja, jika ada seorang siswa yang mengambil dua dari mata pelajaran tersebut, ujian mereka harus diadakan di slot waktu yang berbeda.

Tabel di bawah ini menunjukkan (dengan tanda silang) pasangan mata pelajaran, berlabel A hingga I, yang memiliki setidaknya satu siswa yang sama.

Sekolah ingin mencari banyak minimum slot waktu yang diperlukan dan bagaimana mengalokasikan mata pelajaran ke waktu yang sesuai. Temukan banyak minimum slot waktu yang dibutuhkan dan alokasi waktu yang sesuai untuk mata pelajaran tersebut.

Solusi:

Kita dapat memisalkan mata pelajaran sebagai titik, tanda silang sebagai adjasensi, dan waktu sebagai warna, sehingga titik-titik yang adjacent berbeda warna.

Mula-mula, susun tabel dengan derajat masing-masing titik:

	A	B	C	D	E	F	G	H	I	Derajat
A		x	x	x						3
B	x			x						2
C	x				x			x	x	4
D	x	x			x	x				4
E			x	x		x	x			4
F				x	x		x			3
G					x	x		x		3
H			x				x		x	3
I			x					x		2

Urutkan dari derajat terbesar, lalu warnai

Titik	Derajat	Warna
C	4	1
D	4	1
E	4	2
A	3	2
F	3	3
G	3	1
H	3	2
B	2	3
I	2	3

Diperlukan 3 slot waktu, dimana waktu 1 untuk mapel C, D, G; waktu 2 untuk mapel A, E, H; dan waktu 3 untuk mapel B, F, I.

2. Peletakan Ikan Hias dalam Aquarium

Pak Feri adalah pedagang ikan hias. Suatu hari Pak Feri membeli 6 jenis ikan hias yang mahal, sebut saja A, B, C, D, E, F. Ikan-ikan tersebut harus ditempatkan pada aquarium dengan teknologi canggih sehingga berbiaya mahal. Ada beberapa ikan yang boleh diletakkan pada aquarium yang sama, tapi ada juga yang tidak boleh karena saling bertengkar. Tabel berikut menunjukkan mana yang boleh di satu aquarium mana yang tidak. Tanda silang menandakan ikan tidak boleh diletakkan pada aquarium yang sama.

	A	B	C	D	E	F
A	-	X	-	X	-	X
B	X	-	-	X	X	-
C	-	-	-	-	X	X
D	X	X	-	-	X	-
E	-	X	X	X	-	-
F	X	-	X	-	-	-

Untuk menghemat biaya, berapa banyak aquarium minimum yang diperlukan untuk menampung ikan hias-ikan hias tersebut? Aturlah peletakan ikan-ikan hias tersebut!

Solusi:

Kita dapat memisalkan ikan hias sebagai titik, tanda silang sebagai adjasensi, dan aquarium sebagai warna, sehingga titik-titik yang adjacent berbeda warna.

Mula-mula, susun tabel dengan derajat masing-masing titik:

	A	B	C	D	E	F	Derajat
A	-	X	-	X	-	X	3
B	X	-	-	X	X	-	3
C	-	-	-	-	X	X	2
D	X	X	-	-	X	-	3
E	-	X	X	X	-	-	3
F	X	-	X	-	-	-	2

Urutkan dari derajat terbesar, lalu warnai

	Derajat	Warna
A	3	1
B	3	2
D	3	3
E	3	1
C	2	3
F	2	2

Jadi, diperlukan 3 aquarium dengan aquarium 1 untuk ikan A dan E, aquarium 2 untuk ikan B dan F, dan aquarium 3 untuk ikan C dan D.

3. Peletakan Bahan Kimia dalam Ruangan

Ada 7 jenis bahan kimia yang perlu disimpan di dalam gudang. Beberapa pasang dari bahan itu tidak dapat disimpan di dalam ruangan yang sama, karena campuran gasnya bersifat eksplosif (mudah meledak). Untuk bahan yang semacam itu perlu dibangun ruang-ruang terpisah yang dilengkapi ventilasi dan penyedot udara keluar yang berlainan. Jika lebih banyak ruang yang dibutuhkan, berarti lebih banyak ongkos yang harus dikeluarkan. Karena itu perlu diketahui berapa banyak minimum ruangan yang diperlukan untuk dapat menyimpan semua bahan kimia dengan aman. Berikut ini adalah daftar pasangan bahan kimia yang tidak dapat disimpan di dalam ruangan yang sama:

Bahan kimia	Tidak dapat disimpan bersama
A	B, D
B	A, D, E, F, G
C	E, G
D	A, F, B
E	B, C, G
F	B, D
G	C, E, B

Gambarkan graf yang menyatakan persoalan (jelaskan arti titik dan sisi yang menghubungkan dua buah titik). Fikirkan termasuk jenis manakah persoalan ini). Kemudian tentukan banyak minimum ruangan yang dibutuhkan untuk menyimpan semua bahan kimia di atas.

Solusi:

Misalkan bahan kimia sebagai titik, tidak dapat disimpan bersama sebagai keberadaan sisi yang menghubungkan dua buah titik, dan ruangan sebagai warna. Perhatikan model graf berikut:

Mula-mula, susun tabel dengan derajat masing-masing titik:

Titik	Adjacent	Derajat
A	B, D	2
B	A, D, E, F, G	5
C	E, G	2
D	A, F, B	3
E	B, C, G	3
F	B, D	2
G	C, E, B	3

Urutkan dari derajat terbesar, lalu warnai

Titik	Derajat	Warna
B	5	1
D	3	2
E	3	2
G	3	3
A	2	3
C	2	1
F	2	3

Jadi, diperlukan 3 ruangan untuk menyimpan semua bahan kimia di atas. Dimana ruang 1 untuk bahan kimia B dan C; ruang 2 untuk bahan kimia D dan E; ruang 3 untuk bahan kimia A, F, dan G.