Modul 6
Pewarnaan Graph
Prof.
Dr. H. Nanang Priatna, M.Pd.
UNIVERSITAS PENDIDIKAN INDONESIA
M
|
odul 6 ini merupakan modul
terakhir dari modul mata kuliah Teori Graph. Modul-modul sebelumnya membahas
tentang Pengetahuan Dasar Teori Graph, Representasi Graph dan Beberapa Graph
Khusus, Lintasan dan Keterhubungan, Pohon, dan Planaritas.
Pada akhir abad kesembilan
belas, seorang kepala sekolah memberikan
soal yang sangat menantang kepada murid-muridnya. Soal itu sebagai berikut:
“Tunjukkan bahwa semua peta hanya memerlukan empat warna, sehingga
negara-negara atau propinsi-propinsi yang bertetangga mendapat warna yang
berbeda”.
Dia mengatakan hanya mau
menerima pembuktian tidak lebih dari 30 baris tulisan dan satu halaman diagram.
Tampaknya soal ini sederhana sekali, tetapi sebenarnya tidak demikian. Soal ini
menjadi masalah besar di dunia matematika, yang kemudian terkenal dengan nama Konjektur
Empat Warna. Baru pada Tahun 1976 ditemukan penyelesaian masalah ini. Pada
tahun tersebut Kenneth Appel dan Wolfgang Haken, dua matematikawan dari
Universitas Illionis di Amerika Serikat, dapat membuktikan (dengan bantuan
komputer) dugaan empat warna dengan menyita waktu sekitar 1.200 jam komputer
untuk menghasilkan beratus-ratus halaman kertas hasil analisis menyeluruh
terhadap sekitar 2.000 graph dengan jutaan kemungkinan bentuknya.
Salah satu cara yang
digunakan adalah menggunakan graph yang titiknya menunjukkan propinsi dan garis
menunjukkan hubungan dua propinsi itu sebagai tetangga.
Konsep-konsep yang dikaji
dan diuraikan di dalam pembahasan modul ini terdiri atas topik-topik yang
menyangkut pewarnaan titik, pewarnaan sisi (pewarnaan peta), dan pewarnaan
garis.
Melalui uraian dan
pembahasan dalam modul ini, diharapkan dapat menunjang wawasan dan pengetahuan
Anda dalam melaksanakan tugas. Disamping itu Anda diharapkan dapat
menggunakannya dalam kehidupan sehari-hari serta dapat mengajarkannya dengan
pendekatan tertentu yang sesuai. Secara khusus tujuan dari penyajian modul ini
adalah agar Anda dapat:
a.
menjelaskan
pewarnaan titik suatu graph,
b.
menjelaskan
pewarnaan sisi (pewarnaan peta),
c.
menjelaskan
pewarnaan garis suatu graph,
d.
menentukan
bilangan khromatik suatu graph,
e.
menjelaskan
algoritma Welsh dan Powell dalam pewarnaan graph,
f.
menjelaskan
teori-teori pewarnaan graph,
g.
menerapkan
analisis pewarnaan graph dalam kehidupan sehari-hari.
Kegiatan Belajar 1
Pewarnaan Titik Suatu Graph
A
|
gar Anda lebih memahami
pengertian tentang pewarnaan titik suatu graph, perhatikan contoh-contoh serta
penjelasan berikut ini.
Contoh
1
Andaikan sebuah pabrik
kimia ingin mengirimkan hasil produksinya dengan menggunakan kereta api. Sesuai
dengan ketentuan yang ada, tidak semua zat kimia ini dapat dimuat dalam satu
kereta, karena kemungkinan bercampurnya zat itu yang dapat menyebabkan
terjadinya reaksi berupa ledakan yang membahayakan. Bagaimana zat-zat kimia ini
dapat dikirim? Dengan maksud meminimumkan biaya, pabrik itu ingin menggunakan
gerbong kereta api sesedikit mungkin. Berapa banyaknya gerbong kereta api itu?
Pada Contoh di atas ada
objek (hasil zat kimia) dan ada
keterhubungan (tidak dapat dimuat dalam satu gerbong kereta) di antara objek
itu. Karena hal ini merupakan ide dasar suatu graph, maka dapat disajikan dalam bentuk graph. Pada contoh di atas, titik-titiknya
adalah zat kimia dan sisinya menghubungkan zat-zat kimia yang tidak dapat
diangkut dalam gerbong kereta yang sama.
Sebagai ilustrasi,
diasumsikan bahwa pada contoh 1 ada enam zat kimia P1, P2, P3, P4, P5, dan P6. Serta P1 dengan P2, P3, atau P4 tidak dapat
diangkut dalam kereta yang sama, juga P2 dengan P3 atau P5, P3 dengan P4, dan P5 dengan P6. Graph yang menyajikan hal ini dapat dilihat pada
Gambar 6.1, yang titik-titiknya menunjukkan enam zat kimia dan sisinya
menghubungkan pasangan zat kimia yang tidak
dapat dimuat dalam gerbong kereta yang sama.
Berapa banyak minimum
gerbong kereta yang diperlukan? Dalam graph pada Gambar 6.1, zat kimia yang
disajikan dengan titik berdekatan harus dimuat dalam gerbong kereta yang tidak
sama. Misal: zat P1 dan P2 berdekatan, misalkan zat P1 diletakkan
pada gerbong kereta 1, kereta lain diperlukan untuk memuat P2, katakan
gerbong kereta 2. Karena P3 berdekatan P1 dan P2, maka diperlukan gerbong kereta lain lagi untuk P3, katakan
gerbong kereta 3. Tetapi tidak diperlukan gerbong kereta lain lagi untuk P4, gerbong
kereta 2 dapat digunakan lagi. Demikian pula halnya, tidak diperlukan gerbong
kereta lain lagi untuk P5, karena gerbong kereta 1 atau 3 dapat digunakan lagi.
Misalnya dipilih gerbong kereta 1, maka untuk P6 dipilih gerbong kereta 2 atau 3, katakan
gerbong kereta 2. Graph pada Gambar 6.2 menunjukkan bagaimana titik-titik itu
diberi nama (label) sehingga zat kimia yang tidak dapat berada bersama, dimuat
dalam gerbong kereta berbeda. Juga karena P1, P2, dan P3 saling berdekatan, maka paling sedikit harus
digunakan tiga gerbong kereta berbeda. Sehingga banyak minimum gerbong kereta
yang harus digunakan ada tiga.
Apa yang telah dilakukan
di atas, adalah memberi label pada titik-titik graph sehingga titik yang
berdekatan mendapatkan label yang berbeda. Ide ini sering terjadi dalam teori
graph, dan label ini disebut warna. Mewarnai sebuah graph berarti
memberi warna pada setiap titik graph, sedemikian hingga titik yang berdekatan
mendapat warna berbeda. Menanyakan banyak minimum gerbong kereta yang
diperlukan pada contoh 1 adalah sama seperti menanyakan banyak minimum warna
yang diperlukan untuk mewarnai graph pada Gambar 6.1, dengan warna mewakili
gerbong kereta.
Bila suatu graph G dapat diwarnai minimal dengan n warna,
maka G dikatakan memiliki bilangan khromatik n. Jadi graph G pada Gambar 6.1 memiliki bilangan khromatik
3.
Contoh
2
Graph pada gambar 6.3 (a)
memiliki bilangan khromatik 2 karena titik V1, V3, dan V5 dapat diwarnai dengan satu warna (misalkan
merah) dan tiga titik lainnya dengan warna kedua (misalkan biru), seperti yang
terlihat pada Gambar 6.3 (b). Secara umum, jika suatu sikel memiliki titik yang
banyaknya genap, maka sikel itu dapat diwarnai menggunakan dua warna.
Contoh
3
Bila suatu sikel memiliki
titik yang banyaknya ganjil, seperti pada Gambar 6.4 (a), maka harus digunakan
tiga warna. Bila dicoba menggunakan warna itu secara berselang seperti pada
Gambar 6.3, warna merah untuk titik V1 dan V3 serta warna biru tidak dapat digunakan lagi
untuk V5.
Penggunaan tiga warna untuk mewarna sikel yang banyak titiknya ganjil
diilustrasikan pada Gambar 6.4 (b).
|
|||||||||||||||
|
|||||||||||||||
|
|||||||||||||||
|
|
||||||||||||||
|
|||||||||||||||
|
|
||||||||||||||
|
|
||||||||||||||
Dalam graph lengkap Kn, setiap titik
saling berdekatan dengan titik lainnya. Jadi, kurang dari n warna tidak cukup
untuk mewarnai graph itu. Oleh karena itu, graph lengkap Kn memiliki bilangan khromatik n.
Contoh
4
Graph pada Gambar 6.5 (a)
dapat diwarnai dengan menggunakan dua warna, seperti terlihat pada Gambar 6.5
(b).
Gambar 6.5
Contoh
5
Graph pada Gambar 6.6
memiliki bilangan khromatik 2 karena titik di sebelah kiri dapat diwarnai
dengan menggunakan warna pertama dan titik di sebelah kanan dapat diwarnai dengan
menggunakan warna kedua.
Secara umum, sangat sulit
untuk menentukan banyak minimum warna yang diperlukan untuk mewarna graph.
Salah satunya dengan mendaftar semua cara mewarna (yang berbeda) titik-titik
graph, kemudian memeriksa setiap cara itu untuk menentukan mana yang
menggunakan banyak warna minimum. Sayangnya, walaupun titik graph tidak
seberapa banyak, dan kita menggunakan komputer super, proses ini sangat memakan
waktu, bahkan sampai berabad-abad.
Tetapi, ada beberapa cara
yang berhasil diperoleh untuk dapat menunjukkan bilangan khromatik suatu graph.
Misal, seperti yang terlihat pada Contoh
3, sikel yang panjangnya ganjil memiliki
bilangan khromatik 3. Jadi setiap graph yang memiliki sikel jenis ini
membutuhkan minimum 3 warna. Graph pada Gambar 6.4 merupakan salah satu
contohnya. Bila sikel pada suatu graph panjangnya genap, maka 2
warna sudah cukup.
Teorema 1
Suatu graph G tidak memiliki sikel yang panjangnya
ganjil, jika dan hanya jika G dapat diwarnai dengan 2 warna.
Bukti
Seperti uraian di atas,
bila G memiliki sikel yang panjangnya ganjil, maka pewarna G membutuhkan paling
sedikit 3 warna.
Sekarang andaikan G tidak
memiliki sikel yang panjangnya ganjil. Pilih suatu titik V yang diberi warna
merah. Kemudian pada setiap titik yang berdekatan dengan V diberi warna biru.
Sekarang, pada titik-titik yang berdekatan dengan titik yang baru diberi warna
biru itu, diberi warna merah. Dapatkah salah satu dari titik yang berwarna
merah ini, katakan titik W, berdekatan dengan titik V yang juga berwarna merah?
Diagram pada Gambar 6.7 mengilustrasikan
situasi ini.
Terlihat bahwa jika V dan
W berdekatan, maka akan ada sikel yang panjangnya 3. Dengan demikian, setiap
titik lain yang baru saja diwarnai warna merah
tidak berdekatan dengan titik yang berwarna merah, karena jika tidak demikian
berarti ada sikel yang panjangnya ganjil. Berikutnya, titik yang berdekatan
dengan yang baru saja diwarnai warna merah
diberi warna biru. Hal ini diperlihatkan pada Gambar 6.8.
Kemudian, jika dua titik
yang diwarnai biru terletak berdekatan, maka ada sikel yang panjangnya ganjil.
Kemudian dilanjutkan dengan mewarnai merah titik yang berdekatan dengan titik
yang baru diwarnai biru. Seperti sebelumnya, tidak ada titik yang baru diwarnai
merah dapat terletak berdekatan dengan titik yang telah berwarna merah. Proses
ini diulangi sampai tidak ada titik yang belum mendapat warna terletak
berdekatan dengan titik yang telah diwarnai.
Jika graphnya tidak
terhubung, maka akan ada titik yang tidak berdekatan dengan titik yang telah
berwarna, sehingga belum mendapat warna. Untuk titik-titik seperti itu, proses
di atas diulang lagi dengan menggunakan warna merah dan biru. Akhirnya semua
titik dapat diwarnai dengan warna merah dan biru.
Contoh
6
Pada graph dalam Gambar
6.9 (a), proses pewarnaan di atas dimulai dengan memilih titik V dan
mewarnainya dengan warna merah. Karena F, B, dan A terletak berdekatan dengan
V, maka warna biru diberikan pada titik itu. Titik yang belum mendapat warna
dan terletak berdekatan dengan titik biru itu adalah C, D, dan E, sehingga
diberi warna merah. Akhirnya, titik G adalah titik yang belum diwarnai dan
terletak berdekatan dengan titik merah, sehingga diwarnai biru. Sekarang, X
adalah titik belum diwarnai yang terletak tidak berdekatan dengan titik yang
berwarna, sehingga X diberi warna merah. Kemudian Y diberi warna biru, serta
akhirnya Z diberi warna merah. Lihat Gambar 6.9 (b).
Teorema berikut ini
memberikan batas atas pada banyak warna yang diperlukan untuk mewarna sebuah
graph.
Teorema 2
Bilangan khromatik dari graph G tidak dapat lebih satu
dari derajat maksimum titik-titik dari G.
Bukti
Misalkan k adalah derajat
maksimum titik dari G. Akan ditunjukkan bahwa G dapat diwarnai dengan
menggunakan k+1 warna C0, ..., Ck. Mula-mula titik V dipilih dan diberi warna C0. Kemudian,
beberapa titik W lain dipilih. Karena paling banyak ada k titik yang berdekatan
dengan W dan ada paling sedikit k + 1 warna yang tersedia, maka paling sedikit
ada satu warna (dapat lebih banyak) yang belum digunakan untuk mewarnai titik
yang berdekatan dengan W. Pilih warna itu. Proses ini dapat dilanjutkan sampai
semua titik dari G mendapat warna.
Contoh
7
Proses yang digambarkan
pada teorema 2 dapat menggunakan lebih banyak warna daripada yang sebenarnya
diperlukan. Graph pada Gambar
6.10 memiliki titik berderajat 4, yang merupakan derajat maksimumnya, sehingga
dengan teorema 2 di atas, graph itu dapat diwarnai dengan menggunakan 4 + 1 = 5
warna. Tetapi, dengan menggunakan prosedur yang digambarkan pada teorema 1,
graph itu dapat diwarnai dengan menggunakan 2 warna.
Gambar 6.10
Berikut ini akan diuraikan
algoritma tambahan, yang ditemukan Welsh dan Powell, untuk pewarnaan
titik-titik dari suatu graph.
Algoritma Welsh
dan Powell
Algoritma ini memberikan
cara mewarnai sebuah graph dengan memberi label titik-titiknya sesuai dengan
derajatnya.
Langkah
1 (melabel titik dengan derajatnya).
Label titik V1, V2, ..., Vn sedemikian
hingga derajat (V1) > derajat (V2) > ... >
derajat (Vn).
Langkah 2 (warnai titik belum berwarna pertama
dari titik-titik belum berwarna yang berdekatan dengan titik itu).
Berikan warna yang belum digunakan pada titik
belum berwarna yang pertama pada daftar titik itu. Lakukan hal itu pada
semua titik dalam daftar secara terurut, berikan warna baru ini pada setiap
titik yang tidak berdekatan dengan setiap titik lain yang telah diwarnai ini.
Langkah 3 (graphnya
telah diwarnai?). Jika beberapa titiknya belum berwarna, maka kembalilah ke
langkah 2.
Langkah 4 (selesai).
Pewarnaan graph telah dilakukan.
Contoh
8
Untuk
graph pada Gambar 6.11 (a), titik F memiliki derajat terbesar, yaitu 4 sehingga
F diberi label V1. Titik A, D, dan E berderajat 3 sehingga diberi label V2, V3, dan V4 secara random. Demikian pula titik B dan C
yang berderajat 2 diberi label V5 dan V6. Titik G yang
merupakan satu-satunya titik yang tersisa, diberi label V7. Hal ini diperlihatkan pada
Gambar 6.11 (b).
Gambar 6.11
Penyajian dalam bentuk
daftar berdekatan sangat mudah digunakan dengan algoritma Welsh dan Powell ini.
Untuk graph pada Gambar 6.11 (b), penyajian daftar berdekatannya adalah
sebagai berikut.
V1 : V2, V3, V4, V5, V7
V2 : V1, V3, V5
V3 : V1, V2, V4
V4 : V1, V3, V6
V5 : V1, V2, V6
V6 : V4, V5
V7 : V1
Pada Algoritma Welsh dan
Powell ini, titik belum berwarna pertama
dalam daftar adalah V1 yang diberi warna
merah. Kemudian dicari titik berikut yang tidak berdekatan dengan V1 pada daftar,
yaitu titik di bawah V1 yang tidak
mengikuti V1. Diperoleh titik V6, yang diberi warna merah. Dilanjutkan dengan
melihat bagian bahwa daftar untuk mencari titik berikutnya yang tidak
berdekatan dengan V1 maupun V6. Karena titik
seperti itu tidak ada, maka kembali dilihat bagian atas daftar dan ditentukan
lagi titik belum berwarna yang pertama,
yaitu V2,
yang diberi warna biru. Kemudian, titik belum berwarna berikutnya ditentukan
yang tidak berdekatan dengan V2. Diperoleh titik V4 dan diberi warna biru. Cara ini dilanjutkan
lagi, dan diperoleh titik V7 yang belum
berwarna dan tidak berdekatan dengan V2 maupun V4, sehingga V7 diwarnai biru, bagian atas daftar dilihat
kembali dan ditentukan titik belum berwarna berikutnya, yaitu V3, yang diberi
warna hijau. Karena V5 belum diwarnai dan
tidak berdekatan dengan V3, yang diberi warna hijau. Dengan demikian maka
graph pada Gambar 11 (b) dapat diwarnai dengan tiga warna.
Penyajian daftar
berdekatan membuat algoritma Welsh dan Powell mudah digunakan, karena titiknya
dapat ditandai ketika diwarnai, sehingga tinggal memperhatikan titik belum
berwarna sisanya dalam proses perwarnaan itu.
Silakan Anda istirahat
sejenak!
Setelah Anda cukup
istirahat, ingat-ingat kembali dan
pahami benar uraian di atas. Kemudian kerjakanlah soal-soal berikut ini sebagai
latihan.
 |
1) Perhatikan tabel 1 matriks siswa dan bidang studi berikut ini.
C
A
|
B
|
C
|
D
|
E
|
|
  1 |
0
|
1
|
0
|
0
|
1
|
2
|
0
|
1
|
0
|
1
|
0
|
3
|
0
|
0
|
1
|
1
|
0
|
4
|
1
|
1
|
0
|
0
|
0
|
5
|
0
|
1
|
0
|
1
|
0
|
6
|
0
|
1
|
0
|
0
|
0
|
7
|
1
|
0
|
1
|
0
|
0
|
8
|
0
|
0
|
1
|
1
|
0
|
Tabel 6.1 menunjukkan matriks tentang lima bidang studi (di
label dengan abjad) yang dipilih oleh delapan orang siswa (di label dengan
angka). Angka 1 diisikan sebagai elemen (i,j) matriks itu, jika siswa i memilih
bidang studi j. Sedangkan angka 0 diisikan sebagai elemen (i,j), jika siswa i
tidak memilih bidang studi j.
Contoh: siswa 1 memilih bidang studi B dan E karena elemen
(1,B) dan (1,E) adalah 1.
Berdasarkan Tabel 6.1, tentukan banyak jadwal ujian yang
dapat dibuat sedemikian rupa sehingga semua siswa dapat mengikuti ujian bidang
studi itu tanpa ada kesulitan waktu (kesulitan terjadi jika ada siswa yang harus mengikuti ujian dua bidang studi
atau lebih pada waktu yang bersamaan).
 |
 |
||||||
 |
 |
||||||
 |
 |
||||||
 |
|||||||||||||
 |
 |
||||||||||||
 |
 |
 |
|||||||||||
 |
|||||||||||||
 |
|||||||||||||
 |
|||||||||||||
4) Ada 6 jenis zat kimia yang perlu disimpan di gudang. Beberapa
pasang dari zat itu tidak dapat disimpan di tempat yang sama, karena campuran
gasnya bersifat eksplosif. Untuk zat-zat semacam itu perlu dibangun ruang-ruang
terpisah yang dilengkapi ventilasi dan penyedot udara ke luar yang berlainan.
Jika lebih banyak ruang dibutuhkan, berarti lebih banyak biaya yang
dikeluarkan. Karena itu perlu diketahui berapa banyak minimum ruangan yang diperlukan
untuk dapat menyimpan semua zat kimia itu dengan aman.
Berikut ini adalah daftar pasangan zat kimia yang tidak dapat
disimpan di tempat yang sama.
Zat
kimia
|
tidak dapat bersama dengan zat
kimia
|
A
B
C
D
E
F
|
B,
D
A,
D, E, F
E
A,
B, F
B,
C
B,
D
|
Berapa banyak minimum ruangan berbeda untuk menyimpan semua
zat kimia itu secara aman?
Periksa dan teliti kembali
jawaban Anda, sekarang cocokkan jawabannya dengan kunci jawaban berikut ini.
Petunjuk Jawaban Latihan
1) Penyelesaian masalah membuat jadwal ujian ini sebenarnya
ekuivalen dengan masalah mencari bilangan khromatik suatu graph. Yang perlu
diingat adalah ujian dan bidang studi dapat dijadwalkan pada waktu yang sama
jika tidak ada siswa yang sama yang mengikuti ujian dua bidang studi itu.
Penjadwalan ujian itu dapat digambarkan sebagai sebuah graph,
dan setiap bidang studi ditunjukkan sebagai titiknya. Dua titik dihubungkan dengan sebuah garis
jika ada siswa yang memiliki kedua bidang studi itu. Sehingga dapat ditafsirkan
bahwa jika dua titik dihubungkan oleh garis maka ujian dua bidang studi itu
tidak dapat dilakukan bersamaan, karena akan ada siswa yang mendapat kesulitan.
Diberikan warna yang berbeda untuk titik-titik semacam itu yang menunjukkan
bahwa waktu ujiannya berbeda.
Kita gambar masalah graph di atas
Jadwalnya perlu dibuat sesedikit mungkin untuk memudahkan
pelaksanaannya. Sehingga perlu kita tentukan bilangan khromatik graph di atas.
Ternyata bilangan khromatiknya 2. Ujian bidang studi A, E,
dan D dapat dilaksanakan bersamaan, sedangkan ujian bidang studi B dan C dapat
dilakukan bersama tetapi pada waktu yang berbeda dengan ujian bidang studi A,
E, dan D.
2) Titik pada graph tersebut dapat diwarnai sebagai berikut.
V5 merah
V3 biru
V2 dan V4 kuning
V1 hijau
V6 putih
Karena graph itu dapat diwarnai minimal dengan 5 warna, maka
bilangan khromatiknya adalah 5.
3) Titik-titik H, B, dan E warna merah (1).
Titik-titik I, F, dan
C warna biru (2).
Titik-titik D, A, dan G warna kuning (3).
Bilangan khromatiknya adalah 3.
4) Soal tersebut dapat dibuat graphnya dengan titik menunjukkan “zat
kimia” dan garis menunjukkan “tidak dapat bersama dengan zat kimia”.
Gambar graphnya adalah sebagai berikut.
Berikut ini tabel yang menunjukkan hubungan antara titik, derajat
titik, dan warna.
Titik
|
B
|
D
|
A
|
F
|
E
|
C
|
Derajat titik
|
4
|
3
|
2
|
2
|
2
|
1
|
Warna
|
(1)
|
(2)
|
(3)
|
(3)
|
(2)
|
(1)
|
Bilangan khromatiknya 3
Jadi, banyak minimum ruang berbeda atau terpisah yang
dibutuhkan ada 3, yaitu:
ruang 1 menyimpan zat B dan C
ruang 2 menyimpan zat D dan E
ruang 3 menyimpan zat A dan F
Mewarna sebuah graph berarti
memberikan warna pada setiap titik graph itu sedemikian hingga titik yang
berdekatan mendapat warna berbeda.
Bila suatu graph G dapat
diwarnai minimal dengan n warna, maka G dikatakan memiliki bilangan khromatik
n.
Untuk
mewarna sebuah graph dengan memberi label titik-titiknya, sesuai dengan
derajatnya, dikemukakan oleh Welsh dan Powell dengan langkah-langkah sebagai
berikut.
1. Beri label titik V1, V2, ..., Vn sedemikian
hingga derajat (V1) > derajat (V2)
> ... > derajat (Vn).
2. Tandailah titik berderajat terbesar dengan tanda angka 1.
Kemudian tanda ini secara berurutan digunakan untuk menandai setiap titik
lainnya yang tidak berdekatan dengan titik-titik yang telah bernomor sama.
3. Ulangilah langkah 2 dengan warna kedua, ketiga, dan seterusnya
sampai semua titik bertanda.
 |
1) Bilangan khromatik gambar graph di bawah ini adalah ....
A. 5
B. 4
C. 3
D. 2
2) Jika graph G berkhromatik 5 dan memiliki 5 titik, maka G adalah
....
A. graph nol
B. graph lengkap
C. graph bipartit
D. graph yang memiliki 5 sisi
3) Bilangan khromatik graph di bawah ini adalah ....
A. 2
B. 3
C. 4
D. 12
4) Jika diketahui bahwa G berkhromatik 1, maka G hanya memiliki ....
A. satu titik
B. satu sisi
C. sisi
D. titik
5) Graph di bawah ini mempunyai bilangan khromatik ....
A. 5
B. 3
C. 2
D. 1
6) Bilangan khromatik dari graph bipartit lengkap K3,5 adalah ....
A. 2
B. 3
C. 4
D. 5
7) Bilangan khromatik dari graph di bawah ini adalah ....
A. 6
B. 5
C. 3
D. 2
8) Bilangan khromatik dari graph sikel C8 adalah ....
A. 2
B. 4
C. 6
D. 8
9) Bilangan khromatik dari graph lengkap K7 adalah ....
A. 1
B. 3
C. 5
D. 7
10) Bilangan khromatik dari graph sikel C15 adalah ....
A. 2
B. 3
C. 10
D. 15
Cocokkanlah jawaban Anda
dengan Kunci Jawaban Tes Formatif 1 yang terdapat di bagian akhir modul ini.
Hitunglah jawaban yang benar. Kemudian, gunakan rumus berikut untuk mengetahui
tingkat penguasaan Anda terhadap materi Kegiatan Belajar 1.
Rumus:
 |
Arti tingkat penguasaan yang
Anda capai:
90 - 100% = baik sekali
80 - 89% =
baik
70 - 79% =
cukup
< 70%
= kurang
Apabila mencapai tingkat
penguasaan 80% atau lebih, Anda dapat meneruskan dengan Kegiatan Belajar 2. Bagus! Jika masih di bawah 80%, Anda
harus mengulangi materi Kegiatan Belajar 1, terutama bagian yang belum
dikuasai.
Kegiatan Belajar 2
Pewarnaan Peta dan
Pewarnaan Garis
S
|
ebuah atlas akan sangat mudah
dipahami kalau masing-masing daerah yang saling berbatasan mempunyai warna yang
berlainan. Suatu masalah yang menarik ialah menentukan banyaknya minimum warna
yang harus disediakan agar tujuan tersebut terwujud. Misalnya untuk mewarnai
peta negara tetangga kita Australia seperti diperlihatkan pada Gambar 6.12.
Pewarnaan peta sama dengan pewarnaan titik-titik graph dari gambar peta
tersebut sedemikian hingga tidak ada dua titik berdekatan yang mendapat warna
sama.
Dalam hal ini
negara-negara bagiannya dan lautan yang mengelilinginya diwakili oleh titik-titik.
Selanjutnya pasangan titik yang mewakili daerah-daerah yang saling berbatasan
dihubungkan dengan sebuah sisi, sehingga model graphnya seperti tampak pada
Gambar 6.13. Oleh karena itu derajat suatu titik mencerminkan banyaknya
perbatasan yang mengelilingi daerah yang diwakili titik itu. Jadi rumusan
persoalan graphnya ialah mewarnai semua titik graph sedemikian hingga
titik-titik yang terhubung oleh sisi mempunyai warna berbeda satu sama lain.
Jadi dapat disimpulkan
bahwa langkah-langkah yang dilakukan dalam pemodelan dengan graph ialah
menentukan:
1. Objek apa yang akan dikonversikan sebagai titik graph?
2.
Hubungan apa
yang dicerminkan oleh sisi graph? Pasangan titik apa saja yang harus
dihubungkan oleh sisi?
3.
Merumuskan
masalah nyata dalam bahasa teori graph.
Angka-angka pada Gambar
6.13 menyatakan kemungkinan penempatan warna, dan masih ada pula kemungkinan
penempatannya yang lain. Dari graph tersebut tampak bahwa dengan empat macam
warna kita telah mampu membuat peta Australia sedemikian hingga dua negara
bagian yang saling berbatasan dapat dibedakan dengan jelas.
1. Pewarnaan Peta
Contoh
1
Warnai peta pada Gambar
6.14, kemudian tentukan bilangan khromatiknya.
Jawab
Peta pada Gambar 6.14,
dapat dilukiskan bentuk graphnya seperti pada Gambar 6.15 berikut ini.
1.
Pengurutan
derajat titik
Titik
|
E
|
F
|
B
|
A
|
C
|
I
|
D
|
G
|
H
|
Derajat titik
|
6
|
5
|
4
|
3
|
3
|
3
|
2
|
2
|
2
|
2. Pewarnaan titik
Pertama tandailah
titik E dengan angka 1. Telusuri daftar titik tadi dan amati gambar graphnya,
ternyata titik C adalah titik pertama yang tidak berdekatan dengan E. Kembali
ke daftar titik, tandai titik F dengan angka 2, dan juga titik A dan H, karena
tidak berdekatan dengan F. Penelusuran ketiga kalinya terhadap daftar titik
akan menandai titik B dengan angka 3, lalu tandai pula titik I, D, dan G dengan
angka 3. Dengan demikian bilangan khromatik graph tersebut adalah 3.
Langkah-langkah tersebut dirangkum dalam bentuk tabel berikut.
Setiap graph G memiliki sebuah subgraph
dari derajat minimum sedikitnya c(G)
≤ ½ + m√2 + ¼.
Titik
|
Warna
|
||
Tahap 1
|
Tahap 2
|
Tahap 3
|
|
E
|
1
|
||
F
|
2
|
||
B
|
3
|
||
A
|
2
|
||
C
|
1
|
||
I
|
3
|
||
D
|
3
|
||
G
|
3
|
||
H
|
2
|
||
Contoh
2
Gambar 6.16 (a) merupakan
bagian dari peta Amerika Serikat. Graphnya beserta warna (label) diperlihatkan
pada Gambar 6.16 (b) dengan menggunakan algoritma Welsh dan Powell.
 |
Berikut ini tabel yang
menunjukkan hubungan antara titik, derajat titik dan warna.
Titik
|
AZ
|
UT
|
NV
|
CO
|
NM
|
CA
|
WY
|
TX
|
Derajat titik
|
4
|
4
|
3
|
3
|
3
|
2
|
2
|
1
|
Warna
|
(1)
|
(2)
|
(3)
|
(1)
|
(2)
|
(2)
|
(3)
|
(1)
|
Peta pada Gambar 6.16 (a)
dapat diwarnai dengan 3 warna.
2. Pewarnaan garis
Pewarnaan garis atau rusuk pada suatu graph adalah penentuan
warna rusuk-rusuk suatu graph sehingga setiap rusuk yang berdekatan mendapatkan
warna yang berbeda. Ukuran keberwarnaan suatu graph didefinisikan sama dengan
ukuran keberwarnaan titik, yaitu mengacu kepada banyaknya warna yang
memungkinkan sehingga setiap rusuk yang berdekatan mendapat warna yang berbeda.
Jumlah warna minimal yang dapat digunakan untuk mewarnai
rusuk-rusuk dalam suatu graph G disebut bilangan khromatik G.
Teorema 1
Jika G adalah graph
sederhana yang derajat maksimum titiknya adalah m, maka bilangan khromatiknya c(G) adalah
m < c(G) < m+1
Contoh
1
Derajat maksimum titik dari graph G1, G2, dan G3 adalah 3
Bilangan
khromatiknya adalah 3.
Contoh
2
Untuk graph lengkap Kn mempunyai sifat khusus mengenai bilangan khromatiknya. Perhatikan beberapa contoh graph
lengkap berikut ini.
Hubungan antara banyaknya
titik graph lengkap dan bilangan khromatik untuk graph itu dapat dirumuskan
dalam teorema berikut ini.
Teorema 2
c(Kn) = n, jika n ganjil dan n > 1
c(Kn) = n-1, jika n genap
Contoh
3
c(K5) = 5; c(K6) = 5 ; c(K7); c(K8) = 7.
Teorema 3
Jika G adalah graph
sederhana bipartit yang derajat maksimum titiknya adalah m, maka c(G) = m.
Contoh
4
Berdasarkan teorema 3,
dapat disimpulkan bahwa c(Kp,t) = max (p,t). Kp,t adalah lambang untuk graph
bipartit lengkap yang himpunan titiknya terpisah menjadi himpunan pertama
terdiri atas p titik dan himpunan kedua terdiri atas t titik.
Tanda
max (p,t) menyatakan yang terbesar di antara p dan t.
Contoh
5
Silakan Anda istirahat
sejenak!
Setelah Anda cukup
istirahat, ingat-ingat kembali dan pahami benar uraian di atas. Kemudian
kerjakanlah soal-soal berikut ini sebagai latihan.
|
1) Susunlah model graph untuk mewarnai 15 bola sodok sehingga
bola-bola itu disusun seperti berikut.
2) Sekolah “Harapan Bangsa” merencanakan seminar pendidikan
matematika bagi anak-anak. Ada enam pembicara tampil dalam kesempatan yang
berbeda, kegiatan tersebut akan memakan waktu terlalu lama. Akan tetapi juga
tidak diharapkan pembicara-pembicara 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
|
B
|
C
|
D
|
E
|
F
|
A
B
C
D
E
|
*
|
*
*
|
*
*
|
*
*
*
|
3) Berilah warna pada garis (rusuk) graph berikut, kemudian tentukan
bilangan khromatiknya.
4)
Tentukan
bilangan khromatik dari graf berikut.
 |
|||
 |
|||
Periksa
dan teliti kembali jawaban Anda, sekarang cocokkan jawabannya dengan kunci
jawaban berikut ini.
Kunci Jawaban Latihan
1) Model graph dari soal tersebut adalah sebagai berikut.
Hubungan antara titik, derajat titik, dan warna ditunjukkan
pada tabel berikut ini.
Titik
Derajat
Warna
|
G
6
(1)
|
H
6
(2)
|
K
6
(3)
|
B
4
(2)
|
C
4
(3)
|
D
4
(1)
|
F
4
(3)
|
I
4
(3)
|
J
4
(2)
|
L
4
(1)
|
M
4
(1)
|
N
4
(2)
|
A
2
(1)
|
E
2
(2)
|
O
2
(3)
|
minimum banyaknya warna yang harus disediakan untuk mewarnai
15 bola sodok sehingga bola-bola yang saling bersentuhan berbeda warnanya
adalah 3 warna.
2) Masalah ini dapat dimodelkan dengan graph. Setiap pembicara
diwakili oleh sebuah titik. Setiap sisi mencerminkan dua pembicara tidak
diharapkan tampil pada saat yang bersamaan. Jadi rumusan persoalan graphnya
ialah memperlihatkan bahwa bilangan khromatik graphnya tidak lebih dari 4.
Berikut ini tabel yang menunjukkan hubungan antara titik,
derajat titik, dan warna.
Titik
Derajat
titik
Warna
|
B
4
(1)
|
C
4
(2)
|
E
3
(3)
|
F
3
(4)
|
A
2
(3)
|
D
0
(1)
|
Graphnya adalah sebagai berikut.
Angka mewakili warna yang dapat diberikan kepada titik graph.
Warna-warna ini mewakili babak pembicara tampil di forum. Dari gambar itu dapat
diamati bahwa titik-titik graphnya dapat diwarnai dengan sekurang-kurangnya 4
macam warna. Jadi dapat disimpulkan bahwa kegiatan tersebut dapat diselesaikan
dalam empat babak.
3)
Berikut ini
graph yang dilengkapi dengan warna pada setiap garisnya (rusuknya).
Garis
DE, AF, dan BC diberi warna 1
Garis CD dan BF
diberi warna 2
Garis
AE dan CF diberi warna 3
Garis
AB dan EF diberi warna 4
Jadi bilangan
khromatik graph tersebut adalah 4.
4) Bilangan khromatik graph H yaitu c(H) = 5.
Pewarnaan peta sama dengan
pewarnaan titik-titik pada graph hasil pemodelan dari gambar peta tersebut
sedemikian hingga tidak ada dua titik berdekatan yang mendapat warna sama.
Langkah-langkah yang
dilakukan dalam pemodelan dengan graph ialah menentukan:
1. Objek apa yang akan dikonversikan sebagai titik graph?
2. Hubungan apa yang dicerminkan oleh sisi-sisi graph? Pasangan
titik apa saja yang harus dihubungkan oleh sisi?
3. Merumuskan masalah nyata dalam bahasa teori graph.
 |
1) Graph bipartit lengkap K7,4 sisinya
(rusuknya) dapat diwarnai minimal
....
A. 3 warna
B. 4 warna
C. 7 warna
D. 11 warna
2) Graph lengkap K10 rusuknya
dapat diwarnai minimal dengan ....
A. 10 warna
B. 9 warna
C. 8 warna
D. 7 warna
3)
Peta berikut
ini dapat diwarnai minimal dengan ....
A. 6 warna
B. 5 warna
C. 4 warna
D. 3 warna
4) Peta di samping dapat diwarnai minimal dengan ....
A. 3 warna
B. 4 warna
C. 5 warna
D. 6 warna
5) Perhatikan gambar peta berikut!
Peta tersebut dapat diwarnai minimal dengan ....
A. 6 warna
B. 4 warna
C. 3 warna
D. 2 warna
6) Peta berikut dapat diwarnai minimal dengan ....
A. 2 warna
B. 3 warna
C. 4 warna
D. 5 warna
7) Graph lengkap K15 rusuknya
dapat diwarnai minimal dengan ....
A. 12 warna
B. 13 warna
C. 14 warna
D. 15 warna
8) Perhatikan graph berikut ini
Sisi (rusuk) graph tersebut dapat diwarnai minimal dengan
....
A. 2 warna
B. 3 warna
C. 4 warna
D. 6 warna
9) Peta berikut ini dapat diwarnai minimal dengan ....
A. 7 warna
B. 5 warna
C. 3 warna
D. 2 warna
10) Sisi (rusuk) dari graph berikut
dapat diwarnai minimal dengan ....
A. 6 warna
B. 5 warna
C. 4 warna
D. 3 warna
Cocokkanlah
jawaban Anda dengan Kunci Jawaban Tes Formatif 2 yang terdapat di bagian akhir
modul ini. Hitunglah jawaban yang benar. Kemudian, gunakan rumus berikut untuk
mengetahui tingkat penguasaan Anda terhadap materi Kegiatan Belajar 2.
Rumus:
|
Arti tingkat penguasaan yang
Anda capai:
90 - 100% = baik sekali
80
- 89%
= baik
70 -
79% = cukup
< 70% = kurang
Apabila
Anda mencapai tingkat penguasaan 80% atau lebih, Anda dapat mengikuti Ujian
Akhir Semester (UAS). Bagus! Jika
masih di bawah 80%, Anda harus mengulangi materi Kegiatan Belajar 2, terutama
bagian yang belum dikuasai.
Kunci Jawaban Tes Formatif
Tes
Formatif 1
 |
1) C
Titik V2 V1 V3 V4 V5
Derajat titik 4
3 3 3 3
Warna (1) (2) (3) (2) (3)
2) B Graph lengkap G dengan 5 titik mempunyai
bilangan khromatik 5.
3) A Titik-titik B, D, E, G, J, dan L diwarnai
dengan warna pertama, sedangkan titik-titik A, C, F, H, I, dan K diwarnai
dengan warna kedua.
4) D A salah, tidak hanya satu titik tetapi bisa lebih dari satu
titik
B
salah, karena mempunyai bilangan khromatik 2
C
salah, karena graph yang hanya mempunyai sisi, minimal mempunyai dua titik,
sehingga bilangan khromatiknya minimal 2
D
benar, karena graph yang hanya mempunyai titik (tidak mempunyai sisi) memiliki
bilangan khromatik 1.
5) B Dengan menggunakan algoritma Welsh dan
Powell diperoleh 3 warna.
6) A Graph bipartit lengkap mempunyai bilangan
khromatik 2.
7) C Dengan menggunakan algoritma Welsh dan
Powell diperoleh 3 warna.
8) A Suatu sikel yang memiliki titik yang
banyaknya genap, dapat diwarnai dengan dua warna.
9) D Bilangan khromatik dari graph lengkap K7 adalah 7, karena setiap titik dari graph
lengkap saling berdekatan.
10) B Suatu sikel yang memiliki titik yang
banyaknya ganjil, dapat diwarnai dengan 3 warna.
Tes
Formatif 2
1) C Bilangan khromatik sisi (rusuk) K7,4 = max (7,4) = 7.
2) B Bilangan khromatik rusuk K10 = 10 - 1 = 9.
3) C Pemodelan graphnya adalah sebagai berikut.
Titik
|
D
|
B
|
C
|
E
|
F
|
A
|
Derajat
titik
|
4
|
3
|
3
|
3
|
3
|
2
|
Warna
|
(1)
|
(2)
|
(2)
|
(3)
|
(4)
|
(1)
|
4) A Pemodelan graphnya adalah sebagai berikut
 |
5) D Pemodelan graphnya adalah sebagai berikut.
6) A Pemodelan graphnya adalah sebagai berikut.
7) D Bilangan khromatik rusuk K15 = 15.
8) B
9) C Pemodelan graphnya
adalah sebagai berikut.
 |
Titik E D B C A G F
Derajat
titik 5 4 4 3 2 2 2
Warna
(1) (2) (3) (2) (1) (3) (3)
10) B
Daftar Pustaka
Budayasa, I. K (1997). Matematika
Diskrit I. Surabaya: University Press IKIP Surabaya.
Deo, N. (1994). Graph
Theory with Application to Engineering and a Computer Science. New Delhi:
Prentice-Hall International, Inc.
Harary, F. (1969). Graph
Theory. California: Addison Wesley Publishing Company.
Mayeda, W. (1992). Graph
Theory. New York: John Wiley and Sons, Inc.
Suryadi, D. (1995/1996). Materi
Pokok Matematika Diskrit. (Modul 5 dan Modul 6). Jakarta:
Universitas Terbuka.
Suryanto. (1986). Materi
Pokok Pengantar Teori Graph. Jakarta: Universitas Terbuka.
Sutarno, H., Priatna, N., dan
Nurjanah (2005). Matematika Diskrit.
Malang: IKIP Malang Press.
Tirta-Seputro, T. M. H.
(1992). Matematika Diskrit. (terjemahan). Surabaya: University Press
IKIP Surabaya.
Wilson, R. J. (1985). Introduction to Graph Theory. New York:
John Wiley and Sons, Inc.
Glosarium
Ajasen
Dua buah titik disebut ajasen,
jika kedua titik tersebut merupakan titik-titik ujung dari sisi yang sama.
Algoritma
Algoritma merupakan prosedur atau aturan. Contoh: algoritma
Welsh dan Powell.
Bilangan Khromatik
Bila suatu graph G dapat diwarnai minimal dengan n warna,
maka G dikatakan memiliki bilangan khromatik n.
Derajat titik
Derajat titik V
yaitu jumlah atau banyaknya sisi yang insiden dengan titik V.
Insiden
Jika sebuah titik V
merupakan titik ujung dari sisi E
maka V dan E saling berinsidensi atau titik V insiden dengan sisi E.
Komputer super
Komputer super merupakan komputer yang mempunyai kapasitas
dan kemampuan yang sangat tinggi.
Konjektur
Konjektur merupakan dugaan sementara atau jawaban sementara
yang harus ditunjukkan kebenarannya.
Lintasan (path)
Suatu lintasan u-v (u-v path) dalam graph G adalah lintasan
yang tidak mengulangi sebarang sisi
(rusuk) dan tidak mengulangi sebarang titik
(simpul).
Pewarnaan titik
Mewarnai titik dilakukan dengan cara memberi label pada
titik-titik graph sehingga titik yang berdekatan mendapatkan label yang berbeda.
Pewarnaan sisi (pewarnaan peta)
Pewarnaan sisi (pewarnaan peta)
sama dengan pewarnaan titik-titik pada graph hasil pemodelan dari gambar peta
tersebut sedemikian hingga tidak ada dua titik berdekatan yang mendapat warna
sama.
Pewarnaan garis
Pewarnaan garis atau rusuk pada suatu graph adalah
penentuan warna rusuk-rusuk suatu graph sehingga setiap rusuk yang berdekatan
mendapatkan warna yang berbeda.
Sikel
Sikel adalah suatu sirkuit yang tidak mengulang sebarang
titik internalnya (titik dalamnya).
Sirkuit
Lintasan u-v, dengan u = v (titik awal sama dengan titik akhir) disebut sirkuit.
.jpg)
0 komentar:
Posting Komentar