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.

Materi Matrik

Matrik adalah kumpulan bilangan berbentuk persegi panjang yang disusun menurut baris dan kolom. Bilangan-bilangan yang terdapat di suatu matriks disebut dengan elemen atau anggota matriks. Dengan representasi matriks, perhitungan dapat dilakukan dengan lebih terstruktur. Pemanfaatannya misalnya dalam menjelaskan persamaan linier, transformasi koordinat, dan lainnya. Matriks seperti halnya variabel biasa dapat dikalkulasi, seperti dikalikan, dijumlah, dikurangkan dan didekomposisikan.

ORDO

Ordo suatu matriks adalah bilangan yang menunjukkan banyaknya baris (m) dan banyaknya kolom (n).  Matriks di atas berordo 2x3.

MATRIKS TRANSPOS

Matriks transpose adalah matriks yang mengalami pertukaran elemen dari baris menjadi kolom dan sebaliknya.

CONTOH

maka matriks transposenya (A^t) adalah

 

KESAMAAN MATRIKS

Dua matriks A dan B dikatakan sama (ditulis A = B), jika a. Ordonya sama 
b. Elemen-elemen yang seletak sama

Contoh:



Tentukan nilai 2x-y+5z!

Jawab:

 maka 

 maka 

 maka 

Penjumlahan dan pengurangan matriks

Penjumlahan dan pengurangan matriks hanya dapat dilakukan apabila kedua matriks memiliki ukuran atau ordo yang sama. Elemen-elemen yang dijumlahkan atau dikurangi adalah elemen yang posisi atau letaknya sama.

atau dalam representasi dekoratfinya

 

 

Perkalian Skalar

Matriks dapat dikalikan dengan sebuah skalar.

Contoh perhitungan :

Perkalian matriks

Matriks dapat dikalikan, dengan cara tiap baris dikalikan dengan tiap kolom, lalu dijumlahkan pada baris yang sama. Namun dengan syarat, dua matriks A dan B terdefinisi untuk dikalikan, jikabanyaknya kolom A = banyaknya baris B, dengan hasil suatu matriks C yang berukuran (memiliki ordo) baris A x kolom B.Jika syarat tersebut tidak dipenuhi (jumlah kolom matriks A tidak sama dengan jumlah bari matriks B) maka kedua matriks tersebut tidak dapat dikalikan.

A _{m x n} x B _{n x p} = C _{m x p}

(jumlah kolom matriks A sama dengan jumlah baris kolom B yaitu n)

Contoh perhitungan :

diatas adalah matriks 2x3 dikali matriks 3x2 yang hasilnya adalah matriks 2x2. 


Ket :
perkalian matriks bersifat tidak komutatif (AxB tidak sama dengan BxA) tetapi bersifatasosiatif (AxB)xC = Ax(BxC).

MATRIKS SATUAN

Matriks satuan adalah suatu matriks bujur sangkar, yang semua elemen diagonal utamanya adalah 1, sedangkan elemen lainya adalah 0. Notasi : I (Identitas)



SIFAT AI = IA = A

DETERMINAN MATRIKSMATRIKS ORDO 2X2

Misalkan:


maka Determinan A (ditulis  ) adalah:




MATRIKS ORDO 3X3
CARA SARRUS

Misalkan:

Jika

 maka tentukan !




Penghitungan matriks dilakukan dengan cara menambahkan elemen dari kiri atas ke kanan bawah (mulai dari a → e → i, b → f → g, dan c → d → h) lalu dikurangi dengan elemen dari kanan atas ke kiri bawah (mulai dari c → e → g, a → f → h, dan b → d → i) sehingga menjadi:

Contoh:

 maka tentukan !





CARA EKSPANSI BARIS KOLOM
Misalkan:


maka tentukan  dengan ekspansi baris pertama!

 

MATRIKS SINGULAR Matriks singular adalah matriks yang nilai determinannya 0.

Contoh:



Jika A matriks singular, tentukan nilai x!

Jawab:

 vs 

MATRIKS INVERSMisalkan: maka inversnya adalah:

• Bilangan (ad-bc) disebut determinan dari matriks A
• Matriks A mempunyai invers jika Determinan A ¹ 0 dan disebut matriks non singular.

Sifat-Sifat
1. (A^t)^t = A
2. (A + B)^t = A^t + B^t
3. (A . B)^t = B^t . A^t
4. (A . B)^-1 = B^-1 . A^-15. A . A^-1 = A^-1 . A = I
Persamaan matriks
Tentukan X matriks dari persamaan:

• Jika diketahui matriks A.X=B

• Jika diketahui matriks X.A=B