alg welch powell

ALGORITMA WELCH-POWELL

Disusun untuk memenuhi tugas mata kuliah Teori Graph yang dibimbing

oleh Ibu Riski Nur I.D.,M.Si

Oleh:

LEDI DWI LISWANTO (130401060012)

M. DEDDY SHOBIKH (130401060172)

NISWATUL HAMIDAH (130401060128)

NURHADI WAHYU MUSTOFA (130401060093)

ZUROIDAH AMALIYAH (136401060003)

PROGRAM STUDI PENDIDIKAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS KANJURUHAN MALANG

2015

1

ALGORITMA WELCH-POWELL

Algoritma Welch-Powell

Ada tiga macam pewarnaan graf, yaitu pewarnaan simpul pewarnaan sisi,

dan pewarnaan wilayah (region). Pewarnaan simpul adalah memberi warna pada

simpul-simpul suatu graf sedemikian hingga tidak ada dua simpul bertetangga

yang mempunyai warna yang sama. Kita dapat memberikan sebarang warna pada

simpul-simpul asalkan berbeda dengan simpul-simpul tetangganya.

Dalam pewarnaan graf, kita tidak hanya sekedar mewarnai simpul-simpul

dengan warnakita tidak hanya sekedar mewarnai simpul-simpul dengan warnakita

tidak hanya sekedar mewarnai simpul-simpul dengan warna yang berbeda dengan

warna simpul tetangganya saja, namun kita juga menginginkan agar jumlah warna

yang digunakan sesedikit mungkin. Jumlah warna minimumyang dapat digunakan

untuk mewarnai simpul-simpul disebut bilangan kromatik dari graf G, yang

dinotasikan dengan χ (G). Gambar di bawah ini memperlihatkan sebuah graf

dengan χ(G) = 3.

Tiga warna cukup untuk mewarnai graf ini.

Algoritma Welch-Powell adalah suatu cara yang efisien untuk mewarnai

sebuah graf G, namun algoritma ini hanya memberikan batas atas untuk χ(G). Jadi

algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan

untuk mewarnai G. Menentukan χ(G) sebenarnya sangat sulit kecuali dalam

kasus-kasus sederhana seperti pada contoh-contoh berikut.

2

Langkah-langkah dalam algoritma Welch-Powell:

1. Menulis derajat tiap titik pada graf lalu urutkan titik-titik dari dari graf

menurut derajatnya dari tinggi ke rendah (bila terdapat lebih dari satu

titik berderajat sama maka ambil sebarang titik dari titik-titik yang

berderajat sama tersebut). Buat daftar titik-titik yang berdekatan pada

urutan titik-titik yang diurutkan sebelumnya.

2. Warnai titik pertama pada daftar tersebut dan titik-titik belum

berwarna yang tidak berdekatan dengan titik itu.

3. Warnai titik berikutnya yang belum berwarna dengan warna yang

belum digunakan pada titik pertama pada daftar titik itu dan titik-titik

yang tidak berdekatan pada titik berikutnya tersebut.

4. Lakukan hal itu pada semua titik dalam daftar secara terurut, berikan

warna baru ini pada setiap titik berikutnya yang belum terwarna

sampai semua titik pada graf terwarnai.

Contoh

Dengan menggunakan algoritma Welch-Powell, titik-titik pada graf di atas

akan diwarnai.

Langkah 1 : menulis derajat semua titik dan diurutkan

deg (F) = 5; deg (A) = 3; deg (E) = 3; deg (D) = 3; deg (B) = 3; deg (C) =

2; deg (G) = 1

3

Daftar titik yang berdekatan

F : A, E, D, B, G

A : F, E, B

E : F, A, D

D : F, E, C

B : F, A, C

C : D, B

G : F

Langkah 2 : Warnai titik pertama pada daftar tersebut dan titik-titik belum

berwarna yang tidak berdekatan dengan titik itu.

F : A, E, D, B, G (Biru)

A : F, E, B

E : F, A, D

D : F, E, C

B : F, A, C

C : D, B (Biru)

G : F

Langkah 3 : Warnai titik berikutnya yang belum berwarna dengan warna

yang belum digunakan pada titik pertama pada daftar titik itu dan titik-titik

yang tidak berdekatan pada titik berikutnya tersebut.


A : F, E, B (Kuning)

E : F, A, D

D : F, E, C (Kuning)

B : F, A, C

C : D, B (Biru)

G : F (Kuning)

4

Langkah 4 : Lakukan hal itu pada semua titik dalam daftar secara terurut,

berikan warna baru ini pada setiap titik berikutnya yang belum terwarna

sampai semua titik pada graf terwarnai.


A : F, E, B (Kuning)

E : F, A, D (Hijau)

D : F, E, C (Kuning)

B : F, A, C (Hijau)

C : D, B (Biru)

G : F (Kuning)

Dari keempat langkah di atas, titik F dan C diberi warna biru, titik A, D,

dan G diberi warna kuning, dan titik E dan B diberi warna hijau. Dengan

demikian graf pada gambar dapat diwarnai dengan tiga warna.

Penyajian daftar berdekatan membuat algoritma Welch-Powell mudah

digunakan karena titiknya mudah ditandai ketika diwarnai, sehingga cukup

memperhatikan titik belum berwarna sisanya dalam proses pewarnaan itu.

5

Latihan Soal

1. Berilah warna pada graf di bawah ini dengan menggunakan algoritma

Welch-Powell.

Penyelesaian:


deg (V5) = 5; deg (V3) = 5; deg (V1) = 4; deg (V2) = 4; deg (V6) = 4; deg

(V4) = 2


V5 : V1, V2, V3, V4, V6

V3 : V1, V2, V3, V4, V5

V1 : V2, V3, V5, V6

V2 : V1, V3, V5, V6

V6 : V1, V2, V3, V5

V4 : V3, V5

Langkah 2 : Warnai titik pertama pada daftar tersebut dan titik-titik

belum berwarna yang tidak berdekatan dengan titik itu.

V5 : V1, V2, V3, V4, V6 (BIRU)

V3 : V1, V2, V4, V5, V6

V1 : V2, V3, V5, V6

V2 : V1, V3, V5, V6

V6 : V1, V2, V3, V5

V4 : V3, V5

6

Langkah 3 : Warnai titik berikutnya yang belum berwarna dengan

warna yang belum digunakan pada titik pertama pada daftar titik itu

dan titik-titik yang tidak berdekatan pada titik berikutnya tersebut.

V5 : V1, V2, V3, V4, V6 (BIRU)

V3 : V1, V2, V4, V5, V6 (HIJAU)

V1 : V2, V3, V5, V6

V2 : V1, V3, V5, V6

V6 : V1, V2, V3, V5

V4 : V3, V5

Langkah 4 : Lakukan hal itu pada semua titik dalam daftar secara

terurut, berikan warna baru ini pada setiap titik berikutnya yang

belum terwarna sampai semua titik pada graf terwarnai.

V5 : V1, V2, V3, V4, V6 (BIRU)

V3 : V1, V2, V4, V5, V6 (HIJAU)

V1 : V2, V3, V5, V6 (KUNING)

V2 : V1, V3, V5, V6 (MERAH)

V6 : V1, V2, V3, V5 (HITAM)

V4 : V3, V5 (KUNING)

Dari keempat langkah di atas, titik V1 diberi warna biru, titik V3 diberi

warna hijau, titik V1 dan V4 diberi warna kuning, titik V2 diberi warna merah,

dan titik V6 diberi warna hitam. Dengan demikian graf pada gambar dapat

diwarnai dengan lima warna.

7

2. Berilah warna pada graf di bawah ini dengan menggunakan algoritma

Welch-Powell.

Penyelesaian:


akan diwarnai.


deg (I) = 6; deg (D) = 5; deg (B) = 4; deg (E) = 4; deg (F) = 4; deg (G) = 4;

deg (A) = 3; deg (C) = 3


I : A, B, D, E, G, H

D : B, C, E, F, I

B : A, C, D, I

E : D, F, I, G

F : D, E, G, H

G : E, F, H, I

A : B, I, H

C : B, D, H



I : A, B, D, E, G, H (BIRU)

D : B, C, E, F, I

8

B : A, C, D, I

E : D, F, I, G

F : D, E, G, H (BIRU)

G : E, F, H, I

A : B, I, H

C : B, D, H (BIRU)





D : B, C, E, F, I (HIJAU)

B : A, C, D, I

E : D, F, I, G


G : E, F, H, I (HIJAU)

A : B, I, H (HIJAU)

C : B, D, H (BIRU)





D : B, C, E, F, I (HIJAU)

B : A, C, D, I (KUNING)

E : D, F, I, G (KUNING)


G : E, F, H, I (HIJAU)

A : B, I, H (HIJAU)

C : B, D, H (BIRU)

9

Dari keempat langkah di atas, titik I, F, dan C diberi warna biru, titik D, G,

A diberi warna hijau, dan titik B dan E diberi warna kuning. Dengan demikian

graf pada gambar dapat diwarnai dengan tiga warna.

3. Perhatikan tabel matriks siswa dan bidang studi berikut ini.

Tabel di atas menunjukkan matriks tentang lima bidang studi (di label

dengan abjad) yang dipilih oleh delapan siswa (dilabel dengan angka).

Angka 1 diisikan sebagai elemen (i,j) matriks itu, jika siswa i memilih

bidang studi j. Sedangkan angka 0 diisikan sebagai elemen jika siswa i tidak

memilih bidang studi j. Contoh: siswa 1 memilih bidang studi B dan E

karena elemen (1,B) dan (1,E) adalah 1. Berdasarkan tabel di atas, tentukan

banyak jadwal ujian yang dapat dibuat sedemikian rupa sehingga semua

siswa dapat mengikuti ujian bidang studi itu tanpa ada kesulitan waktu

(kesulitan terjadi jika ada siswa yang harus mengikuti ujian dua bidang studi

atau lebih pada waktu yang bersamaan).

Penyelesaian:

Penyelesaian masalah membuat jadwal ujian ini sebenarnya ekuivalen

dengan masalah mencari bilangan kromatik suatu graf. Yang perlu diingat

adalah ujian dan bidang studi dapat dijadwalkan pada waktu yang sama jika

tidak ada siswa yang sama yang mengikuti ujian dua bidang studi itu.

10

Penjadwalan ujian itu dapat digambarkan sebagai sebuah graf, dan setiap

bidang studi ditunjukkan sebagai titiknya. Dua titik dihubungkan dengan

sebuah garis jika ada siswa yang memiliki kedua bidang studi itu. Sehingga

dapat ditafsirkan bahwa jika dua titik dihubungkan oleh garis maka ujian

dua bidang itu tidak dapat dilakukan bersamaan, karena akan ada siswa

yang mendapat kesulitan. Diberikan warna yang berbeda untuk titik-titik

semacam itu yang menunjukkan bahwa waktu ujiannya berbeda.

Kita gambar masalah graf di atas

Jadwalnya perlu dibuat sesedikit mungkin untuk memudahkan

pelaksanaannya. Sehingga perlu ditentukan bilangan kromatik graf di atas.


akan diwarnai.


deg (B) = 3; deg (A) = 2; deg (C) = 2; deg (D) = 2; deg (E) = 1


B : A, D, E

A : B, C

C : A, D

D : B, C

E : B



B : A, D, E (BIRU)

A : B, C

11

C : A, D (BIRU)

D : B, C

E : B




B : A, D, E (BIRU)

A : B, C (HIJAU)

C : A, D (BIRU)

D : B, C (HIJAU)

E : B (HIJAU)




B : A, D, E (BIRU)

A : B, C (HIJAU)

C : A, D (BIRU)

D : B, C (HIJAU)

E : B (HIJAU)

Dari keempat langkah di atas, titik B dan C diberi warna biru, titik A, D,

dan E diberi warna hijau. Dengan demikian graf pada gambar dapat diwarnai

dengan dua warna. Ujian bidang studi A, E, dan D dapat dilaksanakan bersamaan,

sedangkan ujian bidang studi B dan C dapat dilakukan bersama tetapi pada waktu

yang berbeda dengan ujian bidang studi A, E, dan D.

12

4. Ada 6 jenis zat kimia yang perlu disimpan di gudang. Beberapa pasang dari

zat itu tidak dapat disimpan di tempat yang sama, karena campuran gasnya

bersifat eksplosif. Untuk zat-zat semacam itu perlu dibangun ruang-ruang

terpisah yang dilengkapi ventilasi dan penyedot udara ke luar yang

berlainan. Lebih banyak minimum ruang yang diperlukan untuk dapat

menyimpan semua zat kimia itu dengan aman. Berikut ini adalah daftar

pasangan zat kimia yang tidak dapat disimpan di tempat yang aman.

Zat Kimia Tidak dapat bersama dengan zat kimia

A B, D

B A, D, E, F

C E

D A, B, F

E B, C

F B, D

Berapa banyak minimum ruangan berbeda untuk menyimpan semua zat

kimia itu secara aman?

Penyelesaian:

Soal tersebut dapat dibuat grafnya dengan titik menunjukkan “zat kimia”

dan garis menunjukkan “tidak dapat bersama dengan zat kimia”.

Gambar grafnya adalah sebagai berikut:

13


akan diwarnai.


deg (B) = 4; deg (D) = 3; deg (A) = 2; deg (E) = 2; deg (F) = 2; deg (C) = 1


B : E, A, D, F

D : A, B, F

A : B, D

E : C, B

F : B, D

C : E



B : E, A, D, F (BIRU)

D : A, B, F

A : B, D

E : C, B

F : B, D

C : E (BIRU)





D : A, B, F (HIJAU)

A : B, D

E : C, B (HIJAU)

F : B, D

C : E (BIRU)

14





D : A, B, F (HIJAU)

A : B, D (KUNING)

E : C, B (HIJAU)

F : B, D (KUNING)

C : E (BIRU)

Dari keempat langkah di atas, titik B dan C diberi warna biru, titik D dan E

diberi warna hijau dan titik A dan F diberi warna kuning.

Jadi, banyak minimum ruang berbeda atau terpisah yang dibutuhkan ada 3,

yaitu:

Ruang 1 menyimpan zat kimia B dan C

Ruang 2 menyimpan zat kimia D dan E

Ruang 3 menyimpan zat kimia A dan F

15

DAFTAR PUSTAKA

https://www.academia.edu/6794159/modul_pewarnaan_graph. Diakses pada 10

Desember 2015 Pukul 10.00 WIB.

alg welch powell

Documents