modul 6. pewarnaan graf (2x pert)

8/17/2019 Modul 6. Pewarnaan Graf (2x Pert)

1/43

Modul 6

Pewarnaan Graf

Prof. Dr. H. Nanang Priatna, M.Pd.

odul 6 ini merupakan modul terakhir dari modul mata kuliah Teori

Graf. Modul-modul sebelumnya membahas tentang PengetahuanDasar Teori Graf, Representasi Graf dan Beberapa Graf husus, !intasan daneterhubungan, Pohon, dan Planaritas.M

Pada akhir abad kesembilan belas, seorang kepala sekolah memberikansoal yang sangat menantang kepada murid-muridnya. "oal itu sebagai

berikut# $Tun%ukkan bah&a semua peta hanya memerlukan empat &arna,sehingga negara-negara atau pro'insi-pro'insi yang bertetangga mendapat&arna yang berbeda(.

Dia mengatakan hanya mau menerima pembuktian tidak lebih dari )* baris tulisan dan satu halaman diagram. Tampaknya soal ini sederhana sekali,tetapi sebenarnya tidak demikian. "oal ini men%adi masalah besar di duniamatematika, yang kemudian terkenal dengan nama Konjektur Empat Warna.Baru pada Tahun +6 ditemukan penyelesaian masalah ini. Pada tahuntersebut enneth ppel dan /olfgang 0aken, dua matematika&an dari1ni'ersitas 2llionis di merika "erikat, dapat membuktikan 3dengan bantuankomputer4 dugaan empat &arna dengan menyita &aktu sekitar +.5** %am

komputer untuk menghasilkan beratus-ratus halaman kertas hasil analisismenyeluruh terhadap sekitar 5.*** graf dengan %utaan kemungkinan

bentuknya."alah satu ara yang digunakan adalah menggunakan graf yang titiknya

menun%ukkan pro'insi dan garis menun%ukkan hubungan dua pro'insi itusebagai tetangga.

onsep-konsep yang dika%i dan diuraikan di dalam pembahasan modulini terdiri atas topik-topik yang menyangkut pe&arnaan titik, pe&arnaan sisi

3pe&arnaan peta4, dan pe&arnaan garis.Melalui uraian dan pembahasan dalam modul ini, diharapkan dapat

menun%ang &a&asan dan pengetahuan nda dalam melaksanakan tugas.

PENDAHULUAN


2/43

PAMA4208/MODUL 6 6.2

Disamping itu nda diharapkan dapat menggunakannya dalam kehidupansehari-hari serta dapat menga%arkannya dengan pendekatan tertentu yang

sesuai. "eara khusus tu%uan dari penya%ian modul ini adalah agar ndadapat#a. men%elaskan pe&arnaan titik suatu graf,

b. men%elaskan pe&arnaan sisi 3pe&arnaan peta4,. men%elaskan pe&arnaan garis suatu graf,d. menentukan bilangan khromatik suatu graf,e. men%elaskan algoritma /elsh dan Po&ell dalam pe&arnaan graf,f. men%elaskan teori-teori pe&arnaan graf,

g. menerapkan analisis pe&arnaan graf dalam kehidupan sehari-hari.


3/43

Kegiatan Belajar

Pewarnaan Titik Suatu Graf (1 soal aplikasi

gar nda lebih memahami pengertian tentang pe&arnaan titik suatugraf, perhatikan ontoh-ontoh serta pen%elasan berikut ini.A

Contoh 1

ndaikan sebuah pabrik kimia ingin mengirimkan hasil produksinya

dengan menggunakan kereta api. "esuai dengan ketentuan yang ada, tidak semua 7at kimia ini dapat dimuat dalam satu kereta, karena kemungkinan

berampurnya 7at itu yang dapat menyebabkan ter%adinya reaksi berupaledakan yang membahayakan. Bagaimana 7at-7at kimia ini dapat dikirim8Dengan maksud meminimumkan biaya, pabrik itu ingin menggunakangerbong kereta api sesedikit mungkin. Berapa banyaknya gerbong kereta apiitu8

Pada 9ontoh di atas ada ob%ek 3hasil 7at kimia4 dan ada keterhubungan

3tidak dapat dimuat dalam satu gerbong kereta4 di antara ob%ek itu. arenahal ini merupakan ide dasar suatu graf, maka dapat disa%ikan dalam bentuk graf. Pada ontoh di atas, titik-titiknya adalah 7at kimia dan sisinyamenghubungkan 7at-7at kimia yang tidak dapat diangkut dalam gerbongkereta yang sama.

"ebagai ilustrasi, diasumsikan bah&a pada ontoh + ada enam 7at kimiaP

+, P

5, P

), P

:, P

;, dan P

6. "erta P

+ dengan P

5, P

), atau P

: tidak dapat diangkut

dalam kereta yang sama, %uga P5 dengan P

) atau P

;, P

) dengan P

:, dan P

;

dengan P6. Graf yang menya%ikan hal ini dapat dilihat pada Gambar 6.+, yangtitik-titiknya menun%ukkan enam 7at kimia dan sisinya menghubungkan

pasangan 7at kimia yang tidak dapat dimuat dalam gerbong kereta yangsama.


4/43

Ga!"ar 6.1

Berapa banyak minimum gerbong kereta yang diperlukan8 Dalam graf

pada Gambar 6.+, 7at kimia yang disa%ikan dengan titik berdekatan harusdimuat dalam gerbong kereta yang tidak sama. Misal# 7at P+ dan P

5

berdekatan, misalkan 7at P+

diletakkan pada gerbong kereta +, kereta lain

diperlukan untuk memuat P5, katakan gerbong kereta 5. arena P

) berdekatan

P+ dan P

5, maka diperlukan gerbong kereta lain lagi untuk P

), katakan

gerbong kereta ). Tetapi tidak diperlukan gerbong kereta lain lagi untuk P:,

gerbong kereta 5 dapat digunakan lagi. Demikian pula halnya, tidak diperlukan gerbong kereta lain lagi untuk P

;, karena gerbong kereta + atau )

dapat digunakan lagi. Misalnya dipilih gerbong kereta +, maka untuk P6

dipilih gerbong kereta 5 atau ), katakan gerbong kereta 5. Graf pada Gambar 6.5 menun%ukkan bagaimana titik-titik itu diberi nama 3label4 sehingga 7atkimia yang tidak dapat berada bersama, dimuat dalam gerbong kereta

berbeda.


5/43

Bila suatu graf G dapat di&arnai minimal dengan n &arna, maka Gdikatakan memiliki bilangan khromatik n.


6/43

Ga!"ar 6.$

Dalam graf lengkap n, setiap titik saling berdekatan dengan titik

lainnya. lehkarena itu, graf lengkap

n memiliki bilangan khromatik n.

Contoh 4

Graf pada Gambar 6.; 3a4 dapat di&arnai dengan menggunakan dua&arna, seperti terlihat pada Gambar 6.; 3b4.

Ga!"ar 6.%

Contoh 5

Graf pada Gambar 6.6 memiliki bilangan khromatik 5 karena titik disebelah kiri dapat di&arnai dengan menggunakan &arna pertama dan titik di

sebelah kanan dapat di&arnai dengan menggunakan &arna kedua.

•

• •

• •

•

• •

• •


7/43

Ga!"ar 6.6

"eara umum, sangat sulit untuk menentukan banyak minimum &arna

yang diperlukan untuk me&arna graf. "alah satunya dengan mendaftar semuaara me&arna 3yang berbeda4 titik-titik graf, kemudian memeriksa setiap araitu untuk menentukan mana yang menggunakan banyak &arna minimum."ayangnya, &alaupun titik graf tidak seberapa banyak, dan kitamenggunakan komputer super, proses ini sangat memakan &aktu, bahkansampai berabad-abad.

Tetapi, ada beberapa ara yang berhasil diperoleh untuk dapatmenun%ukkan bilangan khromatik suatu graf. Misal, seperti yang terlihat

pada 9ontoh ), sikel yang pan%angnya gan%il memiliki bilangan khromatik ).


8/43

Ga!"ar 6.&

Terlihat bah&a %ika = dan / berdekatan, maka akan ada sikel yang pan%angnya ). Dengan demikian, setiap titik lain yang baru sa%a di&arnai&arna merah tidak berdekatan dengan titik yang ber&arna merah, karena %ikatidak demikian berarti ada sikel yang pan%angnya gan%il. Berikutnya, titik yang berdekatan dengan yang baru sa%a di&arnai &arna merah diberi &arna

biru. 0al ini diperlihatkan pada Gambar 6.?.

Ga!"ar 6.'

emudian, %ika dua titik yang di&arnai biru terletak berdekatan, makaada sikel yang pan%angnya gan%il. emudian dilan%utkan dengan me&arnaimerah titik yang berdekatan dengan titik yang baru di&arnai biru. "epertisebelumnya, tidak ada titik yang baru di&arnai merah dapat terletak

berdekatan dengan titik yang telah ber&arna merah. Proses ini diulangisampai tidak ada titik yang belum mendapat &arna terletak berdekatandengan titik yang telah di&arnai.


9/43


10/43

Bukti

Misalkan k adalah dera%at maksimum titik dari G. kan ditun%ukkan

bah&a G dapat di&arnai dengan menggunakan kE+ &arna 9*, ..., 9k . Mula-mula titik = dipilih dan diberi &arna 9

*. emudian, beberapa titik / lain

dipilih. arena paling banyak ada k titik yang berdekatan dengan / dan ada paling sedikit k E + &arna yang tersedia, maka paling sedikit ada satu &arna3dapat lebih banyak4 yang belum digunakan untuk me&arnai titik yang

berdekatan dengan /. Pilih &arna itu. Proses ini dapat dilan%utkan sampaisemua titik dari G mendapat &arna.

Contoh !

Proses yang digambarkan pada teorema 5 dapat menggunakan lebih banyak &arna daripada yang sebenarnya diperlukan. Graf pada Gambar 6.+*memiliki titik berdera%at :, yang merupakan dera%at maksimumnya, sehinggadengan teorema 5 di atas, graf itu dapat di&arnai dengan menggunakan : E +F ; &arna. Tetapi, dengan menggunakan prosedur yang digambarkan padateorema +, graf itu dapat di&arnai dengan menggunakan 5 &arna.

Ga!"ar 6.1)

Berikut ini akan diuraikan algoritma tambahan, yang ditemukan /elshdan Po&ell, untuk pe&arnaan titik-titik dari suatu graf.

Algoritma Welsh dan Powell

lgoritma ini memberikan ara me&arnai sebuah graf dengan memberilabel titik-titiknya sesuai dengan dera%atnya.

"angkah 1 3melabel titik dengan dera%atnya4. !abel titik =+, =

5, ..., =

n

sedemikian hingga dera%at 3=+4 dera%at 3=54 ... dera%at3=

n4.


11/43

"angkah 2 3&arnai titik belum ber&arna pertama dari titik-titik belum ber&arna yang berdekatan dengan titik itu4. Berikan &arna yang

belum digunakan pada titik belum ber&arna yang pertama padadaftar titik itu. !akukan hal itu pada semua titik dalam daftar seara terurut, berikan &arna baru ini pada setiap titik yangtidak berdekatan dengan setiap titik lain yang telah di&arnai ini.

"angkah 3 3grafnya telah di&arnai84.


12/43

=+ # =

5, =

), =

:, =

;, =

=5 # =

+, =

), =

;

=) # =+, =5, =:=

: # =

+, =

), =

6

=; # =

+, =

5, =

6

=6 # =

:, =

;

= # =

+

Pada lgoritma /elsh dan Po&ell ini, titik belum ber&arna pertama

dalam daftar adalah =+ yang diberi &arna merah. emudian diari titik berikut yang tidak berdekatan dengan =+ pada daftar, yaitu titik di ba&ah =

+

yang tidak mengikuti =+. Diperoleh titik =

6, yang diberi &arna merah.

Dilan%utkan dengan melihat bagian bah&a daftar untuk menari titik berikutnya yang tidak berdekatan dengan =

+ maupun =

6. arena titik seperti

itu tidak ada, maka kembali dilihat bagian atas daftar dan ditentukan lagi titik belum ber&arna yang pertama, yaitu =

5, yang diberi &arna biru. emudian,

titik belum ber&arna berikutnya ditentukan yang tidak berdekatan dengan =5.

Diperoleh titik =: dan diberi &arna biru. 9ara ini dilan%utkan lagi, dandiperoleh titik =

yang belum ber&arna dan tidak berdekatan dengan =

5

maupun =:, sehingga =

di&arnai biru, bagian atas daftar dilihat kembali dan

ditentukan titik belum ber&arna berikutnya, yaitu =), yang diberi &arna

hi%au. arena =; belum di&arnai dan tidak berdekatan dengan =

), yang diberi

&arna hi%au. Dengan demikian maka graf pada Gambar ++ 3b4 dapat di&arnaidengan tiga &arna.

Penya%ian daftar berdekatan membuat algoritma /elsh dan Po&ellmudah digunakan, karena titiknya dapat ditandai ketika di&arnai, sehinggatinggal memperhatikan titik belum ber&arna sisanya dalam proses

per&arnaan itu."ilakan nda istirahat se%enakH"etelah nda ukup istirahat, ingat-ingat kembali dan pahami benar

uraian di atas. emudian ker%akanlah soal-soal berikut ini sebagai latihan.


13/43

+4 Perhatikan tabel + matriks sis&a dan bidang studi berikut ini.

Ta"el 6.1Matriks Siswa dan *idang Studi

A B C D E

1 0 1 0 0 12 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.+ menun%ukkan matriks tentang lima bidang studi 3di labeldengan ab%ad4 yang dipilih oleh delapan orang sis&a 3di label denganangka4. ngka + diisikan sebagai elemen 3i,%4 matriks itu, %ika sis&a imemilih bidang studi %. "edangkan angka * diisikan sebagai elemen 3i,%4,

%ika sis&a i tidak memilih bidang studi %.9ontoh# sis&a + memilih bidang studi B dan A karena elemen 3+,B4 dan3+,A4 adalah +.

Berdasarkan Tabel 6.+, tentukan banyak %ad&al u%ian yang dapat dibuatsedemikian rupa sehingga semua sis&a dapat mengikuti u%ian bidangstudi itu tanpa ada kesulitan &aktu 3kesulitan ter%adi %ika ada sis&a yangharus mengikuti u%ian dua bidang studi atau lebih pada &aktu yang

bersamaan4.

LA!"HAN

1ntuk memperdalam pemahaman nda mengenai materi di atas,ker%akanlah latihan berikutH


14/43

54 Berapa bilangan khromatik graf berikut8

)4 Tentukan bilangan khromatik graf berikut.

:4 da 6 %enis 7at kimia yang perlu disimpan di gudang. Beberapa pasangdari 7at itu tidak dapat disimpan di tempat yang sama, karena ampurangasnya bersifat eksplosif. 1ntuk 7at-7at semaam itu perlu dibangunruang-ruang terpisah yang dilengkapi 'entilasi dan penyedot udara keluar yang berlainan.


15/43

Berapa banyak minimum ruangan berbeda untuk menyimpan semua 7atkimia itu seara aman8

Periksa dan teliti kembali %a&aban nda, sekarang ookkan %a&abannyadengan kuni %a&aban berikut ini.

$etunjuk %awaban "atihan

+4 Penyelesaian masalah membuat %ad&al u%ian ini sebenarnya ekui'alendengan masalah menari bilangan khromatik suatu graf. Cang perlu

diingat adalah u%ian dan bidang studi dapat di%ad&alkan pada &aktu yangsama %ika tidak ada sis&a yang sama yang mengikuti u%ian dua bidangstudi itu.Pen%ad&alan u%ian itu dapat digambarkan sebagai sebuah graf, dan setiap

bidang studi ditun%ukkan sebagai titiknya. Dua titik dihubungkandengan sebuah garis %ika ada sis&a yang memiliki kedua bidang studiitu. "ehingga dapat ditafsirkan bah&a %ika dua titik dihubungkan olehgaris maka u%ian dua bidang studi itu tidak dapat dilakukan bersamaan,

karena akan ada sis&a yang mendapat kesulitan. Diberikan &arna yang berbeda untuk titik-titik semaam itu yang menun%ukkan bah&a &aktuu%iannya berbeda.ita gambar masalah graf di atas


16/43

Ternyata bilangan khromatiknya 5. 1%ian bidang studi , A, dan D dapatdilaksanakan bersamaan, sedangkan u%ian bidang studi B dan 9 dapat

dilakukan bersama tetapi pada &aktu yang berbeda dengan u%ian bidangstudi , A, dan D.

54 Titik pada graf tersebut dapat di&arnai sebagai berikut.=

; merah

=) biru

=5 dan =

: kuning

=+ hi%au

=6 putih

arena graf itu dapat di&arnai minimal dengan ; &arna, maka bilangankhromatiknya adalah ;.

)4 Titik-titik 0, B, dan A &arna merah 3+4.Titik-titik 2, @, dan 9 &arna biru 354.Titik-titik D, , dan G &arna kuning 3)4.Bilangan khromatiknya adalah ).

:4 "oal tersebut dapat dibuat grafnya dengan titik menun%ukkan $7at kimia(dan garis menun%ukkan $tidak dapat bersama dengan 7at kimia(.Gambar grafnya adalah sebagai berikut.


17/43

Berikut ini tabel yang menun%ukkan hubungan antara titik, dera%at titik,dan &arna.

Titik B D @ A 9Dera%at titik : ) 5 5 5 +/arna 3+4 354 3)4 3)4 354 3+4

Bilangan khromatiknya )


18/43

+4 Bilangan khromatik gambar graf di ba&ah ini adalah ....

. ;B. :9. )

D. 5

54


19/43

. 5B. )

9. :D. +5

:4


20/43

. 6B. ;

9. )D. 5

?4 Bilangan khromatik dari graf sikel 9? adalah ....

. 5B. :9. 6D. ?

4 Bilangan khromatik dari graf lengkap adalah ..... +B. )9. ;D.

+*4 Bilangan khromatik dari graf sikel 9+;

adalah ....

. 5B. )

9. +*D. +;

9ookkanlah %a&aban nda dengan uni


21/43

pabila menapai tingkat penguasaan ?*I atau lebih, nda dapatmeneruskan dengan egiatan Bela%ar 5. Bagus!


22/43

Kegiatan Belajar 2

Pewarnaan Peta danPewarnaan Garis(1 soal aplikasi

ebuah atlas akan sangat mudah dipahami kalau masing-masing daerahyang saling berbatasan mempunyai &arna yang berlainan. "uatu

masalah yang menarik ialah menentukan banyaknya minimum &arna yang

harus disediakan agar tu%uan tersebut ter&u%ud. Misalnya untuk me&arnai peta negara tetangga kita ustralia seperti diperlihatkan pada Gambar 6.+5.Pe&arnaan peta sama dengan pe&arnaan titik-titik graf dari gambar petatersebut sedemikian hingga tidak ada dua titik berdekatan yang mendapat&arna sama.

%

Dalam hal ini negara-negara bagiannya dan lautan yang mengelilinginyadi&akili oleh titik-titik. "elan%utnya pasangan titik yang me&akili daerah-daerah yang saling berbatasan dihubungkan dengan sebuah sisi, sehingga

model grafnya seperti tampak pada Gambar 6.+). >leh karena itu dera%atsuatu titik menerminkan banyaknya perbatasan yang mengelilingi daerahyang di&akili titik itu.


23/43

Ga!"ar 6.12 Ga!"ar 6.1#

b%ek apa yang akan dikon'ersikan sebagai titik graf85. 0ubungan apa yang dierminkan oleh sisi graf8 Pasangan titik apa sa%a

yang harus dihubungkan oleh sisi8). Merumuskan masalah nyata dalam bahasa teori graf.

ngka-angka pada Gambar 6.+) menyatakan kemungkinan penempatan

&arna, dan masih ada pula kemungkinan penempatannya yang lain. Dari graf tersebut tampak bah&a dengan empat maam &arna kita telah mampumembuat peta ustralia sedemikian hingga dua negara bagian yang saling

berbatasan dapat dibedakan dengan %elas.

1& $ewarnaan $eta

Contoh 1

/arnai peta pada Gambar 6.+:, kemudian tentukan bilangan

khromatiknya.

Ga!"ar 6.1$

%awab

Peta pada Gambar 6.+:, dapat dilukiskan bentuk grafnya seperti padaGambar 6.+; berikut ini.


24/43

Ga!"ar 6.1%

+. Pengurutan dera%at titik

Titik A @ B 9 2 D G 0Dera%attitik

6 ; : ) ) ) 5 5 5

5. Pe&arnaan titik Pertama tandailah titik A dengan angka +. Telusuri daftar titik tadi danamati gambar graphnya, ternyata titik 9 adalah titik pertama yang tidak

berdekatan dengan A. embali ke daftar titik, tandai titik @ dengan angka5, dan %uga titik dan 0, karena tidak berdekatan dengan @. Penelusuranketiga kalinya terhadap daftar titik akan menandai titik B dengan angka), lalu tandai pula titik 2, D, dan G dengan angka ). Dengan demikian

bilangan khromatik graf tersebut adalah ). !angkah-langkah tersebutdirangkum dalam bentuk tabel berikut."etiap graf G memiliki sebuah subgraf dari dera%at minimum sedikitnyaχ3G4 K L E m5 E N.


25/43

TitikWarna

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.+6 3a4 merupakan bagian dari peta merika "erikat. Grafnya beserta &arna 3label4 diperlihatkan pada Gambar 6.+6 3b4 denganmenggunakan algoritma /elsh dan Po&ell.

Ga!"ar 6.16 (a Ga!"ar 6.16 ("

Berikut ini tabel yang menun%ukkan hubungan antara titik, dera%at titik dan &arna.

Titik 1T O= 9> OM 9 /C TDera%at titik : : ) ) ) 5 5 +

/arna 3+4 354 3)4 3+4 354 354 3)4 3+4

Peta pada Gambar 6.+6 3a4 dapat di&arnai dengan ) &arna.


26/43

2& $ewarnaan garis

Pe&arnaan garis atau rusuk pada suatu graf adalah penentuan &arnarusuk-rusuk suatu graf sehingga setiap rusuk yang berdekatanmendapatkan &arna yang berbeda. 1kuran keber&arnaan suatu graf didefinisikan sama dengan ukuran keber&arnaan titik, yaitu mengaukepada banyaknya &arna yang memungkinkan sehingga setiap rusuk yang berdekatan mendapat &arna yang berbeda.


27/43

1ntuk graf lengkap n mempunyai sifat khusus mengenai bilangan

khromatiknya. Perhatikan beberapa ontoh graf lengkap berikut ini.

0ubungan antara banyaknya titik graf lengkap dan bilangan khromatik untuk graf itu dapat dirumuskan dalam teorema berikut ini.

Teorema 2

χ3 n4 F n, %ika n gan%il dan n +

χ3 n4 F n-+, %ika n genap


28/43

Contoh 3

χ3 ;4 F ; χ3 64 F ; χ3 4 χ3 ?4 F .

Teorema 3


29/43

Contoh 5

"ilakan nda istirahat se%enakH

"etelah nda ukup istirahat, ingat-ingat kembali dan pahami benar uraian di atas. emudian ker%akanlah soal-soal berikut ini sebagai latihan.

+4 "usunlah model graf untuk me&arnai +; bola sodok sehingga bola-bolaitu disusun seperti berikut.

54 "ekolah $0arapan Bangsa( merenanakan seminar pendidikanmatematika bagi anak-anak. da enam pembiara tampil dalamkesempatan yang berbeda, kegiatan tersebut akan memakan &aktuterlalu lama. kan tetapi %uga tidak diharapkan pembiara-pembiaratertentu tampil pada saat yang bersamaan. Pimpinan sekolahmenghendaki seminar ini berlangsung tidak lebih dari empat babak.Bagaimanakah kegiatan ini di%ad&alkan %ika pembiara-pembiara yangsebaiknya tidak tampil pada saat yang bersamaan ditandai dengan $(

pada tabel berikut.

LA!"HAN

1ntuk memperdalam pemahaman nda mengenai materi di atas,ker%akanlah latihan berikutH


30/43

Nama pembicara A B C D E F

A

B

C

D

E

* *

* *

*

*

*

*

)4 Berilah &arna pada garis 3rusuk4 graf berikut, kemudian tentukan

bilangan khromatiknya.

:4 Tentukan bilangan khromatik dari graf berikut.

Periksa dan teliti kembali %a&aban nda, sekarang ookkan %a&abannyadengan kuni %a&aban berikut ini.


31/43

Kun'i %awaban "atihan

+4 Model graf dari soal tersebut adalah sebagai berikut.

0ubungan antara titik, dera%at titik, dan &arna ditun%ukkan pada tabel berikut ini.

Titik

Derajat

Warna

G

6

(1)

H

6

(2)

K

6

(3)

B

(2)

C

(3)

D

(1)

F

(3)

I

(3)

!

(2)

"

(1)

#

(1)

$

(2)

A

2

(1)

E

2

(2)

%

2

(3)

minimum banyaknya &arna yang harus disediakan untuk me&arnai +; bola sodok sehingga bola-bola yang saling bersentuhan berbeda&arnanya adalah ) &arna.

54 Masalah ini dapat dimodelkan dengan graf. "etiap pembiara di&akilioleh sebuah titik. "etiap sisi menerminkan dua pembiara tidak

diharapkan tampil pada saat yang bersamaan.


32/43

Grafnya adalah sebagai berikut.

ngka me&akili &arna yang dapat diberikan kepada titik graf. /arna-

&arna ini me&akili babak pembiara tampil di forum. Dari gambar itudapat diamati bah&a titik-titik graphnya dapat di&arnai dengansekurang-kurangnya : maam &arna.


33/43

Pe&arnaan peta sama dengan pe&arnaan titik-titik pada graf hasil pemodelan dari gambar peta tersebut sedemikian hingga tidak ada duatitik berdekatan yang mendapat &arna sama.

!angkah-langkah yang dilakukan dalam pemodelan dengan graf ialah menentukan#+. >b%ek apa yang akan dikon'ersikan sebagai titik graf85. 0ubungan apa yang dierminkan oleh sisi-sisi graf8 Pasangan titik

apa sa%a yang harus dihubungkan oleh sisi8

). Merumuskan masalah nyata dalam bahasa teori graf.

+4 Graf bipartit lengkap ,:

sisinya 3rusuknya4 dapat di&arnai

minimal ....

. ) &arnaB. : &arna9. &arnaD. ++ &arna

54 Graf lengkap +*

rusuknya dapat di&arnai minimal dengan ....

. +* &arnaB. &arna9. ? &arnaD. &arna

)4 Peta berikut ini dapat di&arnai minimal dengan ....

#AN$KUMAN

!E% &O#MA!"& 2

Pilihlah satu %a&aban yang paling tepatH


34/43

. 6 &arnaB. ; &arna

9. : &arnaD. ) &arna

:4 Peta di samping dapat di&arnai minimal dengan ....

. ) &arnaB. : &arna9. ; &arnaD. 6 &arna

;4 Perhatikan gambar peta berikutH

Peta tersebut dapat di&arnai minimal dengan ..... 6 &arnaB. : &arna9. ) &arna

D. 5 &arna

64 Peta berikut dapat di&arnai minimal dengan ....


35/43

. 5 &arnaB. ) &arna

9. : &arnaD. ; &arna

4 Graf lengkap +;

rusuknya dapat di&arnai minimal dengan ....

. +5 &arnaB. +) &arna9. +: &arnaD. +; &arna

?4 Perhatikan graf berikut ini

"isi 3rusuk4 graf tersebut dapat di&arnai minimal dengan ..... 5 &arnaB. ) &arna9. : &arnaD. 6 &arna

4 Peta berikut ini dapat di&arnai minimal dengan ..... &arnaB. ; &arna

9. ) &arnaD. 5 &arna

+*4 "isi 3rusuk4 dari graf berikut dapat di&arnai minimal dengan ....


36/43

. 6 &arnaB. ; &arna

9. : &arnaD. ) &arna

9ookkanlah %a&aban nda dengan uni


37/43

+uni -awa"an Tes or!atif (es )ormatif 1

+4 9 Titik =5

=+

=)

=:

=;

Dera%at titik : ) ) ) )

/arna 3+4 354 3)4 354 3)4

54 B Graf lengkap G dengan ; titik mempunyai bilangan khromatik ;.)4 Titik-titik B, D, A, G,


38/43

(es )ormatif 2

+4 9 Bilangan khromatik sisi 3rusuk4 ,: F maQ 3,:4 F .54 B Bilangan khromatik rusuk

+* F +* - + F .

)4 9 Pemodelan grafnya adalah sebagai berikut.

Titik D B C E F A

Derajat titik 3 3 3 3 2

Warna (1) (2) (2) (3) () (1)

:4 Pemodelan grafnya adalah sebagai berikut


39/43

Titik G D E F C I H B A J

Derajat titik 4 4 4 4 3 3 3 3 2 2

Warna (1) (1) (2) (2) (2) (2) (3) (3) (1) (1)

;4 D Pemodelan grafnya adalah sebagai berikut.

64 Pemodelan grafnya adalah sebagai berikut.

4 D Bilangan khromatik rusuk +;

F +;.

?4 B


40/43

4 9 Pemodelan grafnya adalah sebagai berikut.

Titik A D B 9 G @

Dera%at titik ; : : ) 5 5 5

/arna 3+4 354 3)4 354 3+4 3)4 3)4

+*4 B


41/43

Daftar Pustaka

Budayasa, 2. 3+4. Matematika *iskrit + . "urabaya# 1ni'ersity Press22P "urabaya.

Deo, O. 3+:4. ,raph (heor- with .ppli'ation to Engineering an/ aComputer 0'ien'e. Oe& Delhi# Prentie-0all 2nternational, 2n.

0arary, @. 3+64. ,raph (heor-. 9alifornia# ddison /esley Publishing9ompany.

Mayeda, /. 3+54. ,raph (heor-. Oe& Cork#


42/43

Glosariu!

Ajasen

Dua buah titik disebut ajasen, %ika kedua titik tersebut merupakan titik-titik u%ung dari sisi yang sama.

Algoritma lgoritma merupakan prosedur atau aturan. 9ontoh# algoritma /elshdan Po&ell.

Bilangan Khromatik

Bila suatu graf G dapat di&arnai minimal dengan n &arna, maka Gdikatakan memiliki bilangan khromatik n.

Derajat titik Dera%at titik yaitu %umlah atau banyaknya sisi yang insiden dengantitik .

Insiden


43/43

Pewarnaan sisi (pewarnaan peta)

Pe&arnaan sisi 3pe&arnaan peta4 sama dengan pe&arnaan titik-titik

pada graf hasil pemodelan dari gambar peta tersebut sedemikianhingga tidak ada dua titik berdekatan yang mendapat &arna sama.

Pewarnaan garis

Pe&arnaan garis atau rusuk pada suatu graf adalah penentuan &arnarusuk-rusuk suatu graf sehingga setiap rusuk yang berdekatanmendapatkan &arna yang berbeda.

ikel

"ikel adalah suatu sirkuit yang tidak mengulang sebarang titikinternalnya 3titik dalamnya4.

irkuit

!intasan u-', dengan u F ' 3titik a&al sama dengan titik akhir4 disebutsirkuit.

modul 6. pewarnaan graf (2x pert)

Documents