![M6 - TT - Terapan Teori Graf - Oke [PDF]](https://pdfs.asia/img/200x200/m6-tt-terapan-teori-graf-oke.jpg)
14 0 4 MB
GRAF BERARAH DAN IMPLEMENTASINYA Dr. Asep Juarna Dr. Ricky Agus Tjiptanata, S.T., S.Si., M.M.
LINGKUP MATERI Masalah Aliran Maksimal
6
1
Graf Berarah, Derajat Simpul pada Graf Berarah
2 Masalah Jalur Terpendek
5
Automata Hingga
4
3
Keterhubungan Graf Berarah, Matriks dan Graf Berarah
Mesin Stata Hingga
• Definsi: Graf (graph) adalah diagram objek-objek di mana beberapa pasang objek saling berkoneksi. • Objek digambarkan dengan simpul (vertex, node) sementara koneksi digambarkan dengan busur (edge, arc). • Secara formal graf dinotasikan sebagai G(V, E), di mana V adalah himpunan simpul-simpul dan E adalah himpunan busur-busur. Himpunan V tidak boleh hampa, E boleh. • G’(V’, E’) adalah subgraf dari graf G(V, E) di mana V’ V dan E’ E. Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Graf G(V, E), di mana V = {1, 2, 3, 4} dan E = {e1, e2, e3, e4} = {{1,2}, {1,3}, {1,4}, (3,4}}. • Karena ada ruas e1 = {1,2}, simpul 1 dan 2 dikatakan bertetangga (adjacent). • Ruas e1 = {1,2} dikatakan bersisian (incident) dengan simpul 1 dan 2. • • • •
Graf Lengkap: setiap simpul terkoneksi ke setiap simpul lainnya. K3: Graf lengkap 3 simpul K4: Graf lengkap 4 simpul Kedua graf (K3 dan K4) dapat dilihat sebagai sebuah graf dengan 2 subgraf.
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Graf tidak berarah (undirected graph): Setiap busur tidak memiliki arah.
G(V,E)
• Graf G(V, E), di mana V = {u, v, w, k} dan E = { {u,w}, {u,v}} adalah graf tidak berarah. • Graf G(V,E) mempunyai 2 subgraf
• Graf berarah (directed graph): Setiap busur memiliki arah. Graf H(V, E), di mana V = {u, v, w} dan E = { (u,v), (u,w), (v,w)} adalah graf berarah. H(V,E)
Perhatikan perbedaan notasi busur pada graf tidak berarah {x,y} dengan graf berarah (x,y). Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Graf tidak berarah, derajat (degree) simpul : Cacahan busur yang bersisian dengan simpul tersebut. Contoh: deg(u) = 2, deg(v) = deg(w) = 1, deg(k) = 0. Simpul berderajat 0 dikatakan terasing (isolated).
• Graf berarah, pada ruas (u,v): u = simpul awal (initial vertex), v = simpul akhir (terminal vertex)ontoh: • •
in-deg(x): Cacahan busur dengan simpul akhir x out-deg(x): Cacahan busur dengan simpul awal x
• in-deg(u) = 0, out-deg(u) = 2 • in-deg(v) = 1, out-deg(v) = 1 • in-deg(w) = 2, out-deg(w) = 0 Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Graf tidak berarah: • Perjalanan (walk): barisan ruas yang menghubungkan barisan simpul. • Jejak (trail): perjalanan di mana setiap ruasnya berbeda. • Lintasan (path): jejak di mana setiap simpulnya (dengan demikian juga setiap ruasnya( berbeda • Perjalanan {{A, E}, {E,F}, {F,E}, {E,B}} bukan sebuah jejak karena ada ruas yang sama yaitu {E,F} = {F,E}. • Jejak {e1, e2, e3, e4} bukan sebuah lintasan karena ada simpul yang berulang yaitu B. Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Graf berarah: • Perjalanan berarah (directed walk): barisan ruas dengan arah sama yang menghubungkan sebarisan simpul tertentu. • Jejak berarah (directed trail): perjalanan berarah di mana setiap ruasnya berbeda. • Lintasan berarah (directed path): jejak berarah di mana setiap simpulnya (dengan demikian juga setiap ruasnya( berbeda • Perjalanan {(A, B), (B,C), (C,D), (D,F), (F,B), (B,C)} bukan sebuah jejak karena ada ruas yang sama yaitu (B,C). • Jejak {A, B, C, D, F, B} bukan sebuah lintasan karena ada simpul yang berulang yaitu B.
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Graf tidak berarah: • Sebuah graf tidak berarah dikatakan terhubung (connected) jika terdapat sebuah lintasan antara setiap pasang simpulnya.
Graf tidak terhubung • Simpul putus (cut vertex) : Jika dikeluarkan dari graf terhubung akan menyebabkan graf tidak terhubung atau jumlah subgrafnya bertambah. • Ruas putus (cut edge) : Jika dikeluarkan dari graf Graf terhubung. X adalah simpul putus. terhubung akan menyebabkan graf tidak Tidak ada ruas putus. terhubung atau jumlah subgrafnya bertambah. Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Graf berarah: 1. Sebuah graf berarah dikatakan terhubung kuat (strongly connected) jika terdapat sebuah lintasan berarah antara setiap pasang simpulnya. 2. Sebuah graf berarah dikatakan terhubung lemah (weakly connected) jika terdapat sebuah lintasan antara setiap pasang simpulnya hanya jika graf tersebut dipandang sebagai graf tidak berarah.
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Matriks bersisian (incident matrix) • Matriks bertetangga (adjacency matrix) • Senarai bertetangga (adjacency list) • Struktur data matriks bersisian dipilih jika informasi tentang ruas-ruas graf lebih diperhatikan. • Struktur data matriks/sebarai bertetangga dipilih jika informasi tentang simpul-simpul graf lebih diperhatikan.
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Pada graf tidak berarah G(V, E):
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Pada graf berarah G(V, E):
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Pada graf berarah G(V, E), ada data bobot ruas (weight of edges) :
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Tata bahasa dispesifikasi dengan 4 tuple: VT (himpunan simbol terminal = alfabet), VN (himpunan simbol non terminal), S (simbol awal), Q (himpunan produksi). • Kalimat adalah string simbol-simbol alfabet. Bahasa adalah kumpulan kalimat. • Produksi A → aB artinya dalam proses pembentukan kalimat, simbol A bisa diganti dengan string aB; proses berlanjut hingga diperoleh kalimat. • Contoh, Grammar G1: VT = {a, b, c, d}, VN = {A, B, C, D}, S = A, Q = {[1]A → aB, [2]B → bA, [3]B → bC, [4]C → cC, [5]C → cD, [6]C → d, [7]D → dD, [8]D → d} - Kalimat terpendek: A aB[1] abC[3] abd[6] - Kalimat umum: A aB[1] abA[2] abaB[1] ababA[2] ababaB[1] abababA[2] ... a(ba)nB[1] a(ba)nbC[3] = (ab)nC[3] (ab)ncC[4] (ab)nccC[4] ... (ab)ncm-1C[4] (ab)ncmD[5] (ab)ncmdD[7] (ab)ncmddD[7] ... (ab)ncmdp-1D[7] (ab)ncmdp[8] Bahasa yang dihasilkan grammar di atas: L = {(ab)ncmdp|n,p 1, m 0} Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Definisi: Automata hingga (finite automata), atau AH, adalah mesin abstrak yang dibangun berdasarkan tata bahasa (grammar) tertentu; fungsi utama AH adalah memeriksa kebenaran kalimat berdasarkan tata bahasa tersebut. • Automata hingga dispesifikasi dengan 5 tuple: K (himpunan stata (state)), VT (alfabet), M (fungsi transisi), S (stata awal), Z (stata penerima). • Automata hingga setiap saat berada pada stata tertentu dan bertransisi ke stata lain karena membaca simbol alfabet; dinamika (mekanisme transisi) AH ditetapkan oleh fungsi transisi. • Dua stata penting: stata awal S dan stata-stata penerima elemen Z. • Pemeriksaan kalimat dimulai pada saat AH berada di stata awal. • Kalimat dinyatakan benar jika setelah membaca kalimat tersebut AH berada pada salah satu stata penerima. Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Automata hingga bisa dinyatakan dengan tabel transisi atau graf berarah; keduanya menggambarkan dinamika (mekanisme transisi) AH tersebut. • Graf AH: simpul = stata, ruas = transisi stata, bobot = simbol dibaca, simpul ganda = stata penerima, simpul dengan panah = stata awal. • Berikut adalah tabel fungsi transisi dan graf berarah sebuat automata hingga AH1: A B C
a B
b [A,C]
c C
d D
D
D
AHN, non deterministic • AH ini bertransisi dari stata A menjadi stata B jika membaca simbol a, juga bertransisi dari stata B ke stata A atau ke stata C jika membaca simbol b. • Contoh kalimat-kalimat yang diterima AHN ini adalah: abd, abccd, ababcd, dan contoh kalimat yang ditolak: abc, abacd.
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Automata hingga adalah hasil konversi dari tata bahasa, khususnya tata bahasa beratutan atau grammar regular (regular grammar), atau GR. • Jika tata bahasa dispesifikasi dengan 4 tuple (VT, VN, S, Q) maka automata hingga dispesifikasi dengan 5 tuple: K (himpunan stata), VT’ (alfabet), M (fungsi transisi), S’ (stata awal), Z (stata penerima). • Ada konversi AHN (N: non deterministik) menjadi AHD (D: deterministik) lalu menjadi GR dan kembali menjadi AHN. • Jika Q adalah karakteristik dinamika tata bahasa maka M adalah karakteristik dinamika AH. Konversi AHN → AHD → GR → AHN intinya adalah konversi M(AHD) menjadi Q(GR) dan Q(GR) menjadi M(AHN). • AHN1 pada slide sebelumnya adalah hasil konversi dari GR1, juga pada slide sebelumnya. Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Definisi: Mesin stata hingga (finite state machine), atau MSH, atau automata hingga beroutput, adalah varian dari automata hingga. • MSH dispesifikasi dengan 5 tuple: K (himpunan stata (state)), VT (alfabet input), f (fungsi transisi), g (fungsi output), S (stata awal), Z (alfabet output). • Berikut adalah contoh MSH, dinyatakan dengan tabel dan graf berarah dengan K = {A, B, C}, VT = {a, b}, Z = {x, y, z}, S = A, f & g bisa dibaca di tabel atau graf. • Jika input MSH ini adalah “aabaa” maka outputnya adalah “xxyxz’.
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
• Contoh lain: MSH Penjumlah Biner (MSH-PB) dengan K = {N, C, H} = {not carry, carry, halt}, VT = {00, 01, 10, 11, b}, Z = {0, 1}, S = N, f & g lihat tabel atau graf. • Jika input MSH ini adalah “aabaa” maka outputnya adalah “xxyxz’. 1101011 (26+25+0+23+0+21+20) = 107 0111011 + (0+25+24+23+0+21+20) = 59 10100110 (27+0+25+0+0+22+21+20) = 166
b
Stata, string input, string output: N- C - C - N - C - C - C - C 11-11-00-11-01-11-10-b ← string input 0- 1-1-0-0-1-0-1 C - C - N- C- C- C- C- H dibalik String output: 10100110
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
Dr. Asep Juarna, Teknik Informatika Universitas Gunadarma
GRAF BERARAH DAN IMPLEMENTASINYA Dr. Asep Juarna Dr. Ricky Agus Tjiptanata, S.T., S.Si., M.M.
LINGKUP MATERI Masalah Aliran Maksimal
6
1
Graf Berarah, Derajat Simpul pada Graf Berarah
2 Masalah Jalur Terpendek
5
Automata Hingga
4
3
Keterhubungan Graf Berarah, Matriks dan Graf Berarah
Mesin Stata Hingga
Masalah Jalur Terpendek (Shortest Path)
Masalah Jalur Terpendek merupakan masalah mendasar dalam graf yakni menemukan jalur terpendek dari sebuah simpul (A) ke simpul lainnya(B).
Berbagai Masalah Jalur Terpendek (Shortest Path) Jalur Terpendek Dari Satu Tempat Ke Tempat Lain IP routing untuk menentukan Open Shortest Path First (OSPF) Jejaring Sosial – Suggestion List Of Friends
Ekstrasi fitur tekstur pada citra medis (Ghidoni et al., 2014) Menentukan Relay Hierarchy pada Microgrid (Ustun, Ozansoy, and Zayegh, 2011)
Gambar 1. Contoh Microgrid (Ustun, Ozansoy, and Zayegh, 2011)
Terdapat beberapa algoritma sederhana (dan efisien) yang dapat digunakan untuk menyelesaikan masalah jalur terpendek. Ada 3 buah Algoritma terbaik yang biasa dipakai: Algoritma Dijkstra, Algoritma Bellman-Ford, dan Algoritma Floyd.
Perhatikan Perbedaan diantara ketiga Algoritma tersebut
Algoritma Dijkstra Algoritma Dijkstra – adalah sebuah solusi untuk masalah jalur terpendek (dari sebuah sumber/source) dalam Teori Graf. Algoritma ini dapat digunakan untuk graf berarah maupun tidak. Semua ruas dari graf harus berbobot tidak negatif. Input: Graf berbobot D(V,A) atau G(V,E) dimana sebagai sumbernya adalah simpul v ∈ V, dengan semua ruasnya berbobot tidak negatif Output: Panjang jalur terpendek dari sumber (simpul v ∈ V) ke semua simpul lainnya
Pendekatannya Algoritma akan menghitung jarak dari titik awal v ke u, untuk setiap simpul u, yaitu bobot jalur terpendek antara v dan u. Algoritma mencatat himpunan simpul yang jaraknya telah dihitung. Setiap simpul memiliki label D yang terkait dengannya. Untuk setiap simpul u, D[u] menyimpan perkiraan jarak antara v dan u. Algoritma akan memperbaharui nilai D[u] ketika menemukan jalur yang lebih pendek dari v ke u. Ketika sebuah simpul u ditambahkan ke ‘data Permanen’, labelnya D[u] sama dengan jarak aktual (akhir) antara simpul awal v dan simpul u 33
Algoritma DIJKSTRA
Telah dipelajari pada materi terdahulu
pseudocode Dijkstra Dijkstra(v1, v2): for each vertex v: // Initialization v's distance := infinity. v's previous := none. v1's distance := 0. List := {all vertices}.
while List is not empty: v := remove List vertex with minimum distance. mark v as known. for each unknown neighbor n of v: dist := v's distance + edge (v, n)'s weight. if dist is smaller than n's distance: n's distance := dist. n's previous := v. reconstruct path from v2 back to v1, following previous pointers. 35
Contoh Kasus: Inisialisasi awal 0
distance(source) = 0
∞ 2
A 1
4
∞
2
C 5
F ∞ Simpul F disini berupa Muara / Sink
3
∞ 1
source) = ∞
B 10 2
D 8
distance (vertex lainnya kecuali
4
E 6
G ∞
∞
Gunakan Algoritma Dijkstra untuk menentukan jalur terpendek antara simpul A dan F pada Graf di atas
36
Contoh Kasus: Inisialisasi awal dilengkapi Matriks 0
distance(source) = 0
* * 4 * * * * *
2 * * * * * * 2
* * * 2 * * * *
1 3 * * * * * 1
* 10 * 2 * * * *
* * 5 8 * * 1 *
∞ 2
A 1
4
∞
Data Graf dalam bentuk Matriks
2
C 5
F ∞
3
∞ 1
source) = ∞
B 10 2
D 8
distance (vertex lainnya kecuali
4
E
∞
6
G ∞
Ambil sebuah simpul dari List dengan jarak paling kecil dari sumber 37
Contoh Kasus: Inisialisasi awal dilengkapi Data iterasi 0
distance(source) = 0
∞ 2
A 1
4
Data Jarak dan Status untuk Iterasi ke-i
A B C D E F G 0 0 ∞ ∞ ∞ ∞ ∞ ∞ T A B C D E F G
∞
2
C 5
F ∞
3
∞ 1
source) = ∞
B 10 2
D 8
distance (vertex lainnya kecuali
4
E
∞
6
G ∞
Ambil sebuah simpul dari List dengan jarak paling kecil dari sumber (A) 38
Contoh Kasus: Mengupdate jarak tetangga terdekat 0
2 2
A 1
4
Data Jarak dan Status untuk Iterasi ke-i
0 T 1 T
A 0 A 0 -
B ∞ B 2 B
C ∞ C ∞ C
D ∞ D 1 D
E ∞ E ∞ E
∞
F ∞ F ∞ F
G ∞ G ∞ G
2
C 5
∞
3
10 2
D 8
F
B
1 1
4
E
∞
6
G
distance(B) = 2
∞
distance(D) = 1
39
Contoh Kasus: Menghapus dari daftar simpul yang memiliki jarak terkecil (D) 0
2 2
A 1
4
Data Jarak dan Status untuk Iterasi ke-i
1 T 2 T
A 0 0 -
B 2 B 2 B
C ∞ C ∞ C
D 1 D 1 -
E ∞ E ∞ E
∞
F ∞ F ∞ F
G ∞ G ∞ G
2
C 5
∞
3
10 2
D 8
F
B
1 1
4
E
∞
6
G ∞
40
Contoh Kasus: Mengupdate jarak tetangga terdekat 0
2 2
A 1
4
Data Jarak dan Status untuk Iterasi ke-i
1 T 2 T
A 0 0 -
B 2 B 2 B
C ∞ C 3 C
D 1 D 1 -
E ∞ E 3 E
3
F ∞ F 9 F
G ∞ G 5 G
2
C 5
9
3
10 2
D 8
F
B
1 1
4
E
3
6
G 5
distance(C) = 1 + 2 = 3 distance(E) = 1 + 2 = 3 distance(F) = 1 + 8 = 9 distance(G) = 1 + 4 = 5 41
Contoh Kasus: Menghapus dari daftar simpul yang memiliki jarak terkecil (B) 0
2 2
A 1
4
Data Jarak dan Status untuk Iterasi ke-i
2 T 3 T
A 0 0 -
B 2 B 2 -
C 3 C 3 C
D 1 1 -
E 3 E 3 E
3
F 9 F 9 F
G 5 G 5 G
2
C 5
9
3
10 2
D 8
F
B
1 1
4
E
3
6
G 5
42
Contoh Kasus: Menghapus dari daftar simpul yang memiliki jarak terkecil (E) 0
2 2
A 1
4
Data Jarak dan Status untuk Iterasi ke-i
3 T 4 T
A 0 0 -
B 2 2 -
C 3 C 3 C
D 1 1 -
E 3 E 3 -
3
F 9 F 9 F
G 5 G 5 G
2
C 5
9
3
10 2
D 8
F
B
1 1
4
E
3
6
G 5
Tidak ada update jarak
43
Contoh Kasus: Menghapus dari daftar simpul yang memiliki jarak terkecil (C) 0
2 2
A 1
4
Data Jarak dan Status untuk Iterasi ke-i
4 T 5 T
A 0 0 -
B 2 2 -
C 3 C 3 -
D 1 1 -
E 3 3 -
3
F 9 F 8 F
G 5 G 5 G
2
C 5
8
3
10 2
D 8
F
B
1 1
4
E
3
6
G
distance(F) = 3 + 5 = 8
5
44
Contoh Kasus: Menghapus dari daftar simpul yang memiliki jarak terkecil (G) 0
2 2
A 1
4
Data Jarak dan Status untuk Iterasi ke-i
5 T 6 T
A 0 0 -
B 2 2 -
C 3 3 -
D 1 1 -
E 3 3 -
3
F 8 F 6 F
G 5 G 5 -
2
C 5
6
3
10 2
D 8
F
B
1 1
4
E
3
6
G 5
Distance sebelumnya distance(F) = min (8, 5+1) = 6 45
Contoh Kasus: Menghapus dari daftar simpul yang memiliki jarak terkecil (F) 0
2 2
A 1
4
Data Jarak dan Status untuk Iterasi ke-i
6 T 7 T
A 0 0 -
B 2 2 -
C 3 3 -
D 1 1 -
E 3 3 -
3
F 6 F 6 -
G 5 5 -
2
C 5
Hasil Selesai
6
3
10 2
D 8
F
B
1 1
4
E
3
6
G 5
46
Algoritma Dijkstra dapat digunakan pada Graf tidak berarah Hasil Kasus
Algoritma Bellman-Ford Algoritma Bellman-Ford membantu kita menemukan jalur terpendek dari sebuah simpul ke semua simpul lain dari sebuah graf berbobot. Ini mirip dengan algoritma Dijkstra, bedanya algoritma Bellman-Ford ini dapat bekerja dengan ruas yang memiliki bobot negatif. Mengapa seseorang memiliki kasus dimana ruas dari graf ada yang berbobot negatif dalam kehidupan nyata? Ruas berbobot negatif mungkin tampak tidak berguna pada awalnya, tetapi itu sebenarnya dapat menjelaskan banyak fenomena seperti arus kas, panas yang dilepaskan atau diserap dalam reaksi kimia, dll.
Pseudocode Bellman-Ford
function bellmanFord(G, S) for each vertex V in G distance[V] ← infinite previous[V] ← NULL distance[S] ← 0 for each vertex V in G for each edge (U,V) in G tempDistance ← distance[U] + edge_weight(U, V) if tempDistance < distance[V] distance[V] ← tempDistance previous[V] ← U for each edge (U,V) in G If distance[U] + edge_weight(U, V) < distance[V} Error: Negative Cycle Exists return distance[], previous[]
Kita perlu mengelola jarak jalur setiap simpul. Kita bisa menyimpannya dalam array ukuran v, di mana v adalah jumlah simpul. Kita juga ingin bisa mendapatkan jalur terpendeknya, tidak hanya mengetahui panjang jalur terpendek. Untuk ini, kita memetakan setiap simpul ke simpul yang terakhir memperbarui panjang jalurnya. Setelah algoritma selesai, kita dapat mundur dari simpul tujuan ke simpul sumber untuk menemukan jalurnya tersebut.
Penggunaan Bellman-Ford pada kasus yang sama dengan sebelumnya A
4 2
F
10 2
D
8
5
B
3
1
C
Sumber = A
2
4
E
6 1
G
Iterasi yang terjadi pada penggunaan Algoritma Bellman-Ford iterasi ke-1 --> untuk ruas (A,B) = 2
iterasi ke-1 --> untuk ruas (C,A) = 4
karena d(B) = 1000 > d(A) + bobot(A,B) = 0 + 2 = 2
karena d(A) = 0 tidak > d(C) + bobot(C,A) = 1000 + 4 = 1004
jadi d(B) menjadi = 2
tidak ada yang dilakukan. jadi d(A) tetap = 0
predecessor(B) menjadi = 1 iterasi ke-1 --> untuk ruas (A,D) = 1 karena d(D) = 1000 > d(A) + bobot(A,D) = 0 + 1 = 1 jadi d(D) menjadi = 1 predecessor(D) menjadi = 1 iterasi ke-1 --> untuk ruas (B,D) = 3 karena d(D) = 1 tidak > d(B) + bobot(B,D) = 2 + 3 = 5 tidak ada yang dilakukan. jadi d(D) tetap = 1 iterasi ke-1 --> untuk ruas (B,E) = 10
iterasi ke-1 --> untuk ruas (C,F) = 5 karena d(F) = 1000 tidak > d(C) + bobot(C,F) = 1000 + 5 = 1005 tidak ada yang dilakukan. jadi d(F) tetap = 1000 iterasi ke-1 --> untuk ruas (D,C) = 2 karena d(C) = 1000 > d(D) + bobot(D,C) = 1 + 2 = 3 jadi d(C) menjadi = 3 predecessor(C) menjadi = 4 iterasi ke-1 --> untuk ruas (D,E) = 2
karena d(E) = 1000 > d(B) + bobot(B,E) = 2 + 10 = 12
karena d(E) = 12 > d(D) + bobot(D,E) = 1 + 2 = 3
jadi d(E) menjadi = 12
jadi d(E) menjadi = 3
predecessor(E) menjadi = 2
predecessor(E) menjadi = 4
Lanjutan ke-1 iterasi ke-1 --> untuk ruas (D,F) = 8
iterasi ke-2 --> untuk ruas (A,B) = 2
karena d(F) = 1000 > d(D) + bobot(D,F) = 1 + 8 = 9
karena d(B) = 2 tidak > d(A) + bobot(A,B) = 0 + 2 = 2
jadi d(F) menjadi = 9
tidak ada yang dilakukan. jadi d(B) tetap = 2
predecessor(F) menjadi = 4 iterasi ke-1 --> untuk ruas (D,G) = 4 karena d(G) = 1000 > d(D) + bobot(D,G) = 1 + 4 = 5 jadi d(G) menjadi = 5 predecessor(G) menjadi = 4 iterasi ke-1 --> untuk ruas (E,G) = 6 karena d(G) = 5 tidak > d(E) + bobot(E,G) = 3 + 6 = 9 tidak ada yang dilakukan. jadi d(G) tetap = 5 iterasi ke-1 --> untuk ruas (G,F) = 1 karena d(F) = 9 > d(G) + bobot(G,F) = 5 + 1 = 6
iterasi ke-2 --> untuk ruas (A,D) = 1 karena d(D) = 1 tidak > d(A) + bobot(A,D) = 0 + 1 = 1 tidak ada yang dilakukan. jadi d(D) tetap = 1 iterasi ke-2 --> untuk ruas (B,D) = 3 karena d(D) = 1 tidak > d(B) + bobot(B,D) = 2 + 3 = 5 tidak ada yang dilakukan. jadi d(D) tetap = 1 iterasi ke-2 --> untuk ruas (B,E) = 10 karena d(E) = 3 tidak > d(B) + bobot(B,E) = 2 + 10 = 12 tidak ada yang dilakukan. jadi d(E) tetap = 3 iterasi ke-2 --> untuk ruas (C,A) = 4
jadi d(F) menjadi = 6
karena d(A) = 0 tidak > d(C) + bobot(C,A) = 3 + 4 = 7
predecessor(F) menjadi = 7
tidak ada yang dilakukan. jadi d(A) tetap = 0
Gambaran Iterasi keseluruhan Simpul Langkah 1 Langkah 2 Iterasi ke-1 Langkah 2 Iterasi ke-2 Langkah 2 Iterasi ke-3 Langkah 2 Iterasi ke-4 Langkah 2 Iterasi ke-5 Langkah 2 Iterasi ke-6 Langkah 3 (Iterasi ke-7)
A 0 0 0 0 0 0 0 0
B 1000 2 2 2 2 2 2 2
C 1000 3 3 3 3 3 3 3
Keterangan: 1000 = ∞
D 1000 1 1 1 1 1 1 1
E 1000 3 3 3 3 3 3 3
F 1000 6 6 6 6 6 6 6
G 1000 5 5 5 5 5 5 5
Lanjutan, akhirnya... iterasi ke-7 --> untuk ruas (D,E) = 2 karena d(E) = 3 tidak > d(D) + bobot(D,E) = 1 + 2 = 3 tidak ada yang dilakukan. jadi d(E) tetap = 3 iterasi ke-7 --> untuk ruas (D,F) = 8 karena d(F) = 6 tidak > d(D) + bobot(D,F) = 1 + 8 = 9 tidak ada yang dilakukan. jadi d(F) tetap = 6 iterasi ke-7 --> untuk ruas (D,G) = 4 karena d(G) = 5 tidak > d(D) + bobot(D,G) = 1 + 4 = 5 tidak ada yang dilakukan. jadi d(G) tetap = 5 iterasi ke-7 --> untuk ruas (E,G) = 6
Data Predecessor before(B) = A before(C) = D before(D) = A before(E) = D before(F) = G before(G) = D jalur terpendek dari A ke G adalah A -> D -> G dengan jarak = 5 jalur terpendek dari A ke F adalah A -> D -> G -> F dengan jarak = 6
karena d(G) = 5 tidak > d(E) + bobot(E,G) = 3 + 6 = 9
jalur terpendek dari A ke E adalah A -> D -> E dengan jarak = 3
tidak ada yang dilakukan. jadi d(G) tetap = 5
jalur terpendek dari A ke D adalah A -> D dengan jarak = 1
iterasi ke-7 --> untuk ruas (G,F) = 1 karena d(F) = 6 tidak > d(G) + bobot(G,F) = 5 + 1 = 6 tidak ada yang dilakukan. jadi d(F) tetap = 6
jalur terpendek dari A ke C adalah A -> D -> C dengan jarak = 3 jalur terpendek dari A ke B adalah A -> B dengan jarak = 2
Hasil yang diperoleh 0
2
A
B
1 3
2 C
6
2
D
1 F
2
1
4
E
3
G
5
Hasil Akhir
Kasus Ruas Negatif A
5 2
B -2 2
C
3
D
0 A
5 2
B 4 -2 2
2 C
3
jalur terpendek dari A ke D adalah A -> D dengan jarak = 2 jalur terpendek dari A ke C adalah A -> D -> B -> C dengan jarak = 2 jalur terpendek dari A ke B adalah A -> D -> B dengan jarak = 4
D 2
Algoritma Floyd-Warshall Algoritma Floyd-Warshall adalah algoritma untuk mencari jalur terpendek antara semua pasangan simpul dalam sebuah graf berbobot. Algoritma ini berfungsi untuk graf berbobot berarah dan tidak berarah. Namun, algoritma ini tidak berfungsi untuk graf dengan siklus negatif (yang mengandung jumlah/total bobot siklus negatif). Algoritma Floyd-Warhshall disebut juga sebagai algoritma Floyd, algoritma Roy-Floyd, algoritma Roy-Warshall, atau algoritma WFI. Algoritma ini menggunakan pendekatan pemrograman dinamis untuk menemukan jalur terpendek.
Pseudocode Floyd-Warshall n = no of vertices A = matrix of dimension n*n for k = 1 to n for i = 1 to n for j = 1 to n Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j]) return A
Contoh Kasus 6 1
2,5
2
3 2
8 7
1,5
4,6
2,5
1,7 4
3
0,4
1,4
0,9 0,55
9 0,85
5
2,5
4,3
0,45
5,9 10
Tabel Data A B C D E F G H I J
A * * * * * * * * * *
B 3 * * * * * * * * *
C 2,5 2,5 * * * * * * * *
D * * 0,55 * 1,4 * * * * *
E * 1,5 0,99 * * * * * * 0,45
F * 2 * * * * * * * *
G * * * * * 2,5 * * * *
H * * * * * * 4,6 * * *
I * * * * 0,85 * * 4,3 * *
J * * * 1,7 0,4 * * * 5,9 *
Data awal
Iterasi ke-1
Iterasi ke-10 (terakhir)
Masalah Aliran Maksimal (Maximum Flow) Apa itu Aliran Jaringan?
Aliran jaringan adalah graf berarah D = (V, A) sedemikian rupa masingmasing ruas memiliki kapasitas non-negatif c (u, v) ≥0 Dua simpul dibedakan pada di Graf tersebut yaitu: Sumber (dilambangkan dengan s): Derajat masuk ke simpul ini adalah 0. Muara (dilambangkan dengan t): Derajat keluar dari simpul ini adalah 0 Aliran dalam jaringan adalah fungsi bernilai integer yang didefinisikan pada ruas-ruas dari G yang memenuhi 0 ≤ f (u, v) ≤ c (u, v), untuk setiap
Contoh Aliran
Kapasitas Aliran
10, 9
1
8,8
1,1
s 6, 6
2
t 10,7
Ilustrasi Aliran dan Kapasitas pada ruas di atas: fs,1 = 9 , cs,1 = 10 (Aliran yang Valid karena 10 > 9) fs,2 = 6 , cs,2 = 6 (Aliran yang Valid karena 6 ≥ 6) f1,2 = 1 , c1,2 = 1 (Aliran yang Valid karena 1 ≥ 1) f1,t = 8 , c1,t = 8 (Aliran yang Valid karena 8 ≥ 8) f2,t = 7 , c2,t = 10 (Aliran yang Valid karena 10 > 7)
Menentukan Aliran Maksimal Untuk menentukan atau menghitung aliran maksimal dari suatu Graf, dapat dilakukan dengan beberapa cara: - Menggunakan intuisi - Menggunakan Algoritma (Ford-Fulkerson) - Max Flow Min Cut
Kasus 1 dengan menggunakan Intuisi Pada umumnya untuk kasus sederhana dapat kita gunakan intuisi 10
1
8
1
s 6
2
t 10
s – 1 – t → Aliran = 8 s – 2 – t → Aliran = 6 s – 1 – 2 - t → Aliran = 1
Jadi Aliran Maksimalnya adalah 15
Algoritma Ford-Fulkerson FORDFULKERSON(G,E,s,t) FOREACH e E f(e) 0
Gf residual graph
WHILE (there exists augmenting path P) f augment(f, P) update Gf
ENDWHILE RETURN f
AUGMENT(f,P)
b bottleneck(P) FOREACH e P IF (e E)
// backwards arc
f(e) f(e) + b
ELSE
// forward arc
f(eR) f(e) - b
RETURN f
Kasus 2 dengan menggunakan Ford4 Fulkerson 2
3
s
5
1
1 2 3
4 1
1 2 2
3 Ini adalah jaringan awal, ditambah pembalikan arkus (Arc).
t
Ford-Fulkerson
2
3
s
4
5 1
1 2 3
4 1
1 2 2
3 Ini adalah jaringan awal, dan jaringan sisa awal.
t
Ford-Fulkerson
2
3
s
4
5 1
1 2 3
4 1
1 2 2
t
3 Temukan jalur s ke t di dalam Graf
Ford-Fulkerson
2
3
s
4
5 1
1 2 2 3 1
4 1
1 1 2 2 1
t
3
Tentukan kapasitas jalurnya (∆). Kirim (∆) aliran pada jalur tersebut. Perbaharui kapasitas sisa.
Ford-Fulkerson
2
3
s
4
5 1
1 2 2 3 1
4 1
1 1 2 2 1
t
3
Temukan jalur s ke t di dalam Graf
Ford-Fulkerson
4
2
3
s
5 1
1 2 1 2 3 1
1
4 1
3
1 11 2 1 1
t
1
Tentukan kapasitas jalurnya (∆). Kirim (∆) aliran pada jalur tersebut. Perbaharui kapasitas sisa.
Ford-Fulkerson
4
2
3
s
5 1
1 2 1 2 3 1
1
4 1
3
1 11 2 1 1
t
1
Temukan jalur s ke t di dalam Graf
Ford-Fulkerson
4
2
3
s
5 1
1 1 2 3 1
1 2
4 1
3
1 11 1 1 2
t
1
Tentukan kapasitas jalurnya (∆). Kirim (∆) aliran pada jalur tersebut. Perbaharui kapasitas sisa.
Ford-Fulkerson
4
2
3
s
5 1
1 1 2 2 3 1
1 2
4 1
3
1 11 1 1 2
t
1
Temukan jalur s ke t di dalam Graf
Ford-Fulkerson
4
2
3
s
5 1
1 1 2 1 2 2 1
1 2
4 1
3
1 11 1
1 2
t
2 1
Tentukan kapasitas jalurnya (∆). Kirim (∆) aliran pada jalur tersebut. Perbaharui kapasitas sisa.
Ford-Fulkerson
4
2
3
s
5 1
1 1 2 1 2 2 1
1 2
4
1 11 1 2
1
3
t
2 1
Temukan jalur s ke t di dalam Graf
Ford-Fulkerson
4 3
2
3 2
1
1
s
1 2 2 1
1
5 1
1 1
1 2
4
1 2
1
3
t
2 1
Tentukan kapasitas jalurnya (∆). Kirim (∆) aliran pada jalur tersebut. Perbaharui kapasitas sisa.
Ford-Fulkerson
4 3
2
3 2
1
1
s
1 2 2 1
1
5 1
1 1
1 2
4
1 2
1
3
t
2 1
Tidak ada jalur s-t di jaringan sisa. Aliran ini sudah optimal.
Ford-Fulkerson
4 3
2
3 2
1
1
s
1 2 2 1
1
5 1
1 1
1 2
4
1 2
1
3
t
2 1
Ini adalah simpul-simpul yang dapat dicapai dari simpul s.
Ford-Fulkerson
1
2
5
1
s s – 2 – 5 – t → Aliran = 1
1 2
4
2
2 2
t
3
s – 4 – t → Aliran = 2 s – 3 – t → Aliran = 2 Inilah Hasil Aliran Maksimalnya, yakni 5
Alternatif lain untuk menghitung Aliran Maksimal Max Flow Min Cut Maximum Flow Minimum Cut-Set Bahwa Aliran Maksimal diperoleh pada Cut-Set bernilai Minimum
Cut-Set (Himpunan Potong) Ada Subgraf S dari graf terhubung G, yang bila kita ambil / pindahkan dari G, akan menyebabkan G tidak terhubung . Kalau tidak ada Subgraf sejati R dari S, yang pemindahannya juga menyebabkan G tidak terhubung, maka S disebut Cut-Set dari G. A
K3 C
B
{(A,B)}, {(A,C)}, {(B,C)} masing2 bukan Cut-Set {(A,B), (A,C)}, adalah Cut-Set {(A,B), (B,C)}, adalah Cut-Set {(C,A), (C,B)}, adalah Cut-Set {(A,B), (A,C), (B,C)} masing2 bukan Cut-Set
Cut-Set menggunakan ‘garis pemotong’ Cut-Set yang terdapat pada K4 berikut ini adalah seperti yang diwakili oleh garis merah putus-putus. Pada K4 tersebut terdapat 6 buah Cut-Set. A
B
{(B,A), (B,C), (B,D)}
{(A,D), (A,C), (B,D), (B,C)}
K4 D
C
{(A,C), (B,C), (D,C)}
Kasus 1 dengan Max Flow Min Cut 15
20 16 10
1
8
1
s 6
2
18
t 10
Cut-Set yang digunakan untuk menentukan Aliran Maksimal adalah Cut-Set yang memisahkan antara sumber (source) dan muara (sink)
Kasus 2 dengan Max Flow Min Cut 8 8
4
2 3
s
5 1
1 2 3
4 1
3
5 1
2 2
t
Kasus 3
Contoh Cut-Set yang dapat dihitung 18
20
15
17
Daftar Pustaka Suryadi, H.S. Teori Graf Dasar, Jakarta: Gunadarma Discrete Mathematics and Its Applications (3rd edition). Kenneth H Rosen. McGraw-Hill Inc. Singapore, 1995 L Toscano, S Stella, and E Milotti, Using graph theory for automated electric circuit solving, [tersedia: https://core.ac.uk/download/pdf/53745212.pdf] Rinaldi Munir, Diktat Kuliah Matematika Diskrit Bandung:ITB MIT OCW Ghidoni, S., Nanni, L., Brahnam, S., and Menegatti, E. 2014. Texture Descriptors Based on Dijkstra's Algorithm for Medical Image Analysis. Studies in Health Technology and Informatics 207:74-82. Ustun, T.S., Ozansoy, C., and Zayegh, A. 2011. Implementation of Dijkstra's algorithm in a dynamic microgrid for relay hierarchy detection. DOI: 10.1109/SmartGridComm.2011.6102370
