Makalah Pewarnaan Bidang Graf [09-10-2018]-1.docx

MAKALAH MATEMATIKA DISKRIT

“PEWARNAAN GRAF” Dra. Linda Rosmery Tambunan, M.Si.

Kelas : 3A Kelompok 7

Dian Veronica Wahyuni : 170384202001 Novi Budi Rahayu .S

: 170384202007

Lia Agustina

: 170384202038

Program Studi Pendidikan Matematika Fakultas Keguruan dan Ilmu Pendidikan Universitas Maritim Raja Ali Haji 2018

KATA PENGANTAR

Puji syukur kami panjatkan kehadirat Allah SWT yang telah memberikan rahmat serta karunia-Nya kepada kami sehingga kami berhasil menyelesaikan makalah ini yang berjudul “Pewarnaan Graf”. Kami menyadari bahwa makalah ini masih jauh dari sempurna, oleh karena itu kritik dan saran dari semua pihak yang bersifat membangun selalu kami harapkan demi kesempurnaan makalah ini. Akhir kata, kami sampaikan terima kasih kepada semua pihak yang telah berperan serta dalam penyusunan makalah ini dari awal sampai akhir. Semoga Allah SWT senantiasa meridhai segala usaha kita, Amin.

Tanjungpinang, 18 September 2018

Kelompok 7

1

DAFTAR ISI Kata Pengantar .......................................................................................................

1

Daftar Isi ................................................................................................................

2

Bab I. Pendahuluan 1.1

Latar Belakang ......................................................................................

3

1.2

Rumusan Masalah .................................................................................

3

1.3

Tujuan ...................................................................................................

3

Bab II. Pembahasan 2.1

Pewarnaan Graf .....................................................................................

4

A. Pewarnaan Bidang ...................................................................

4

B. Graf Dual dari Graf Planar ........................................................

5

C. Pewarnaan Map .........................................................................

7

Bab III. Penutup 3.1

Kesimpulan ..........................................................................................

8

3.2

Saran ....................................................................................................

8

Daftar Pustaka .........................................................................................................

9

2

BAB I PENDAHULUAN 1.1 Latar Belakang Dalam matematika dan ilmu komputer, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objekobjek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi. Dalam graf yang memenuhi syarat, di mana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (sudut atau simpul) yang digabungkan dengan kurva (garis atau sisi).

1.2 Rumusan Masalah 1) Apa itu pewarnaan bidang pada graf? 2) Bagaimana langkah melakukan pewarnaan? 1.3 Tujuan Untuk mencari solusi terefektif dan terefesien dalam memecahkan masalah berkenaan tentang pewarnaan graf.

3

BAB II PEMBAHASAN 2.1 Pewarnaan Graf Pewarnaan graf (graph coloring) adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik pada batas tertentu. Ada tiga macam pewarnaan graf : a) Pewarnaan simpul/titik. b) Pewarnaan sisi. c) Pewarnaan bidang. Pada pembahasan kali ini akan dijelaskan tentang pewarnaan bidang. A. Pewarnaan Bidang Pewarnaan bidang adalah memberi warna pada bidang sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama. Pewarnaan bidang hanya bisa dilakukan dengan membuat graf tersebut menjadi graf planar terlebih dahulu. Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan), seperti yang ditunjukkan gambar di bawah ini.

Gambar 1. Contoh Graf Planar Setelah terbentuk graf planar, lalu memberikan warna berbeda untuk setiap bidang yang berdekatan. Dan jumlah warna yang digunakan harus sedikit mungkin. Pewarnaan region dari suatu graf planar (graf bidang) G adalah suatu pemetaan warna-warna ke region-region dari graf G sedemikian hingga region-region yang bertetangga mempunyai warna yang berbeda. Gambar 2 menunjukkan contoh permasalahan pewarnaan region.

4

Gambar 2. Dalam pewarnaan graf, jumlah warna yang digunakan untuk mewarnai simpul, sisi, maupun bidang diusahakan sesedikit mungkin. Jumlah warna minimum yang dapat digunakan tersebut disebut bilangan kromatik graf G, disimbolkan dengan χ(G). Suatu graf G yang mempunyai bilangan kromatis k dilambangkan dengan χ(G) = k.

B. Graf Dual dari Graf Planar Dari suatu permasalahan pewarnaan region pada graf bidang, bisa kita bawa ke permasalahan pewarnaan simpul dengan membangun sebuah graf dual dari graf bidang tersebut.

Cara membentuk graf dual. Misal terdapat sebuah graf bidang M. Dalam setiap region dari M, pilih sebuah titik. Jika dua buah region mempunyai sebuah sisi bersama, maka titik-titik yang terkait dapat dihubungkan dengan sebuah garis melalui sisi bersama tersebut. Garis-garis ini akan membentuk kurva. Kurva-kurva ini digambarkan sedemikian hingga agar tidak bersilangan. Dengan demikian kurva-kurva tersebut membentuk sebuah graf yang disebut sebagai graf dual dari M. Gambar 5 menunjukkan graf dual dari graf planar pada gambar 4.

Gambar 4.

5

Gambar 5. Permasalahan pewarnaan region seperti yang ditunjukkan pada gambar 4 dapat kita bawa ke masalah pewarnaan simpul, dengan kita buat graf dual dari gambar 4 seperti ditunjukkan dalam gambar 6.

Gambar 6. Dengan algoritma Welch Powell (permasalahan pewarnaan simpul), Simpul :

v1

v2

v3

v4

v5

v6

Derajat :

4

4

4

4

4

4

Warna :

a

b

c

b

a

c

ℵ(G) = 3. Hasil ini sama dengan hasil dari pewarnaan region pada gambar 4.

Contoh 2. Permasalahan pada gambar dibawah ini juga dapat kita bawa ke masalah pewarnaan simpul, dengan kita buat graf dual seperti ditunjukkan pada gambar .

6

menjadi Dengan algoritma Welch Powell, Simpul :

v4

v8

v1

v2

v5

v7

v3

v6

Derajat :

6

5

3

3

3

3

2

1

Warna :

a

b

a

b

c

d

c

b

ℵ(G) = 4. Hasil ini sama dengan hasil dari pewarnaan region pada gambar. Ini adalah bukti bahwa algoritma welch Powell memang tidak selalu menghasilkan warna minimum.

C. Pewarnaan Map

Gambar 3. Peta merupakan contoh pewarnaan bidang. Misalkan suatu map M. Dua region dari map M dikatakan berdampingan jika mereka mempunyai suatu ruas persekutuan. Yang dimaksud dengan pewarnaan map yaitu dengan pemberian warna yang berbeda pada setiap region yang berdampingan.

7

BAB III PENUTUP 3.1 Kesimpulan Teori graf merupakan pokok bahasan yang sudah lama tapi sampai sekarang masih memiliki terapan di berbagai persoalan dalam kehidupan sehari-hari, salah satu contohnya adalah penggunaan pewarnaan graf pada pengaturan lampu lalu lintas di perempatan jalan & peyusunan jadwal dengan metode pewarnaan graf.

3.2 Saran Saat mengerjakan pewarnaan graf memerlukan ketelitian dan ketekunan agar perhitungan yang dilakukan tidak mengalami kekeliruan.

8

DAFTAR PUSTAKA

https://rahadikusuma.blogspot.com/2013/12/matematika-diskrit-pewarnaan-graf_30.html https://sisfo02.files.wordpress.com/2012/05/bab-6-pewarnan-graf.pdf https://slideplayer.info/slide/3629515/ http://dhukhasyamsy.blogspot.com/2013/05/pewarnaan-graf-graph-coloring.html

9