Cara Mencari Pewarnaan ( coloring ) Graph

Contoh Soal dan Pembahasan Pewarnaan Graph - yee akhirnya UAS telah tiba gan... saatnya belajar dulu nih. kali ini kita akan membahas bagaimana sih cara mencari pewarnaan Graph. oke langsung saja, cekidot.

Sebelumnya, apa itu sih pewarnaan Graph, oke pewarnaan graph adalah subuah pemetaan warna-warna ke simpul-simpul sehingga simpul relasinya mempunyai warna-warna yang berbeda.

Kali ini kita akan membahas pewarnaan titik ( welch powel ). langsung aja ke contoh soal ya gan.

Contoh 1

Tentukan warna dan jumlah warnanya, hayooo berapa ya gan ?

jawab :
pertama-tama agan tentukan dahulu titik yang bertetangga (derajat). jika sudah, urutkan dari yang terbesar ke yang terkecil. maka hasilnya seperti dibawah ini :

Nah jika sudah, tentukan tipe warnanya. carany warna harus berbeda pada setiap titik yang bertetangga. misalnya titik A warnanya p, nah titik A kan bertetangga tuh sama titik B,C dan D, berarti warna di titik B,C, dan D harus berbeda warnanya dengan titik A. 

jika pada setiap titik tidak bertetangga, maka warnanya boleh sama gan. Maka dapat dihasilkan warna sebagai berikut :

jadi ,
jenis warnanya adalah p,q dan r
dan jumlah warnanya ada 3 gan. X(G) = 3

Contoh 2

Misalnya :
A ( futsal ) : Ndoro, Yusuf, Fikri, Diki, Haga
B ( Badminton ) : Ria, Euis, Ilham, Faiz, Bonar
C ( Basket ) : Arnold, Izal, Yusuf, Ilham
D ( Catur ) : Dibu, Suta, Ria, Haga
E ( Renang ) : Bonar, Andi, Izal, Lani

Mereka akan melakukan rapat dan menyewa ruangan dengan syarat setiap kelompok anggotanya harus lengkap, berapa jumlah slot waktu rapat agar syarat terpenuhi ?

Jawab :
Pertama-tama agan buat dahulu nama dan permainannya yang bertetangga. seperti dibawah ini :

Sama seperti contoh 1, tentukan jumlah yang bertetangga ( Derajat ) terhadap titik dan urutkan dari tertinggi ke terendah seperti dibawah ini gan :

Sama seperti contoh 1, tapi disini kata2nya diganti menyari slot. maka hasilnya seperti dibawah ini gan :

Jadi,

Jumlah slot yang dibutuhkan ada 3, X(G)=3

Sekian dulu dari ane gan. jika terdapat kesalahan atau kekurangan gitu mohon diberitahukan, kita sama-sama belajar gan hehehe. jangan lupa follow dan baca artikelnya yang lain ya gan.. byee. Asalamualaikum...