pelabelan aliran maksimum dengan · pelabelan aliran maksimum dengan ... memaksimumkan aliran...

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

3

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 sumber2. vertex t dengan out-degree 0 disebut dengan tujuan

(sink)

4

kapasitas

s=

1

32

54

t=

6

27

12 15

246

12

12

8

6

kapasitas tiap edge (i,j)

adalah c(i,j) 0.

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

10

i jflow/cap

i jflowrc

i jflow/cap

i jrcflow

Forward edge Backward edge

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

16

s t

3/8 6/7 2/6 4/9

s t

5 3 1 6 2 4 5 4

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.

18

s t

4 4 0 7 1 5 4 5

minimum(5, 1, 2, 5) = 1

s t

5 3 1 6 2 4 5 4

19

s

X

Z Y

W

t

4

6

3

55

4 4

Theorema: flow dalam sebuah capacitated network adalah maximum flow jika dan hanya jika tidak terdapat augmenting path dalam jaringan

Angka menunjukkan

kapasitas tiap link

20

s

X

Z Y

W

t

4

0

3 0

5

0

5

0

6

04 0

4

0

0 0

Augmenting path: s->X->W->t Excess capacity of s->X->W->t = min(4, 3, 5) = 3

21

s

X

Z Y

W

t

1

3

0 3

2

3

5

0

6

04 0

4

0

3 3

Augmenting path: s->X->t Excess capacity of s->X->t = min(1, 5) = 1

22

s

X

Z Y

W

t

0

4

0 3

2

3

4

1

6

04 0

4

0

4 4

Augmenting path: s->Z->Y->t Excess capacity of s->Z->Y->t = min(6, 4, 4) = 4

23

s

X

Z Y

W

t

0

4

0 3

2

3

4

1

2

40 4

0

4

8 8

At this point, there are no remaining augmenting paths! Therefore the flow is a maximum = 8.

24

s

X

Z Y

W

t

4/4

3/3

3/5

1/5

4/64/4

4/4

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 Ford-Fulkerson, yaitu:

1. Tahap pelabelan, terdiri atas beberapa langkaha. simpul sumber dengan (0,∞)

b. Bila i merupakan simpul yang sudah dilabelkan dengan fi,j< ci,j , maka beri label untuk simpul j dengan (i, e(j)) dimana

a. e(j) = min (e(i), ci,j - fi,j ).

b. Arah aliran dari i ke j

c. Bila i merupakan simpul yang sudahdilabelkan, j simpul yang belumdilabelkan 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

32

1 6

5

4

3

2(6,3)

(8,7)

7 7

Sumber di simpul 1 dan tujuan di simpul 6

kapasitas

aliran

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.

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

4. Cek apakah simpul tujuan SL. Bila SL berarti sudah ditemukan ‘jalan aliran yg diperbesar’ tambahkan fij + e, bila belum, ulangi langkah 2 & 3

33

34

Contoh pelabelan

1 6

5

4

3

2(6,3)

(8,7)

7 7(+0,∞)

Labelkan simpul sumber dengan (+0,∞)

(+1,3)

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

e(i) (+2,3)

(-4,2)

(+5,2)

35

Contoh pelabelan

1 6

5

4

3

2(6,3)

(8,7)

7 7(+0,∞)

(+1,3)(+2,3)

(-4,2)

(+5,2)

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 )

36

1 6

5

4

3

2(6,3)

(8,7)

7 7(+0,∞)

(+1,3)(+2,3)

(+5,2)

•Tujuan SL (sudah label)•Tambahkan fij+e=7+2=9

(-4,2)

37

Contoh penambahan aliran

1 6

5

4

3

2(6,5)

(8,7)

9 9

Tambahkan 2 satuan ke tujuanTambahkan 2 satuan aliran f56Kurangkan 2 satuan aliran f54Tambahkan 2 satuan aliran ke f24Tambahkan 2 satuan aliran ke f12

38

Setelah prosedur selesai, hapus label-label tadi. Kemudian ulangi prosedur hingga tidak ditemukan lagi aughmenting path.

Tidak bisa dilabelkan sampai tujuan, artinya aliran jaringan sudah optimal

39

1 6

5

4

3

2(6,5)

(8,7)

9 9

(+1,1)

(+0,∞)

(+2,1)

Sumber di node 1 dan tujuan di node 6

40

1 6

5

4

3

2(8,7)

(2,2

)

(8,1)

9 9

41

42

s

2

3

4

5 t10

10

9

8

4

10

1062

0

0

0

0 0 0

0

0

G:

Flow value = 0

0

flow

capacity

43

residual capacity

s

2

3

4

5 t10 9

4

1062

Gf:

10 8

10

44

s

2

3

4

5 t10

4

106

Gf:

8

8

8

9

22

2

Flow value = 8

45

s

2

3

4

5 t

4

2

Gf:

10

810

2

10 7

106

Flow value = 10

46

s

2

3

4

5 t1

6

Gf:

10

810

8

6

6

4

4

4

2

Flow value = 16

47

s

2

3

4

5 t

62

Gf:

10

10

88

8

2

2 1

2

8 2

Flow value = 18

48

s

2

3

4

5 t1 9

1

162

Gf:

10

710

9

9

3

1

Flow value = 19

49

3

s

2

3

4

5 t1 9

1

162

Gf:

10

710

9

91

Flow value = 19Cut capacity = 19

1. Dengan algoritma ford fulkerson, tentukan

penambahan aliran yang dapat dilakukan

untuk graph berikut (sumber di node 1 dan

tujuan di node 6):

50

(8)

(3)

(4)

(4)(2)

(8)

(8)

(4)

(8)

1

2

3

6

4

5

2. Dengan algoritma ford fulkerson, tentukan

penambahan aliran yang dapat dilakukan untuk

graph berikut (sumber di node 1 dan tujuan di node

6):

51

9

9

(8,1)

(2,2)(3,1)

(3,1)

(8,3)

(8,6)

(9,3)

(8,7)

(7,6) 2

3

4

5

61