PERTEMUAN_12_Pewarnaan_Graf math disk.pdf

math disk pewarnaan grafis

1. MATEMATIKA DISKRIT
PERTEMUAN 12
PEWARNAAN GRAF

2. PENDAHULUAN
•Ada dua macam: pewarnaansimpul, dan pewarnaansisi
•Hanya dibahasperwarnaansimpul
•Pewarnaan simpul: memberiwarnapada simpul-simpulgraf
sedemikiansehinggadua simpulbertetanggamempunyaiwarna
berbeda.
•Aplikasipewarnaangraf: mewarnaipeta.
•Peta terdiriatassejumlahwilayah.
•Wilayah dapatmenyatakankecamatan, kabupaten, provinsi,
ataunegara.
•Peta diwarnaisedemikiansehinggadua wilayah bertetangga
mempunyaiwarnaberbeda.

3. PEWARNAAN GRAF

4. PEWARNAAN GRAF
•Nyatakanwilayah sebagaisimpul, dan batas antardua
wilayah bertetanggasebagaisisi.
•Mewarnaiwilayah pada petaberartimewarnaisimpulpada
grafyang berkoresponden.
•Setiapwilayah bertetanggaharusmempunyaiwarna
berbeda➔warnasetiapsimpulharusberbeda.

5. •(a) Peta
•(b) Peta dan graf yang merepresentasikannya
(c) Graf yang merepresentasikanpeta
(d) Pewarnaan simpul, setiapsimpulmempunaiwarnaberbeda
(e) Empatwarnasudahcukupuntukmewarnai8 simpul

6. BILANGAN KROMATIK
•Bilangankromatik: jumlahminimum warnayang dibutuhkanuntukmewarnaipeta.
Simbol: (G).
•SuatugrafG yang mempunyaibilangankromatisk dilambangkandengan(G) = k.
Graf di bawahinimemiliki(G) = 3

7. BILANGAN KROMATIK
•Graf kosongNnmemiliki(G) = 1, karenasemuasimpultidakterhubung, jadiuntuk
mewarnaisemuasimpulcukupdibutuhkansatuwarnasaja.

8. BILANGAN KROMATIK
•Graf lengkapKnmemiliki(G) = n sebabsemuasimpulsalingterhubungsehingga
diperlukann buahwarna.

9. ALGORITMA WELCH POWELL
•Menentukanwarnasebenarnyasangat sulitkecualidalam
kasus-kasussederhanasepertipada contoh-contohyang akan
kitabahasdalambabini
•AlgoritmaWelch-Powell adalahsuatucarayang efisienuntuk
mewarnaisebuahgrafG.

10. ALGORITMA WELCH POWELL
1.Urutkansimpul-simpuldariG dalamurutanderajatyang menurun.
Urutaninimungkintidakunikkarenabeberapasimpulmungkin
mempunyaiderajatyang sama.
2.Gunakansatuwarnatertentuuntukmewarnaisimpulpertama. Secara
berurut, setiapsimpuldalamdaftar yang tidakberelasidengansimpul
sebelumnyadiwarnaidenganwarnaini.
3.Ulangilangkah2 di atasuntuksimpuldenganurutantertinggiyang
belumdiwarnai.
4.Ulangilangkah3 di atassampaisemuasimpuldalamdaftar terwarnai.

11. ALGORITMA WELCH POWELL
•Contoh:
GunakanalgoritmaWelch-Powell untukmewarnaigrafdi bawahinidan
tentukanbilangankromatiknya!
•Jadi, , (G) = 3
Simpul 1 36425
Derajat 4 43322
Warna a bbcca
1
6 2
5 3
4

12. ALGORITMA WELCH POWELL
•Misalkanterdapatdelapanorang mahasiswa(1, 2, …, 8) dan lima buahmatakuliahyang dapat
dipilihnya(A, B, C, D, E). Tabel berikutmemperlihatkanmatrikslima matakuliahdan delapanorang
mahasiswa. Angka 1 pada elemen(i, j) berartimahasiswaimemilihmatakuliahj, sedangkanangka0
menyatakanmahasiswaitidakmemilihmatakuliahj.

13. ALGORITMA WELCH POWELL
•Berapapaling sedikitjumlahhariyang dibutuhkanuntuk
jadwalujiantersebutsedemikiansehinggasemua
mahasiswadapatmengikutiujianmatakuliahyang
diambilnyatanpabertabrakanwaktunyadenganjadwal
ujiankuliahlain yang juga diambilnya?
•Penyelesaian:
simpul→matakuliah
sisi→adamahasiswayang mengambilkeduamata
kuliah(2 simpul)

14. ALGORITMA WELCH POWELL
•(a) Graf persoalanpenjadwalanujian5 matakuliahuntuk8 orang mahasiswa
(b) Hasil pewarananpada simpul-simpulgraf
•Bilangankromatikgrafpada Gambar di atasadalah2.
• Jadi, ujianmatakuliahA, E, dan D dapatdilaksanakanbersamaan, sedangkanujianmatakuliahB
dan C dilakukanbersamaantetapipada waktuyang berbedadenganmatakuliahA, E, dan D.

15. LATIHAN SOAL
1. Sebuahdepartemenmempunyai6 kelompokkerjayang setiap
bulannyamasing-masing selalumengadakanrapatsatukali. Keenam
kelompokkerjadenganmasingmasinganggotanyaadalah: K1 =
{Amir, Budi, Yanti}, K2 = {Budi, Hasan, Tommy}, K3 = {Amir, Tommy,
Yanti}, K4 = {Hasan, Tommy, Yanti}, K5 = {Amir, Budi}, K6 ={Budi,
Tommy, Yanti}. Berapabanyakwakturapatberbedayang harus
direncanakansehinggatidakadaanggotakelompokkerjayang
dijadwalkanrapatpada waktuyang sama. Gambarkangrafyang
merepresentasikanpersoalaninilalu(jelaskansisimenyatakanapa,
simpulmenyatakanapa) tentukanjumlahwakturapatini.

16. LATIHAN SOAL
2. Terdapat8 macamzatkimiaA, B, C, D, E, F, G, H yang akandisimpandalambeberaparuangan.
Untukmenghematbiayamakadiperlukanruanganseminimalmungkin. Untukitudikelompokkan
daftar zat–zatyang akanmeledakjikadiletakkandalamsaturuangan. Gambarkangrafyang
menyatakanpersoalandi atas, lalutentukanadaberaparuanganyang dibutuhkanagar amandalam
penyimpanan. Berikutzat–zatyang tidakbisadisimpandalamsaturuangan:

17. LATIHAN SOAL
•Pak Ahmad mempunyai8 ekorayamjantanyang sukabertarungjikabertemudenganayamjantan
yang lain. Berapabanyakkandangminimal yang harusdisiapkanPak Ahmad agar ayam–ayamnya
tidakbertarung. Ayam yang mana sajakahyang bisadigabungdalamkandangyang sama, jikadata
ayamtersebutsepertidi bawaah:

18. LATIHAN SOAL
3. Terdapat 7 matakuliah (A s/d G) yang pada semester ini di ambil oleh 14 mahasiswa. Berikut ini adalah tabel
pengambilan matakuliah oleh mahasiswa. Gunakan algoritma pewarnaan Welsh-Powell untuk penjadwalan kuliah
yangefisien.
a. Tentukan slot waktu minimal yang harus disiapkan agar para mahasiswa diatas dapat mengikuti
perkuliahan.
b. Matakuliah mana sajakah yang bisa dijadwalkan dalam slot waktu yangsama.
NIM A B C D E F G
001 1 - - - - - 1
002 1 1 - - - - -
003 1 - - - - 1 -
004 - 1 - - - 1 -
005 - 1 1 - - - -
006 - 1 - 1 - - -
007 - - 1 1 - - -
008 - - 1 - - - 1
009 - - - 1 1 - -
010 - - - 1 - - 1
011 - - - - 1 1 -
012 - - - - 1 - 1
013 - - - - - 1 1
014 - 1 - - - 1 -

19. TERIMAKASIH