Graf

(Part 3)

1
 Pewarnaan Graf
• Pewarnaan graf ada dua macam, yaitu pewarnaan
simpul dan pewarnaan sisi
• Pewarnaan simpul: memberi warna pada simpul-simpul
graf sedemikian sehingga dua simpul bertetangga
mempunyai warna berbeda.
• Aplikasi pewarnaan graf: mewarnai peta.
• Peta terdiri atas sejumlah wilayah.
• Wilayah dapat menyatakan kecamatan,
kabupaten, provinsi, atau negara.
• Peta diwarnai sedemikian sehingga dua wilayah
bertetangga mempunyai warna berbeda.
• Nyatakan wilayah sebagai simpul, dan batas
antar dua wilayah bertetangga sebagai sisi.
• Mewarnai wilayah pada peta berarti mewarnai
simpul pada graf yang berkoresponden.
• Setiap wilayah bertetangga harus mempunyai
warna berbeda ➔ warna setiap simpul harus
berbeda.
 1 1 1
2 2 2

3 3 3
4 4
4
8 5 8 5 8 5

7 6 7 6 7 6

(a) (b) (c)

1 merah 2 kuning 1 merah 2 kuning

biru 3 jingga biru 3 merah

ungu ungu
4 4
hijau
8 5 kuning
8 5

putih kuning
7 6 7 6
hitam merah

(d) (e)

Gambar 8.72 (a) Peta

(b) Peta dan graf yang merepresentasikannya,
(c) Graf yang merepresentasikan peta,
(d) Pewarnaan simpul, setiap simpul mempunai warna berbeda,
(e) Empat warna sudah cukup untuk mewarnai 8 simpul
• Bilangan kromatik: jumlah minimum warna yang
dibutuhkan untuk mewarnai peta.
• Simbol: (G).
• Suatu graf G yang mempunyai bilangan kromatis k
dilambangkan dengan (G) = k.

Graf di bawah ini memiliki (G) = 3

Graf kosong Nn memiliki (G) = 1, karena semua simpul
tidak terhubung, jadi untuk mewarnai semua simpul cukup
dibutuhkan satu warna saja.
Graf lengkap Kn memiliki (G) = n sebab semua simpul
saling terhubung sehingga diperlukan n buah warna.
• Graf bipartit Km,n mempunyai (G) = 2, satu untuk
simpul-simpul di himpunan V1 dan satu lagi untuk
simpul-simpul di V2.

• Graf lingkaran dengan n ganjil memiliki (G) = 3,

sedangkan jika n genap maka (G) = 2.
• Sembarang pohon T memiliki (T) = 2.
• Untuk graf-graf yang lain tidak dapat dinyatakan
secara umum bilangan kromatiknya.
Perkembangan teorema pewarnaan graf:
• TEOREMA 1. Bilangan kromatik graf planar  6.
• TEOREMA 2. Bilangan kromatik graf planar  5.
• TEOREMA 3. Bilangan kromatik graf planar  4.

Teorema 4 berhasil menjawab persoalan 4-warna (yang

diajuka pada abad 19): dapatkah sembarang graf planar
diwarnai hanya dengan 4 warna saja?
Jawaban dari persoalan ini ditemukan oleh Appel dan Haken
yang menggunakan komputer untuk menganalisis hampir
2000 graf yang melibatkan jutaan kasus
Cukup 4 warna saja untuk mewarnai sembarang peta
Aplikasi lain pewarnaan graf: penjadwalan.
Misalkan terdapat delapan orang mahasiswa (1, 2, …, 8) dan lima buah mata kuliah yang dapat dipilihnya
(A, B, C, D, E). Tabel berikut memperlihatkan matriks lima mata kuliah dan delapan orang mahasiswa.
Angka 1 pada elemen (i, j) berarti mahasiswa i memilih mata kuliah j, sedangkan angka 0 menyatakan
mahasiswa i tidak memilih mata kuliah j.

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 0 1 1 0
7 1 0 1 0 0
8 0 0 1 1 0

Berapa paling sedikit jumlah hari yang dibutuhkan untuk jadwal ujian tersebut sedemikian sehingga semua
mahasiswa dapat mengikuti ujian mata kuliah yang diambilnya tanpa bertabrakan waktunya dengan jadwal
ujian kuliah lain yang juga diambilnya?
Penyelesaian:
• simpul → mata kuliah
• sisi → ada mahasiswa yang mengambil kedua mata kuliah (2 simpul)

A merah A

biru E
E
B B merah

merah
biru
D
D C

(a) (b)

Gambar 8.74. (a) Graf persoalan penjadwalan ujian 5 mata kuliah

untuk 8 orang mahasiswa
(b) Hasil pewaranan pada simpul-simpul graf

•Bilangan kromatik graf pada Gambar 8.74 adalah 2.

• Jadi, ujian mata kuliah A, E, dan D dapat dilaksanakan bersamaan,
sedangkan ujian mata kuliah B dan C dilakukan bersamaan
tetapi pada waktu yang berbeda dengan mata kuliah A, E, dan D.
 Latihan soal
1. Dapatkah kita menggambar graf teratur
berderajat 3 dengan 7 buah simpul? Mengapa?
2. Tentukan jumlah simpul pada graf sederhana
bila mempunyai 20 buah sisi dan tiap simpul
berderajat sama.
3. Berapa jumlah minimum simpul yang
diperlukan agar sebuah graf dengan 6 buah sisi
menjadi planar? Ulangi soal yang sama untuk
11 buah sisi.
4. Diberikan gambar sebuah graf G seperti di bawah ini.

B (a) Tunjukkan dengan ketidaksamaan Euler bahwa graf

G tidak planar.
A C

(b) Tunjukkan dengan Teorema Kuratowski bahwa graf

D E G tidak planar.
F G

H
5. Gambarkan 2 buah graf yang isomorfik dengan graf
teratur berderajat 3 yang mempunyai 8 buah simpul.

6. Sebuah departemen mempunyai 6 kelompok kerja yang

setiap bulannya masing-masing selalu mengadakan
rapat satu kali. Keenam kelompok kerja dengan masing-
masing anggotanya adalah: K1 = {Amir, Budi, Yanti}, K2
= {Budi, Hasan, Tommy}, K3 = {Amir, Tommy, Yanti},
K4 = {Hasan, Tommy, Yanti}, K5 = {Amir, Budi}, K6 =
{Budi, Tommy, Yanti}. Berapa banyak waktu rapat
berbeda yang harus direncanakan sehingga tidak ada
anggota kelompok kerja yang dijadwalkan rapat pada
waktu yang sama. Gambarkan graf yang
merepresentasikan persoalan ini lalu (jelaskan sisi
menyatakan apa, simpul menyatakan apa) tentukan
jumlah waktu rapat ini.
7. Apakah K13 memiliki sirkuit Euler? Sirkuit Hamilton?
Ulangi pertanyaan yang sama untuk K14
8. Sebuah graf akan dibentuk dari 25 buah sisi. Berapa
jumlah maksimum simpul di dalam graf sederhana yang
dapat dibuat dari 25 buah sisi tersebut?
 Referensi
Munir, Rinaldi. Graf (Bagian 1). Struktur
Diskrit. STEI ITB.