BAB II. Konsep Dasar

BAB II Konsep Dasar

BAB II Konsep Dasar

2.1 Definisi Graf Graf G = (VG ,EG) terdiri dari himpunan tidak kosong VG , disebut himpunan titik, dan himpunan EG, disebut himpunan sisi, yang beranggotakan pasangan tak terurut dari anggota berbeda di VG. Sebagai contoh, graf G = (VG, EG) dengan VG = {v1 , v2 , v3} dan EG = {v1v2, v1v3 } digambarkan pada gambar 2.1. Jika u, v ∈ VG dan uv ∈ EG, maka u dan v disebut ujung-ujung dari uv. Dengan demikian, pada graf G di atas, sisi v1v2 mempunyai ujung v1 dan v2, sisi v1v3 mempunyai ujung v1 dan v3. Titik v dikatakan terkait oleh sisi e jika titik tersebut merupakan ujung dari sisi e. Dua buah sisi dikatakan saling terkait jika keduanya memiliki salah satu ujung yang sama. Graf sederhana adalah graf yang tidak ada dua sisi yang memiliki sepasang ujung yang sama. Untuk selanjutnya, setiap graf yang dimaksud dalam tugas akhir ini adalah graf sederhana. Graf dinamakan demikian dikarenakan graf dapat direpresentasikan secara grafis. Untuk graf G, setiap u ∈ VG digambarkan dengan titik dan setiap uv ∈ EG, digambarkan dengan garis yang menghubungkan titik u dengan titik v. Tidak ada cara yang unik dalam menggambarkan graf. Posisi titik dan garis dapat digambar secara bebas.

5 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II Konsep Dasar

v1

v2

v3

Gambar 2.1. Graf G.

Dua buah titik yang berbeda dikatakan bertetangga jika dua titik tersebut dihubungkan oleh suatu sisi. Pada gambar diatas, v1 bertetangga dengan v2 dan v3; v2 bertetangga dengan v1, dan v3 bertetangga dengan v1. Pada graf sederhana, derajat dari titik v didefinisikan sebagai banyaknya tetangga dari titik v. Matriks ketetanggaan A(G)=[aij] dari G dengan n = |VG| dan VG = {v1, ...,vn} adalah suatu matriks berukuran n x n dengan:

⎧⎪ 1, a ij = ⎨ ⎪⎩ 0 ,

jik a v i v j ∈ E G ; jik a v i v j ∉ E G ;

Gambar 2.2 memperlihatkan suatu graf beserta matriks ketetanggaannya. v1

v2 v1 v2 v3 v4

v3

v1 0 1 1 0

v2 v3 v4 1 1 0 0 0 1 0 0 1 1 1 0

v4

G

A(G) Gambar 2.2


BAB II Konsep Dasar

2.2 Himpunan Kabur (Fuzzy Set) Teori himpunan kabur merupakan suatu teori tentang konsep penilaian yang batasannya tidak begitu jelas atau memiliki elastisitas. Dengan nilai/derajat elastisitas ini himpunan kabur mempertegas sesuatu yang kabur, misalkan terdapat kalimat atau pernyataan ‘setengah baya’. Pertanyaan yang muncul, “Berapa kriteria umur yang dapat dikatakan setengah baya ?”. Dapat ditentukan bahwa orang yang disebut ‘setengah baya’ mempunyai kriteria usia berkisar antara 35-55 tahun. Bagaimana dengan yang berusia 34 tahun. Dapatkah dikatakan ‘setengah baya’?. Crisp set atau sistem jangkauan menjawab dengan tegas bahwa 34 tahun tidak termasuk ‘setengah baya’ (bernilai 0), namun himpunan kabur (fuzzy set) dapat menyatakan dengan leluasa bahwa usia 34 tahun juga termasuk setengah baya dengan derajat tertentu. Himpunan kabur adalah sekumpulan obyek x dengan masing-masing obyek memiliki nilai keanggotaan (membership function), disimbolkan dengan μ ( x ) . Nilai ini dipetakan ke dalam range [0,1]. Jika Χ adalah sekumpulan obyek, maka himpunan kabur A pada X adalah himpunan dengan sepasang anggota.

A = {( x, μ A ( x)) x ∈ Χ} Sebagai contoh, jika ingin didefinisikan himpunan bilangan yang mendekati 10, maka dapat dituliskan dengan menggunakan himpunan kabur sebagai berikut :

A = {( x, μ A ( x)) μ A ( x) = (1 + ( x − 10) 2 )−1 , x ∈ X } .


BAB II Konsep Dasar

Grafik yang mewakili nilai μ A ( x ) adalah :

1 0,5

0 5

10

15

x

Gambar 2.3. Grafik kabur untuk bilangan yang mendekati 10

2.2.1 Operasi Himpunan Kabur Misalkan A dan B himpunan kabur pada semesta pembicaraan X.

Himpunan kabur A dan B dikatakan sama ( A=B ) jika

μ A ( x) = μ B ( x), ∀x ∈ X

A termuat di B ( A ⊆ B ) jika

μ A ( x) ≤ μ B ( x), ∀x ∈ X

Gabungan (union) dari himpunan kabur A dan B, dinotasikan dengan A ∪ B , didefinisikan sebagai A ∪ B = {( x, μ A∪ B ( x)) x ∈ X } dengan

μ A∪ B ( x) = ( μ A ( x) ∨ μ B ( x)), ∀x ∈ X

Irisan (intersection) dari himpunan kabur A dan B, dinotasikan dengan A ∩ B , didefinisikan sebagai A ∩ B = {( x, μ A∩ B ( x)) x ∈ X } dengan

μ A∩ B ( x) = ( μ A ( x) ∧ μ B ( x)), ∀x ∈ X

Komplemen dari himpunan kabur A, dinotasikan A , didefinisikan sebagai

A = {( x, μ A ( x)) x ∈ X } dengan 8 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II Konsep Dasar

μ A ( x) = 1 − μ A ( x), ∀x ∈ X

Produk (product) dari himpunan kabur A dan B, dinotasikan dengan AB, didefinisikan sebagai AB = {( x, μ AB ( x)) x ∈ X } dengan

μ AB ( x) = μ A ( x) μ B ( x), ∀x ∈ X

Contoh : Misalkan X = {1, 2, 3, 4, 5, 6} . Misalkan pula μ A (3) = 0.8, μ A (6) = 0.6 , μ B (3) = 0.7, μ B (6) = 0.5 , maka :

μ A∪ B (3) = 0.8

μ A∩ B (6) = 0.5

μ A (1) = 1, μ A (3) = 0.2

μ AB (3) = 0.56, μ AB (6) = 0.3

2.2.2 Fungsi Keanggotaan Fungsi keanggotaan (membership function) yang sering digunakan terdiri dari beberapa jenis, yaitu : 1. Fungsi-S (S-function) Aturan dari fungsi-S ini adalah : ⎧0 ⎪ 2 ⎪2[( x − a) /(c − a )] S ( x; a, b, c) = ⎨ 2 ⎪1 − 2[( x − a ) /(c − a)] ⎪⎩1 dengan b = (a+c)/2

jika x < a jika a ≤ x ≤ b jika b ≤ x ≤ c jika x > c


BAB II Konsep Dasar

Gambar grafik fungsi keanggotaannya adalah :

1 S

0 a

b

c

x

Gambar 2.5. Grafik fungsi keanggotaan S

Contoh penerapan dari fungsi S : Χ adalah himpunan yang terletak antara 0 sampai 120, dimana x mewakili usia. A adalah himpunan kabur yang dianggap mempunyai usia tua. ⎧0 −2 −1 ⎩{1 + [( x − 40) / 5] }

μ A ( x) = ⎨

0 ≤ x ≤ 40 40 ≤ x ≤ 120

Di sini terlihat bahwa untuk usia yang melebihi usia 40, nilai anggotanya terus naik dan pada usia 45 akan mempunyai nilai 0,5. Jadi pada usia 45 merupakan titik penyeberangan dan pada usia selanjutnya, nilai keanggotaan akan terus naik menuju nilai 1. Jika digambarkan nilai fungsi >0 di atas, maka bentuknya akan mendekati bentuk fungsi S.


BAB II Konsep Dasar

2. Fungsi-π (π-function) Aturan fungsi-π diperoleh dari modifikasi aturan fungsi-S, sebagai berikut : jika x ≤ c ⎧ S ( x; c − b, c − b / 2, c) ⎩1 − S ( x; c, c + b / 2, c + b) jika x ≥ c

π ( x; b, c) = ⎨

Gambar grafik fungsi keanggotaannya adalah : 1 S

0 c-b

c-b/2

c

c+b/2

c+b

x

Gambar 2.6. Grafik fungsi keanggotaan π

Contoh penerapan fungsi π : Misalkan X adalah himpunan yang beranggotakan bilangan yang terletak antara 70 sampai 110. A adalah himpunan kabur yang diasumsikan sebagai bilangan yang mendekati nilai 90. Carilah nilai dari masing-masing nilai himpunan X. Misalkan fungsi keanggotaan adalah μ A ( x) , maka setiap anggota himpunan A dapat ditulis sebagai berikut : A = {( x, μ A ( x)) | x ∈ X dengan μ A ( x) = {1 + [1/100( x - 90)2]}-1 .

Di sini terlihat bahwa bilangan 90 memiliki nilai tertinggi yaitu 1, sedangkan nilai keanggotaan yang lain sesuai dengan fungsi keanggotaannya. Di sini juga terlihat 11 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II Konsep Dasar

bahwa nilai-nilai di atas jika digambarkan akan menghasilkan bentuk mendekati bentuk fungsi π.

3. Fungsi keanggotaan segitiga (Triangular membership function) Aturan untuk bentuk segitiga ini adalah :

⎧0 ⎪ Τ( x; a, b, c) = ⎨( x − a) /(b − a ) ⎪(c − x) /(c − b) ⎩

jika x < a, x > c jika a ≤ x ≤ b jika b ≤ x ≤ c

Gambar grafik fungsi keanggotaannya adalah : 1

0

a

b

c

Gambar 2.7. Grafik fungsi keanggotaan segitiga

4. Fungsi keanggotaan trapesium (Trapezoidal membership function) Aturan untuk bentuk trapesium ini adalah : ⎧0 ⎪1 ⎪ Ζ( x; a, b, c, d ) = ⎨ ⎪( x − a) /(b − a) ⎪⎩(d − x) /(d − c)

jika x < a, x < d jika b ≤ x ≤ c jika a ≤ x ≤ b jika c ≤ x ≤ d


BAB II Konsep Dasar

Gambar grafik fungsi keanggotaannya adalah :

μ 1

0 a

b

c

d

x

Gambar 2.8. Grafik fungsi keanggotaan trapesium

2.2.3 Variabel Linguistik Variabel linguistik adalah variabel yang bernilai kata/kalimat, bukan angka. Sebagai alasan menggunakan kata/kalimat daripada angka karena peranan linguistik kurang spesisifik dibandingkan angka, namun informasi yang disampaikan lebih informatif. Variabel linguistik ini merupakan konsep penting dalam logika kabur dan memegang peranan penting dalam beberapa aplikasi. Jika “kecepatan” adalah variabel linguistik, maka nilai linguistik untuk variabel kecepatan adalah, misalnya “lambat”, “sedang”, “cepat”. Hal ini sesuai dengan kebiasaan manusia sehari-hari dalam menilai sesuatu, misalnya : “Ia mengendarai mobil dengan cepat”, tanpa memberikan nilai berapa kecepatannya. Konsep tentang variabel linguistik ini diperkenalkan oleh Lofti Zadeh. Variabel linguistik menurut Zadeh dikarakteristikkan oleh : (X, T(x), U, M)


BAB II Konsep Dasar

dengan : X

=

nama variabel.

T(x) atau T

=

semesta pembicaraan untuk x atau disebut juga nilai linguistik dari x .

U

=

jangkauan dari setiap nilai kabur untuk x yang dihubungkan dengan variabel dasar U.

M

=

aturan semantik yang menghubungkan setiap Χ dengan artinya.

Sebagai contoh, jika X = “kecepatan”, dengan U[0, 100] dan T(kecepatan) = {lambat, sedang, cepat}, maka M untuk setiap X, M ( x ) adalah M(lambat), M(sedang), M(cepat), dengan : M(lambat)

=

himpunan kaburnya “kecepatan dibawah 40 km/jam” dengan fungsi keanggotaan μ lambat.

M(sedang)

=

himpunan kaburnya “kecepatan mendekati 55 km/jam” dengan fungsi keangotaan μ sedang.

M(cepat)

=

himpunan kaburnya “kecepatan diatas 70 km/jam” dengan fungsi keanggotaan μ cepat.


BAB II Konsep Dasar

Gambar grafik fungsi keanggotaannya sebagai berikut : Degree of membership

1 lambat

sedang

cepat

0 40

55

70 x

Gambar 2.4. Grafik fungsi keanggotaan kecepatan

2.3 Graf Kabur (Fuzzy Graph) Graf G = (V , Eμ ) terdiri dari himpunan tidak kosong V, disebut himpunan titik, dan himpunan Eμ , disebut himpunan sisi kabur, yang dapat dikarakteristikkan oleh matriks μ = ( μij )i , j∈V dengan

μij = μ E ({i, j}) ∀i, j ∈ V , i ≠ j dan μ E : V × V → I adalah fungsi keanggotaan. Dari definisi diatas,

μij ∈ I merepresentasikan tingkat intensitas sisi {i,j},

i, j ∈ V dengan i ≠ j . Di sini, fuzzy graph dapat pula dilambangkan dengan G = (V , μ ) .

Himpunan I tersusun secara linear, dengan demikian ekspresi " μij ≺ μi ' j ' " dapat dikatakan ”tingkat intensitas sisi {i,j} lebih kecil dari tingkat intensitas sisi {i’,j’}”. Graf G = (V , E ) dapat dipandang sebagai graf kabur G = (V , ( μij )i , j∈V ) dengan ⎧1 ⎩0

μij = ⎨

jika i, j ∈ E jika i, j ∉ E 15

Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II Konsep Dasar

Untuk ilustrasi, perhatikan graf kabur G = (V , E ) dengan V = {v1, v2, v3, v4}, nilai fungsi keanggotaan I = { 1 4 , 1 3 , 1 2} , dan tingkat intensitas sisi dinyatakan pada tabel 2.1. v1

v2

v3

v4

v1

0

1/2

1/4

1/4

v2

1/2

0

1/3

1/3

v3

1/4

1/3

0

1/2

v4

1/4

1/3

1/2

0

Tabel 2.1

a. Matriks ketetanggaan G dengan tingkat intensitas sisi

1

2

v1

v2

v3

v4

v1

0

1

0

0

v2

1

0

0

0

v3

0

0

0

1

v4

0

0

1

0

Tabel 2.2

Selanjutnya, dari matriks ketetanggaan ini dapat digambarkan dalam bentuk graf sebagai berikut : v1

v2

v4 v3

Gambar 2.9. μ =

1

2


BAB II Konsep Dasar

b. Matriks ketetanggaan G dengan tingkat intensitas sisi

1

3

v1

v2

v3

v4

v1

0

1

0

0

v2

1

0

1

1

v3

0

1

0

1

v4

0

1

1

0

Tabel 2.3

Selanjutnya, dari matriks ketetanggaan ini dapat digambarkan dalam bentuk graf sebagai berikut : v1

v2

v4 v3

Gambar 2.10. μ =

1

3

c. Matriks ketetanggaan G dengan tingkat intensitas sisi

1

4

v1

v2

v3

v4

v1

0

1

1

1

v2

1

0

1

1

v3

1

1

0

1

v4

1

1

1

0

Tabel 2.4

Selanjutnya, dari matriks ketetanggaan ini dapat digambarkan dalam bentuk graf sebagai berikut : 17 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II Konsep Dasar

v1

v2

v4 v3

Gambar 2.11. μ =

1

4

2.4 Pewarnaan Titik Misal G = (VG, EG) adalah suatu graf. Pewarnaan titik pada graf G adalah suatu fungsi dari VG ke himpunan bilangan asli. Suatu pewarnaan titik pada graf G dikatakan k-pewarnaan titik sejati jika titik-titik pada VG dapat dipetakan ke himpunan k bilangan asli pertama dan memenuhi setiap dua titik yang bertetangga memperoleh warna berbeda. Bilangan kromatik χ(G) merupakan bilangan asli terkecil k sehingga terdapat k-pewarnaan titik sejati. Suatu graf yang mempunyai bilangan kromatik k disebut graf k-kromatik. Gambar di bawah menunjukkan suatu graf 3-kromatik, karena titik-titik pada graf tersebut dapat diwarnai dengan 3 warna namun tidak dapat diwarnai dengan 2 warna.

1 2 3 Gambar 2.12. graf 3-kromatik


BAB II Konsep Dasar

2.5 Pewarnaan Titik Graf Fuzzy Dalam pewarnaan titik graf fuzzy, konsep pewarnaan titik yang dilakukan sama dengan konsep pewarnaan titik pada graf biasa. Sebagai contoh, misalkan terdapat suatu sistem lalu lintas sebagai berikut :

A

D

B

C

Gambar 2.13. Sistem tersebut dapat dimodelkan dengan suatu graf kabur G = (V , Eμ ) dengan V = {AC, BC, DA, DB, DC} dan fungsi keanggotaan tingkat intensitas sisi di antara lintasan ini dituliskan sebagai berikut : I = {n, l , m, h, t} .

n = null (satu lintasan dengan lintasan lainnya memiliki keterkaitan yang erat saat tingkat kemacetan sangat tinggi).

l = low (satu lintasan dengan lintasan lainnya memiliki keterkaitan yang erat saat tingkat kemacetan tinggi).

m = medium (satu lintasan dengan lintasan lainnya memiliki keterkaitan yang erat saat tingkat kemacetan sedang).

h = high (satu lintasan dengan lintasan lainnya memiliki keterkaitan yang erat saat tingkat kemacetan rendah).


BAB II Konsep Dasar

t = total (satu lintasan dengan lintasan lainnya tidak saling terkait dalam kondisi tingkat kemacetan sangat rendah) AC BC DA DB DC

AC 0 m n h m

BC m 0 n n l

DA n n 0 n n

DB h n n 0 n

DC m l n n 0

Tabel 2.5 Dari matriks ketetanggaan ini, dapat digambarkan dalam bentuk graf untuk setiap tingkat intensitas sisi sebagai berikut : 1. Matriks ketetanggaan G dengan tingkat intensitas sisi h AC BC DA DB DC

AC 0 0 0 1 0

BC 0 0 0 0 0

DA 0 0 0 0 0

DB 1 0 0 0 0

DC 0 0 0 0 0

Tabel 2.6

Selanjutnya, dari matriks ketetanggaan ini dapat digambarkan dalam bentuk pewarnaan graf sebagai berikut : AC 1

DA

1

1

BC

1 DB

DC

1

Gambar 2.14. μ = h 20 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II Konsep Dasar

2. Matriks ketetanggaan G dengan tingkat intensitas sisi m AC BC DA DB DC

AC 0 1 0 1 1

BC 1 0 0 0 0

DA 0 0 0 0 0

DB 1 0 0 0 0

DC 1 0 0 0 0

Tabel 2.7

Selanjutnya, dari matriks ketetanggaan ini dapat digambarkan dalam bentuk pewarnaan graf sebagai berikut : AC 1

DA

BC

1

DB

DC

1

Gambar 2.15. μ = m

3. Matriks ketetanggaan G dengan tingkat intensitas sisi l AC BC DA DB DC

AC 0 1 0 1 1

BC 1 0 0 0 1

DA 0 0 0 0 0

DB 1 0 0 0 0

DC 1 1 0 0 0

Tabel 2.8

Selanjutnya, dari matriks ketetanggaan ini dapat digambarkan dalam bentuk pewarnaan graf sebagai berikut : 21 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II Konsep Dasar

AC 1

DA

BC

1

3 DB 1

DC 3

Gambar 2.16. μ = l

Lengkapnya, akan diperoleh hasil sebagai berikut :

μ

Eμ

χμ

AC

BC

DA

DB

DC

n

{AC,BC};{AC,DA};{AC,DB};{AC,DC};{BC,DA};

5

1

2

3

4

5

{BC,DB};{BC,DC};{DA,DB};{DA,DC};{DB,DC} l

{AC,BC};{AC,DB};{AC,DC};{BC,DC}

3

1

2

1

2

3

m

{AC,BC};{AC,DB};{AC,DC}

2

1

2

1

2

2

h

{AC,DB}

2

1

1

1

2

1

t

∅

1

1

1

1

1

1

Tabel 2.9

AC

AC 1

DA

1

1

3

2

BC

DA

1

1

1

1

BC

2 3

1

4 5

DC

DB 4

DB

DC

5

Gambar 2.17. μ = n

Gambar 2.18. μ = t 22


BAB II Konsep Dasar

Dari tabel 2.9 diperoleh bilangan kromatik G , yaitu :

χ (G ) = {(1, t ), (2, h)(3, l ), (4, n), (5, n)}

2.6 Algoritma Pewarnaan Titik Salah satu metode pewarnaan titik adalah metode pewarnaan terurut SC (Sequential Coloring). Metode pewarnaan tersebut adalah sebagai berikut:

Beri suatu urutan untuk titik-titik di G, misalkan urutan a0, a1, ..., an-1.

Beri a0 warna terkecil, yaitu f(a0) = 1.

Jika a1,…,ai-1 (i ≥ 1) telah menerima warna, maka untuk ai diberikan warna terkecil yang tidak muncul pada tetangga ai.

Pada tahun 1979 Brelaz menemukan algoritma DSATUR (Degree of Saturation). Algoritma DSATUR merupakan algoritma pewarnaan terurut dengan membangun urutan titik-titik secara dinamis. Derajat saturasi dari suatu titik x yang dinotasikan dengan degs(x) adalah banyaknya warna berbeda yang sudah muncul pada tetangga x. Langkah-langkah konstruksi pewarnaan f untuk titik-titik dari graf G dengan menggunakan algoritma DSATUR adalah sebagai berikut:

Pilih salah satu titik yang memiliki derajat terbesar. Titik tersebut diberi warna terkecil yaitu 1.

Titik yang diwarnai selanjutnya ialah salah satu titik yang memiliki degs(x) terbesar.


BAB II Konsep Dasar

Selanjutnya diberikan beberapa definisi yang akan digunakan pada teorema berikutnya.

Definisi 3.1 Pewarnaan f1, f2, dari G = (V, E) dikatakan ekivalen jika f1 dan f2 mempartisi himpunan titik V berturut-turut menjadi U1, ..., Uk dan W1, ..., Wk dengan |Ui| = |Wi| untuk i = 1, ..., k.

Definisi 3.2 Suatu pewarnaan f dari titik a0,…, an-1 dari graf G disebut ketat terhadap urutan yang diberikan, jika : f(ai) ≤ colors(i-1) + 1 untuk semua i = 0,1,…,n-1 dengan colors(j) untuk j = 0,1,...,n-2 merupakan banyaknya warna yang berbeda pada titik a0,…, aj, dan colors(-1) = 0.

Kemudian untuk mengkonstruksi suatu pewarnaan f untuk graf G yang menggunakan warna sebanyak bilangan kromatik χ(G), Brown memperkenalkan suatu algoritma. Algoritma ini menggunakan metode pewarnaan terurut dan penelusuran kembali (backtracking). Untuk efisiensi algoritma, cabang-cabang yang tidak diperlukan dari pohon pencarian dihindari dengan menggunakan teorema berikut.

Teorema 3.1 (Klotz[5]) Misal f adalah pewarnaan dari graf G, maka terdapat suatu pewarnaan dari graf G yang ketat dan ekivalen dengan f.


BAB II Konsep Dasar

Bukti :

Misal f(a0) = k1 > 1. Jika tidak ada titik yang mendapat warna 1, maka ganti k1 dengan 1. Jika ada, maka tukar warna k1 dengan 1.

Misal f telah ketat untuk semua titik a0,…, ai-1, i ≥ 1 dan misalkan colors(i-1) = l.

Jika f(ai) = k > l+1 dan tidak ada titik yang mempunyai warna l+1, maka ganti warna k dengan l+1. Jika f(ai) = k > l+1 dan ada titik yang mempunyai warna l+1, maka tukar warna k dengan l+1. ⁯

Konsep Algoritma Backtracking oleh Brown Konsep algoritma backtracking yang dikemukakan oleh Brown berdasarkan 2 tahap, yaitu maju dan mundur.

Tahap Maju: Semua titik diwarnai satu per satu berdasarkan warna yang mungkin hingga tidak ada lagi titik yang tidak memiliki warna.

Tahap Mundur: Pilih satu titik yang sudah diwarnai. Kemudian warnai titik tersebut dengan warna lain yang berbeda dengan warna sebelumnya. Selanjutnya, titik-titik lain diwarnai kembali mengikuti langkah seperti pada tahap maju.

Backtrack: Apabila masih mungkin ditemukan pewarnaan pada graf G yang lebih sedikit dari pewarnaan sebelumnya maka akan dilakukan suatu pewarnaan titik kembali. Proses ini dilakukan terus menerus dan berhenti apabila titik awal pewarnaan pada tahap maju tidak bisa diwarnai dengan warna yang lain.


BAB II Konsep Dasar

Algoritma asli dari Brown dikembangkan lagi oleh Brelaz. Titik-titik dari graf disimpan dalam suatu array, misalkan A. Pertama, titik-titik tersebut diurutkan berdasarkan derajat yang tidak naik. Urutan ini lalu berubah secara dinamis. Misal A[0],…,A[i-1] telah mendapat warna dan misalkan banyaknya warna yang berbeda pada titik-titik ini adalah colors(i-1) = li. Himpunan warna bebas dari suatu titik x = A[i], dinotasikan dengan U = freeColors(x), adalah himpunan bagian dari warna {1,2,…, li+1} yang tidak muncul pada tetangga x. Jika suatu batas atas, dinotasikan dengan optColorNumber (χ(G)≤optColorNumber), telah didapat dari suatu pewarnaan f, maka semua warna ≥ optColorNumber dibuang dari U. Titik yang diwarnai selanjutnya adalah seperti pada DSATUR, yaitu titik yang memiliki derajat saturasi terbesar. Titik ini diwarnai dengan warna terkecil di U. Jika U kosong, maka suatu penelusuran kembali (backtrack) dilakukan. Algoritma ini disebut BSC (Backtracking Sequential Coloring) yang dapat mengkonstruksi suatu pewarnaan dari graf G dengan menggunakan warna sebanyak bilangan kromatik χ(G).

Algoritma BSC(Backtracking Sequential Coloring) [input] n

//banyak titik

A[i]

, I = 0,1,…….,n-1

//array pengurutan derajat titik secara descending

[Procedure] for i:=1 to n do

//derajat saturasi setiap titik = 0

F[i]:=0; 26 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II Konsep Dasar

start := 0;

//index awal

optColorNumber := n + 1;

//jumlah warna optimal.

v := A[0];

//titik yang akan diwarnai

colors(-1) := 0;

//colors(j) = banyaknya warna di A[0],...,A[j]

U := [1];

//variabel untuk himpunan warna bebas(terurut)

freeColors[v] := U;

//array untuk himpunan warna bebas dari v

while (start>=0) do

//setiap titik diwarnai pada loop dibawah ini

back:=false; for i:= start to n-1 do if i>start then

//cari titik yang belum diwarnai dan mempunyai derajat saturasi terbesar

v:=GetDSaturOne;

// GetDSaturOne adalah fungsi untuk mencek derajat saturasi titik

U:=GetUOne;

//GetUOne adalah fungsi untuk mencek freecolors titik

if U<>[] then

//proses dijalankan jika U ≠ ∅

C:=MinValue(U);

//warna bebas yang dipilih

F[v]:=C;

//pewarnaan untuk titik v

freeColors[v]:=U-[C]; l:=colors[i-1]; colors[i]:= max(C,l); else

//U = ∅ dilakukan penelusuran kembali, mundur satu posisi

start:=i-1; 27 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II Konsep Dasar

back:=true; break;

//keluar dari loop for

// akhir loop for

if back then if start>=0 then v:=A[start];

//titik awal yang baru

F[v]:=0;

//hapus warna v

U:=freeColors[v]; else

//loop diatas dilalui tanpa berhenti

for i:=1 to n do Fopt[i]:=F[i];

//menyimpan pewarnaan yang optimal pada saat ini

optColorNumber:=colors[n-1];

for i:=0 to n-1 do if F[A[i]]=optColorNumber then

// i = indeks terkecil dimana F[A[i]]=optColorNumber

break; start:=i-1; if start<0 then break;

//keluar dari loop while

for j:=start to n-1 do F[A[j]]:=0;

//hapus warna A[j], dimana j ≥ start 28


BAB II Konsep Dasar

for i:=0 to start do v:=A[i]; U:=freeColors[v]; for j:=optColorNumber to MaxVertex do U:=U-[j];

//semua warna ≥ optColorNumber dihilangkan dari U

freeColors[v]:=U; // disini v= A[start]; U=freecolors(v) // akhir dari loop while

[Output] Fopt[n+1]:=fmax(Fopt);

//Bilangan Kromatik

Result:=Fopt;


BAB II Konsep Dasar

Untuk ilustrasi dari algoritma tersebut, perhatikan contoh dibawah ini : 1. Misalkan graf yang akan diwarnai adalah sebagai berikut 1

3

2

4

5

7 6 8

9 11

10 Gambar 2.19

2. Untuk mewarnai graf pada gambar 2.9 dengan menggunakan algoritma BSC, langkah pertama yang dilakukan adalah menyusun derajat titik pada graf tersebut

secara

descending

dalam

array

A.

Sehingga,

didapatkan

A:=[v6 , v2 , v10 , v11 , v1 , v3 , v4 , v5 , v7 , v8 , v9 ]. 3. Selanjutnya, pilih salah satu titik yang memiliki derajat terbesar. Jika terdapat lebih dari satu, maka pilih titik dengan label terkecil. Cek freecolors U yang mungkin diberikan pada titik tersebut, kemudian warnai titik tersebut dengan warna terkecil yang terdapat pada freecolors v. Kemudian hapus warna yang digunakan untuk mewarnai titik tersebut dari freecolors v. 4. Pilih titik dengan derajat saturasi terbesar. Jika terdapat lebih dari satu, maka pilih titik dengan derajat titik terbesar. Jika terdapat lebih dari satu, maka pilih titik dengan label terkecil. Cek freecolors U yang mungkin diberikan pada titik tersebut, kemudian warnai titik tersebut dengan warna terkecil yang terdapat


BAB II Konsep Dasar

pada freecolors v dan tidak dimiliki oleh tetangga dari titik tersebut. Kemudian hapus warna yang digunakan untuk mewarnai titik tersebut dari freecolors v. 5. Langkah 4 dilakukan terus hingga semua titik pada graf diwarnai. Sebagai gambaran dari langkah 3 dan 4, perhatikan gambar 2.20.

Gambar 2.20 6. Dari langkah 5 diperoleh hasil sebagai berikut freeColors(v6) =[] freeColors(v3) =[] freeColors(v2) =[3] freeColors(v10) = [3] freeColors(v5) = [] freeColors(v1) = [4] freeColors(v7) = [4] freeColors(v11) = [4] freeColors(v4) = [4] freeColors(v9) = [] freeColors(v8) = [3,4,5]

1

3

2

4

5

7 6 8

10

9 11

Gambar 2.21 7. Hasil yang diperoleh ini kemudian disimpan pada Fopt (Fopt = 4).


BAB II Konsep Dasar

8. Titik yang memiliki warna 4 dihapus (v9 ) . Kemudian hapus warna yang digunakan titik v8 . 9. Hapus semua warna ≥ 4 dari freecolors v dan U. 10. Kemudian warnai kembali v8 dengan warna yang tersedia pada freecolors v8. Selanjutnya v9 diwarnai kembali dengan terlebih dahulu melakukan cek ulang terhadap freecolors v9. Jika v9 tidak memiliki freecolors yang tersedia, maka hapus warna titik v9 dan warna titik sebelumnya berdasarkan urutan mundur dari A (dalam contoh ini kita hapus warna v8). 11. Kemudian warnai kembali v8 dengan warna yang tersedia pada freecolors v8. Jika v8 tidak memiliki freecolors yang tersedia, maka hapus warna titik v8 dan v7. 12. Semua warna titik akan dihapus berdasar urutan mundur dari A jika titik tersebut tidak memiliki freecolors v yang tersedia (pada contoh ini, proses berhenti hingga v10). 13. Kemudian warnai kembali v10 dengan warna yang tersedia pada freecolors v10. Setelah v10 diwarnai, lakukan kembali langkah 4 hingga semua titik diwarnai. 14. Sebagai gambaran langkah 8 hingga 13, perhatikan gambar 2.22


BAB II Konsep Dasar

Gambar 2.22

15. Dari langkah 14 diperoleh hasil sebagai berikut freeColors(v6) =[] freeColors(v3) =[] freeColors(v2) =[3] freeColors(v10) = [] freeColors(v5) = [] freeColors(v1) = [] freeColors(v7) = [] freeColors(v11) = [] freeColors(v4) = [] freeColors(v9) = [] freeColors(v8) = []

1

3

2

4

5

7 6 8

10

9 11

Gambar 2.23 16. Hasil yang diperoleh disimpan pada Fopt (Fopt = 3). 17. Selanjutnya, lakukan cara yang sama pada langkah 8 hingga 13. Algoritma BSC berhenti apabila semua titik memiliki freecolors = []. 18. Hasil yang diperoleh adalah hasil dari Fopt terakhir (pada contoh ini hasil yang diperoleh adalah 3). 33 Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas

BAB II. Konsep Dasar

Recommend Documents