1
Pelabelan aliran maksimum dengan algoritma Ford-Fulkerson telah diperkenalkan pada pertengahan 1950, Merupakan algoritma untuk memaksimumkan aliran (flow) dengan kapasitas dan biaya yang terbatas pada jaringan. Algoritma Ford-Fulkerson juga merupakan metode yang dipakai untuk melakukan penambahan aliran dalam suatu jaringan. 2
Sebuah digraph G = (V,E), yang mempunyai fungsi kapasitas pada tiap sisi (edge) disebut dengan jaringan berkapasitas Pada jaringan ini terdapat dua vertex yg berbeda, 1. Vertex s dengan in-degree 0 disebut dengan sumber 2. vertex t dengan out-degree 0 disebut dengan tujuan (sink)
3
kapasitas 4
12
5
15
12
s= 1
27
t= 6 6
24
3
2
8
12 6
kapasitas tiap edge (i,j)
adalah c(i,j) 0. 4
flow
• flow (aliran) dlm jaringan adalah nilai integer
fungsi f yg didefinisikan di tiap edge. • 0 f(i,j) c(i,j) untuk setiap edge (i,j) .
5
Conservation
Condition
• Untuk setiap vertex j , dimana j bukan sumber s
atau tujuan t, maka penjumlahan aliran yg masuk ke j sama dengan aliran yang ke luar dari j. feasible
flow.
• Aliran yang memenuhi disebut conservation
condition feasible flow.
6
Algoritma Ford-Fulkerson menentukan maximum flow pada jaringan. Jika f merupakan feasible flow dalam G. maka Edge (i,j) dikatakan : saturasi jika f(i,j) = c(i,j) bebas jika f(i,j) = 0 positif if 0 < f(i,j) < c(i,j).
7
tiga hal penting yang perlu diperhatikan dalam kaitannya dengan metode menggunakan algoritma Ford-Fulkerson, yaitu: • • •
Residual network Flow Augmenting Path Minimum Cutset
8
residual capacity (rc) dari sebuah edge (i,j) • sama dengan c(i,j) – f(i,j) ketika (i,j) adalah
forward edge, dan • sama dengan f(i,j) ketika (i,j) adalah backward edge.
9
flow/cap
i i
rc
j flow
Forward edge
j
flow/cap
i i
flow
j rc
j
Backward edge
10
11
Flow
Aughmenting Path merupakan suatu lintasan yang memungkinkan terjadinya suatu penambahan aliran.
Syarat
•
dilakukan Flow Aughmenting Path
∆ = ci,j – fi,j ≠ 0
12
Langkah
Flow Aughmenting Path:
• Menaikkan flow forward link sampai menuju ci,j • Menurunkan flow arah backward link sampai
menuju 0 (kapasitas terendah)
13
14
augmenting
path
• Adalah urutan alternatif dari vertex dan edge
s, e1, v1, e2, v2, …, ek, t • Dengan syarat tidak ada vertex yang diulang
dan tidak ada forward edge yg saturasi dan tidak ada backward edge yg bebas
15
3/8
6/7
2/6
4/9
s
t
5
s
3
1
6
2
4
5
4
t
16
Kita
dapat meningkatkan flow pada path s ke t dengan menentukan excess flow capacity dari path ini.
Dari
kiri ke kanan, residual capacities (jumlah flow yg dapat ditingkatkan pada edge) adalah huruf pertama pada masing-masing edge. 17
excess flow capacity dari sebuah augmenting path sama dengan minimum dari residual capacities dari setiap edge dalam path. 5
3
1
6
2
4
5
4
s
t
4
4
0
7
1
5
s
4
5
t
minimum(5, 1, 2, 5) = 1
18
Theorema: flow dalam sebuah capacitated network adalah maximum flow jika dan hanya jika tidak terdapat augmenting path dalam jaringan Angka menunjukkan kapasitas tiap link
3 X
W
4
5
5
s 6
t Z
4
4 Y
19
0
3
X
0
W
5
5 4
0
0
s
t
0
0
0
6 0
Z
4
0
Y
4
20
Augmenting path: s->X->W->t Excess capacity of s->X->W->t = min(4, 3, 5) = 3 0 3
3
X
W
2
5 1
3
3
s
t
0
3
0
6 0
4
Z
0
Y
4
21
Augmenting path: s->X->t Excess capacity of s->X->t = min(1, 5) = 1
4
0
X
3
W
2
4 0
4
3
s
t
1
4
0
6 0
Z
4
0
Y
4
22
Augmenting path: s->Z->Y->t Excess capacity of s->Z->Y->t = min(6, 4, 4) = 4 0 4
3
X
W
2
4 0
8
3
s
t
1
8
4
2 4
0
Z
4
Y
0
23
At
this point, there are no remaining augmenting paths! Therefore the flow is a maximum = 8. X
3/3
W
4/4
3/5 1/5
s 4/6
Z
4/4
t Y
4/4
24
Minimum
cut-set yaitu suatu metode pemecahan jaringan menjadi beberapa subnet. Minimum cut-set akan membentuk suatu partisi (membentuk dua buah jaringan baru)
25
26
algoritma Ford-Fulkerson mempunyai dua bagian, yang dinamakan Routine A dan Routine B,
Routine A
• Yg pertama adalah proses labeling yang mencari sebuah
flow augmenting path { i.e., path dari s ke t yg mempunyai f < c untuk seluruh arah foward dan f > 0 untuk seluruh arah backward. Jika Routine A menemukan sebuah flow augmenting path,maka :
Routine B
• Routine B mengubah flow yg sesuai. Dengan kata lain,
jika sudah tidak terdapat augmenting path , maka flow sudah dipastikan optimal, sesuai dengan teorema:
27
Sebuah flow f mempunyai nilai maksimum jika dan hanya jika tidak terdapat flow augmenting path
28
Terdapat dua tahapan dalam melakukan algoritma FordFulkerson, yaitu:
1.
Tahap pelabelan, terdiri atas beberapa langkah a. b.
simpul sumber dengan (0,∞) Bila i merupakan simpul yang sudah dilabelkan dengan fi,j < ci,j , maka beri label untuk simpul j dengan (i, e(j)) di mana
a.
b.
e(j) = min (e(i), ci,j - fi,j ).
Arah aliran dari i ke j
c. Bila i merupakan simpul yang sudah dilabelkan, j simpul yang belum dilabelkan dan fj,i > 0, buat label di j dengan (-i, e(j)) dengan a. e(j)= min (e(i), fj,i ) 29
2.
Pengubahan aliran, terdiri atas beberapa tahap: a. untuk simpul-simpul yang terlabelkan dengan
prosedur 1.b, maka aliran ditambah fi,j = fi,j + e(t) b. untuk simpul-simpul yang terlabelkan dengan cara 1.c maka aliran dikurangi fj,i=fi,j – e(t) c. Setelah prosedur selesai, hapus label-label tadi. Kemudian ulangi prosedur hingga tidak ditemukan lagi aughmenting path.
30
Jika
kita mulai dengan setiap feasible flow (e.g., f = 0). Secara umum, sebuah node dalam tiga kondisi berikut: • unlabeled, • labeled dan scanned, atau • labeled dan unscanned.
31
aliran kapasitas 7
2
(6,3)
4
1
6
3
(8,7)
7
5
Sumber di simpul 1 dan tujuan di simpul 6 32
1.
Labelkan simpul satu dengan (+0,∞)
2.
Pilih simpul yg SL (sudah label) tapi BS ( belum scan)simpul 1 dipilih
3.
Simpul 1 sebagai simpul i. simpul i SL dan labelkan setiap simpul j yg BL (belum label)
Cari fij < cij, kalau tidak ada cari fji > 0.
4.
Jika fij < cij maka labelkan simpul j dengan (+i,(ej)) dengan e(j)=min (e(i), ci,j fi,j ). Jika fji>0, maka labelkan simpul j dgn (-i,e(j)) dimana e(j)=min (e(i),fji)
Sekarang simpul i SS (sudah scan), simpul j SL dan BS
Cek apakah simpul tujuan SL. Bila SL berarti sudah ditemukan ‘jalan aliran yg diperbesar’ tambahkan fij + e, bila belum, ulangi langkah 2 & 3
33
Contoh pelabelan Bila i merupakan simpul yang sudah dilabelkan dan fi,j < ci,j , maka beri label untuk simpul j dengan (i, e(j)) di mana e(j) = min (e(i), ci,j fi,j ). Arah aliran dari i ke j Labelkan simpul sumber dengan (+0,∞)
e(i)
(+1,3)
2 7
(6,3)
(+2,3)
4
(+0,∞)
1
6
7
(+5,2)
3
(8,7)
5 (-4,2) 34
Contoh pelabelan (+1,3)
2 7
(6,3)
(+2,3)
4
(+0,∞)
1
6
7
(+5,2)
3
(8,7)
Bila i merupakan simpul yang sudah dilabelkan, j simpul yang belum dilabelkan dan fj,i > 0, buat label di j dengan (-i, e(j)) dengan e(j)= min (e(i), fj,i )
5 (-4,2)
35
•Tujuan SL (sudah label) •Tambahkan fij+e=7+2=9 (+1,3)
2 7
(6,3)
(+2,3)
4
(+0,∞)
1
6
7
(+5,2)
3
(8,7)
5 (-4,2) 36
Contoh penambahan aliran 2 9
(6,5)
4
1
6
3
(8,7)
9
5
Tambahkan 2 satuan ke tujuan Tambahkan 2 satuan aliran f56 Kurangkan 2 satuan aliran f54 Tambahkan 2 satuan aliran ke f24 Tambahkan 2 satuan aliran ke f12 37
Setelah prosedur selesai, hapus label-label tadi. Kemudian ulangi prosedur hingga tidak ditemukan lagi aughmenting path.
38
(+1,1)
2 9
(6,5)
(+2,1)
4
(+0,∞)
1
6
3
(8,7)
9
5
Tidak
bisa dilabelkan sampai tujuan, artinya aliran jaringan sudah optimal 39
9
4 (2,2)
2
(8,7)
1
3
Sumber
(8,1)
6
9
5
di node 1 dan tujuan di node 6 40
41
G:
0 10 s
0 10
2
0 4
2 0
0 8
3
0 9
4
60
0 10
5
0 10
flow capacity
t
Flow value = 0
42
2
4
4
2
8
6
10
3
9
5
10
Gf: 10 s
10
residual capacity
t
43
Gf:
2
4
4
2
2
8
6
10
10
3
9
5
2
8
s
t
8
Flow value = 8
44
Gf:
s
2
4
4
10
2
8
6
10
10
3
7
5
10
t
2 Flow value = 10
45
2
Gf:
4
4
6
s
10
2
8
6
4
4
3
1
5
10
6
t
8 Flow value = 16
46
2 2
Gf:
2
4
8
s
10
2
8
6
2
2
3
1
5
10
8
8
t
Flow value = 18
47
3 2
Gf:
s
1
10
2
7
1
3
9
9
4
1
9 6
1
5
10
t
Flow value = 19
48
3 2
Gf:
s
1
4
10
2
7
1
3
9
1
9 6
1
5
10
t
9
Cut capacity = 19
Flow value = 19
49
1.
Dengan algoritma ford fulkerson, tentukan penambahan aliran yang dapat dilakukan untuk graph berikut (sumber di node 1 dan tujuan di node 6): (8)
2
(4)
4
(8)
(4)
(2)
1
(8)
6
(3) 3
(8)
5
(4)
50
2.
Dengan algoritma ford fulkerson, tentukan penambahan aliran yang dapat dilakukan untuk graph berikut (sumber di node 1 dan tujuan di node 6):
(7,6) 9
2
(8,7) (3,1)
1 (9,3)
3
4
(2,2)
(3,1)
(8,1)
(8,6) 6
5
9
(8,3)
51
