Minggu Ke XI 11.1 Pewarnaan Peta Pada Contoh 8.4 telah dikemukakan bahwa masalah pewarnaan peta dapat dimodelkan menjadi masalah pewarnaan simpul-simpul graf. Dalam hal ini persoalannya ialah menentukan minimum banyaknya warna agar simpul-simpul yang berikatan mempunyai warna yang berlainan. Banyaknya warna yang minimum ini disebut bilangan kromatik graf tersebut. Sebagai gambaran, misalnya simpul-simpul graf G = (V, E) pada Gambar 11.1 dapat diwarnai dengan tiga, empat, dan lima macam warna. Warna simpul diwakili oleh angka-angka dari 1 sampai dengan 5. Dalam hal ini bilangan kromatik graf G ialah 3, karena sekurang-kurangnya harus ada 3 warna agar simpul-simpul yang berikatan tidak sewarna. 1
4
2
3
2
3
5
3
1
2
1
4
1
2
3
Gambar 11.1 Pada dasarnya graf planar dapat mewakili masalah pewarnaan peta pada bidang datar. Persoalan yang terkenal tentang pewarnaan graf planar ialah bagaimana memperlihatkan bahwa bilangan kromatiknya sama dengan 4, yang dalam bentuk ungkapan lebih populernya ialah persoalan “Dugaan empat warna”. Pada akhir abad ke sembilan belas telah dapat dibuktikan dengan mudah bahwa simpul-simpul graf planar dapat diwarnai dengan lima macam sedemikian sehingga simpul-simpul yang saling berikatan tidak sewarna. Selanjutnya sampai tahun 1976 kita dapat menyangkal dan juga belum dapat membuktikan bahwa pewarnaan semacam itu dapat diselesaikan dengan empat macam warna saja. Pada tahun tersebut Kenneth Appel dan Wolfgang Haken, dua matematikawan dari universitas Illiois di Amerika Serikat, dapat membuktikan (dengan bantuan komputer) dugaan empat warna dengan menyita waktu sekitar 1200 jam-komputer untuk menghasilkan beratus-ratus halaman kertas hasil analisis menyeluruh terhadap sekitar 2000 graf dengan jutaan kemungkinan berikutnya. Contoh 11.1. Pemecahan masalah pewarnaan peta Australia pada Contoh 8.4 disajikan pada Gambar 11.2.
54
Angka-angka pada gambar itu menyatakan kemungkinan penempatan warna, dan masih ada kemungkinan penempatannya yang lain. Dari graf tersebut tampak bahwa dengan empat macam warna kita telah mampu membuat peta Australia sedemikian sehingga dua negara bagian yang saling berbatasan dapat dibedakan dengan jelas. Contoh 11.2. Sekolah “Penuh Harapan” merencanakan seminar pendidikan matematika bagi anak-anak. Ada enem pembicara yang masing-masing akan tampil selama satu jam. Seandainya setiap pembicara tampil dalam kesempatan yang berbeda, kegiatan tersebut akan memakan waktu terlalu lama. Akan tetapi juga tidak diharapkan pembicarapembicara tertentu tampil pada saat yang bersamaan. Pimpinan sekolah menghendaki seminar ini berlangsung tidak lebih dari empat babak. Bagaimanakah kegiatan ini dijadwalkan jika pembicara-pembicara yang sebaiknya tidak tampil pada saat yang bersamaan ditandai dengan “” pada tabel berikut. Nama Pembicara
A
A
B
C
B
D
C
E
F
D
E
Penyelesaian. Masalah ini dapat dimodelkan dengan graf. Setiap pembicara diwakili oleh sebuah simpul. Setiap sisi mencerminkan dua pembicara tidak diharapkan tampil pada saat yang bersamaan. Jadi rumusan persoalan grafnya ialah memperlihatkan bahwa bilangan kromatik grafnya tidak lebih dari 4. Dua visualisasi graf dan kemungkinan penempatan warnanya diperlihatkan pada Gambar 11.3 dan 11.4. E(4)
D • (1) B(3)
E(3)
C(2)
C(1) D • (1)
A(1) B(4)
F(1)
Gambar 11.3
A(2)
F(2)
Gambar 11.4
Angka mewakili warna yang dapat diberikan kepada simpul graf. Warna-warna ini mewakili babak pembicara tampil di forum. Dari gambar itu dapat diamati bahwa simpul-simpul grafnya dapat diwarnai dengan sekurang-kurangnya empat warna. Jadi dapat disimpulkan bahwa kegiatan tersebut dapat diselesaikan dalam empat babak. Pemecahan masalah ini yang disajikan pada Gambar 11.3 dapat ditafsirkan sebagai pembicara A, D, dan F akan tampil pada saat yang bersamaan, yaitu babak pertama,
55
sedangkan ketiga pembicara lainnya akan tampil pada babak-babak sisanya. Akan tetapi kalau ternyata ruangan yang tersedia hanya dua buah, maka salah satu pemecahannya haruslah seperti yang disajikan pada Gambar 11.4: C dan D tampil pada babak pertama, A dan F pada babak kedua, sedangkan E dan B masing-masing pada babak sisanya. Ada sebuah “algoritma” yang sangat bermanfaat, meskipun kurang sempurna (belum tentu menghasilkan solusi optimum), untuk mewarnai peta dengan banyaknya warna yang minimum. Algoritma ini dikenal sebagai algoritma pertama terbesar, karena simpul yang derajatnya terbesar diwarnai terlebih dahulu. Langkah pertamanya ialah mengurutkan derajat simpul-simpul grafnya secara menurun. Hasil pengurutannya belum tentu khas (unik, tunggal) kalau ada simpul-simpul yang berderajat sama. Tandailah simpul berderajat terbesar dengan tanda angka 1. Kemudian tanda ini secara beruntun digunakan untuk menandai setiap simpul lainnya yang tidak berikatan dengan simpul yang bernomor 2. Ulangilah langkah ini dengan warna yang ke dua, ke tiga dan seterusnya sampai semua simpul bertanda. Maka nomor tanda terakhir menyatakan minimum banyaknya warna yang harus disediakan dalam pewarnaan peta itu. Sebagai gambaran, misalnya langkah-langkah pewarnaan peta pada Gambar 11.5, yang diwakili oleh graf pada Gambar 11.6, ialah : 1. Pengurutan derajat simpul : Simpul
E
F
B
A
C
I
D
G
H
Derajat
6
5
4
3
3
3
2
2
2
2. Pewarnaan simpul : Pertama tandailah simpul E dengan angka 1. Telusuri daftar simpul tadi dan amati gambar grafnya, ternyata simpul C adalah simpul pertama yang tidak berikatan dengan E; berilah tanda 1. Tampak bahwa simpul-simpul lainnya berikatan dengan E dan C. Kembali ke daftar simpul, tandai simpul F dengan angka 2, dan juga simpul-simpul A dan H, karena tidak berikatan dengan F. Penelusuran ketiga kalinya terhadap daftar simpul akan menandai simpul B dengan angka 3; lalu tandai pula simpul 1, D, dan G dengan angka 3. Dengan demikian bilangan kromatik graf ini sama dengan 3. A(2)
A
B F
D(3) E
G H
C(1)
C
D E
B(3)
I
H(2)
Gambar 11.5
F(2) I(3)
Gambar 11.6
56
G(3)
Dengan demikian langkah-langkahnya dapat dirangkum dalam bentuk tabel berikut. Simpul E F B A C I D G H
Warna Tahap 2
Tahap 1 1
Tahap 3
2 3 2 1 3 3 3 2
Soal-soal Latihan 1. Jelaskan berapa bilangan kromatik bagi (a) pohon dengan n simpul (b) graf bipartit (c) graf lengkap Kn (d) graf sirkuit 2. Jelaskan berapa bilangan kromatik graf berikut (a) (b)
(c)
(D)
•
•
• •
•
•
3. Berikan contoh graf dengan 15 simpul dan berbilangan kromatik (a) 1 (b) 2 (c) 3 4. Seorang pemimpin perusahaan bermaksud mengirim delapan orang stafnya ke luar kota. Mereka akan diberangkatkan dengan menggunakan mobil. Suasana perjalanan dianggap baik bagi para stafnya apabila staf-staf yang hubungannya akrab saja
57
berangkat dalam kendaraan yang sama. Staf-staf yang hubungannya kurang akrab ditandai dengan “” pada tabel berikut. Nama Staf
P
P
-
Q
R
S
T
-
Q
-
R
U
V
-
S
-
T
W
-
U
-
V
5. Pada enam kota, yang masing-masing dinamai A, B, C, D, E, dan F, akan dibangun stasiun televisi. Jarak antara masing-masing kota disajikan pada tabel di bawah ini (dalam satuan km) Nama Kota
A
B
C
D
E
F
A
0
151
137
98
79
86
0
97
149
92
108
0
77
73
64
0
67
53
0
29
B C D E
Apabila hanya tersedia empat saluran yang berlainan dan diharapkan kota-kota yang jaraknya tidak lebih dari 80 km memiliki saluran berbeda, jelaskan apakah masalah ini ada penyelesaiannya ?. 6. Gunakanlah algoritma pertama terbesar untuk mewarnai peta pada gambar berikut. (a) (b) A B
C F
D
E H
G
F
E
A
C
B
I G
D I
J
H J
58
