Pewarnaan Graf (Graph Coloring)

Pewarnaan graf adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik pada batas tertentu.
Ada tiga macam pewarnaan graf.
Pertama, pewarnaan titik (vertex coloring) yaitu memeberikan warna berbeda pada setiap titik yang bertetangga sehingga tidak ada dua titik yang bertengga dengan warna yang sama.

Kedua, pewarnna sisi (edge coloring), yaitu memberikan warna berbeda pada sisi yang bertetangga sehingga tidak ada dua sisi yang bertetangga memepunya warna yang sama.

Ketiga, pewarnaan bidang, yaitu memberikan warna pada bidang sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama.

DEFINISI 1

Pewarnaan simpul (Vertex coloring), singkatnya pewarnaan (coloring),suatu Graf adalah pemberian warna terhadap simpul sedemikian sehingga dua simpul yang berdampingan mempunyai warna yang berlainan.

DEFiNISI 2

Kita katakan G berwarna n,bila terdapat pewarnaan dengan menggunakan n warna.

DEFINISI 3

Jumlah minimum warna yang dibutuhkan disebut bilangan khromatis dari G,ditulis K(G).

Dalam memecahkan problem pewarnaan ,kita selalu berusaha mewarnai simpul menggunakan banyak warna minimal.

ALGORITMA WELCH-POWELL

Kita dapat menggunakan algoritma Welch-Powell untuk mewarnai suatu Graf, an banyak warna minimal, sebagai berikut;

Mula-mula kita urutkan semua simpul berdasarkan derajatnya, dari derajat besar ke derajat kecil. Ambil warna pertama, warnai simpul pertama (dalam urutan), kemudian simpul berikutnya yang tidak berdampingan, terus menerus, berdasarkan urutan. Kemudian kita lanjutkan dengan warna kedua dan seterusnya, sampai semua simpul telah diberi warna.

Contoh :

Kita akan mewarnai simpul Graf menggunakan algoritma Welch-powell.

Urutan simpul berdasarkan deraiatnya:

E. G, C, A, B, D, F, H

Ambil warna pertama. misalnya hijau. Beri wama hijau simpul E, kemudian warnai simpul A, karena A tidak berdampingan dengan simpul E.

Urutan simpul yang belum diberi warna:

G, C, B, D, F, H

Ambil warna kedua, misalnya merah, beri warna merah simpul G,B dan F.

Urutan simpul yang belum diberi warna

C, D. H

Warna ketiga, misalnya putih, beri warna putih simpul C, D dan H.

Pewarnaan telah selesai, Graf merupakan. Graf berwarna 3.

Dapat dicatat bahwa Graf bukan Graf berwarna 2, karena misalnya simpul A, B dan D harus mempunyai warna yang berbeda. Jadi K(G) = 3.

Berikut ini teorema mengenai Pewarnaan Graf

Teorema 1

Pernyataan berikut adalah ekivalen :

(I) G berwarna 2

(2) G adalah bipartisi

(3) Setiap Sirkuit dalam G mempunyai panjang genap

Dengan mudah dilihat bahwa Graf lengkap dengan n simpul Kn membutuhkan n warna dalam setiap pewarnaan, karena masing-masing simpul berdampingan dengan simpul yang lain.

Berikut ini teorema bagi Graf Planar

Teorema 1

Suatu Graf Planar G adalah berwarna 5

PEWARNAAN MAP

Perhatikan suatu Map M. Dua Region dari M dikatakan berdampingan jika mereka mempunyai suatu ruas persekutuan .Sebagai contoh pada Gambar. Region R2 dan R3 adalah berdampingan, sedangkan Region R3 dan R5 tidak berdampingan.

DEFINISI

Yang dimaksud dengan pewarnaan Map adalah pemberian warna Region sedimikian sehingga Region yang berdampingan mempunyai warna yang berbeda.

Suatu Map M berwarna n jika terdapat suatu pewarnaan dari M dengan menggunakan n warna. Graf pada Gambar adalah berwarna 3, karena Region dapat diberi warna sebagai berikut

R1 merah, R2 putih, R3 merah, R4 putih, R5 merah, R6 biru

Di sini 3 adalah banyak warna minimal

Andaikata kita menggambar sebuah simpul baru pada masing-masing Region suatu Map M, kemudian membuat sebuah ruas menghubungkan simpul pada 2 Region yang berdampingan memotong setiap ruas batas/persekutuan kedua Re¬gion, dengan tanpa adanya ruas baru yang berpotongan, maka akan terbentuk suatu Map M* yang disebut Dual dari Map M.

Perhatikan dual dari Map Gambar 1.35:

Dapat dilihat bahwa masing-masing Region dar M* mengandung tepat satu simpul dari M demikian pula setiap ruas dari M memotong tepat satu ruas dari M* karena itu dapat dikatakan juga bahwa M adalah dual dari M*. Relasi Dual adalah relasi yang simetris.

Dapat diamati bahwa pewarnaan region dari M sama artinya dengan pewarnaan simpul dari M*. Dengan perkataan lain:

Suatu map M berwarna n jika dan hanya jika dualnya M* berwarna (simpul) n.

Jadi diperoleh teorema

Teorema 1:

Suatu map M adalah berwarna 5

Namun tidak ada map yang dijumpai membutuhkan 5 warna pada setiap pewarnaan.

Teorema 2:

Setiap map adalah berwarna (region) 4, dan setiap Graf planar adalah berwarna (simpul)4.

Teorema ini dibuktikan oleh Apple dan Haken pada tahun 1976 dengan menggunakan computer untuk menganalisis sampai 2000 Graf yang mengandung jutaan kasus.

Materi ALgoritma Semut

Saat ini sedang banyak dilakukan penelitian terhadap perilaku alam yang mungkin bisa diterapkan untuk mencari solusi pada permasalahan2 optimasi. Kita sudah sering mendengar JST dan Algoritma Genetika yang meniru system kerja tubuh manusia. Perilaku hewan juga ditiru, burung, lebah, angsa… dan algoritma semut hanya salah satunya.

Perilaku Semut Yang Mana?

Pada saat semut menemukan sumber makanan, maka semut perlu menentukan jalur yang terpendek antara sumber makanan dan sarang semut. Disinilah peran teman2 atau ‘koloni’ semut. Pekerjaan menelusuri jalur didistribusikan kepada beberapa agen semut. Pada awalnya semut2 tersebut akan melalui semua jalur yang memungkinkan secara acak. Kemudian jalur yang terpendek pada saat itu dibubuhi jejak, yang disebut dengan pheromone. Pada dunia nyata, pheromone merupakan alat komunikasi berupa hormon yang dikeluarkan oleh semut sebagai penunjuk jalan bagi semut yang lain.



Ilustrasi koloni semut menemukan jalur terpendek untuk mencari makanan

Dengan adanya informasi pheromone, maka semut2 selanjutnya tidak akan berjalan secara acak lagi, namun akan lebih tertarik mengikuti jalur yang ada pheromonenya. Semakin banyak semut melalui suatu jalur, semakin banyak pula jumlah pheromone yang tertinggal di jalur tersebut. Sehingga, lama kelamaan semua semut melalui satu jalur yang seragam, yaitu jalur yang terpendek. Perilaku semut yang seperti ini merupakan salah satu bentuk autocatalytic-suatu perulangan dengan feedback yang positif.

Ilmuwan Pencetus Algoritma Semut?

Dorigo Marco pada tahun 1992 meneliti algoritma semut sebagai thesis PhD nya. Setelah itu banyak dilakukan penelitian mengaplikasikan Algoritma Semut pada berbagai jenis permasalahan optimasi, dan muncul banyak variasi Algoritma Semut.

Macam-Macam Algoritma Semut?

- Versi pertama disebut dengan Ant System (AS), yang diaplikasikan pada TSP
- Elitist Ant System (EAS)
- Ant Colony System (ACS)
- Approximate Nondeterministic Tree Search (ANTS)
- Hyper-Cube Framework for ACO
- Rank-Based ANt System (ASrank)
- Min-Max Ant System (MMAS)
- Dsb

Masing-masing punya karakteristik sendiri2 yang membedakan. Tiap varian cocok untuk jenis permasalahan tertentu. walaupun ada banyak varaisi, basisnya tetaplah AS.

Sudah Diaplikasikan pada Berbagai Macam Kasus

- Travelling Salesman Problem (TSP) dan Asymmetric TSP (ATSP)
- The Single Machine Total Weighted Tardiness Scheduling Problem (SMTWTP)
- The Generalized Assignment Problem (GAP)
- Quadratic Assignment Problem (QAP)
- Job-Shop Scheduling Problem (JSP)
- The Set Covering Problem (SCP)
- Network Routing Applications

ALGORITMA DIJKSTRA

Pada tahun 1959 sebuah tulisan sebanyak tiga halaman yang berjudul A Note on Two Problem in Connexion with Graphs diterbitkan oleh jurnal Numerische Mathematic. Pada tulisan ini, Edsger W. Dijkstra, seorang ilmuwan komputer berusia 29 tahun mengusulkan algoritma-algoritma untuk solusi dari dua masalah teoritis graf dasar. The Minimum Weight adalah algoritma dijkstra untuk lintasan terpendek adalah salah satu algoritma yang paling ternama dalam ilmu komputer dan sebuah algoritma paling populer dalam operasi pencarian (OR).

2.1 Definisi Algoritma Dijkstra

Pada dasarnya, algoritma ini adalah salah satu bentuk algoritma greedy. Algoritma ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi negatif dan menghasilkan sebuah pohon lintasan terpendek. Algoritma ini sering digunakan pada routing. Algoritma dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan strategi greedy sebagai berikut :

Untuk setiap simpul pada sumber (source) dalam graf, algoritma ini akan mencari jalur dengan cost minnimum antara simpul tersebut dengan simpul lainnya.

2.2 Skema Umum Algoritma Dijkstra

Berikut adalah skema algoritma dijksrta dalam mencari shortest path :

1. Buat 3 buah list yaitu list jarak (1), list simpul-simpul sebelumnya (2), dan list simpul yang sudah dikunjungi (3) serta sebuah variabel yang menampung simpul saat ini (current vertex).

2. Isi semua nilai dalam list jarak dengan tak hingga, kecuali simpul awal diisi 0

3. Isi semua nilai dalam list 2 dengan false

4. Isi semua nilai dalam list 3 dengan null.

5. Current vertex diisi dengan simpul awal (start).

6. Tandai current vertex sebagai simpul yang sudah dikunjungi.

7. Update list 1 dan 2 berdasarkan simpul-simpul yang dapat langsung dicapai dari current vertex.

8. Update current vertex dengan simpul yang paling dekat dengan simpul awal.

9. Ulangi langkah 6 sampai semua simpul dikunjungi.

MAXIMUM FLOW PROBLEM

3.1 Network Flow

Dalam teori graf, sebuah flow network adalah sebuah graf berarah yang tiap sisinya mempunyai bobot dan terdapat arus yang mengalir diantara 2 simpul yang mengapit sisi tersebut. Jumlah arus yang mengalir harus lebih kecil atau sama dengan bobot sisinya.

Pada aplikasinya, sebuah sebuah graf berarah sering disebut network. Setiap arus (fkow) yang ada pada network harus memenuhi sebuah batasan, yaitu arus yang masuk ke simpul harus sama dengan arus yang keluar dari simpul itu, kecuali pada source yang arus keluarnya lebih besar dan pada sink yang arus mauknya lebih besar.