bab 8 ford fulkerson

Download BAB 8 Ford Fulkerson

Post on 11-Feb-2018

226 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • 7/23/2019 BAB 8 Ford Fulkerson

    1/30

    Algoritma Ford

  • 7/23/2019 BAB 8 Ford Fulkerson

    2/30

    1950,

    ? Algoritma Ford-Fulkerson merupakan salah satu dari algoritma yang dipakaidalam aplikasi graph. Berdasarkan pengertiannya algoritma Ford-Fulkersonyaitu algoritma untuk memaksimumkan aliran (flow) dengan kapsitas danbiaya yang terbatas pada

    jaringan.

    ? Algoritma Ford-Fulkerson juga merupakan metode yang dipakai untukmelakukan penambahan aliran dalam suatu jaringan.

    2

    kapasitasSebuahdigraphG=(V,E), yangmempunyaifungsikapasitaspadatiapsisi

    (edge)disebutdenganjaringanberkapasitasPadajaringaniniterdapatduavertexygberbeda,

  • 7/23/2019 BAB 8 Ford Fulkerson

    3/30

    6

    5 15

    38

    t=6

  • 7/23/2019 BAB 8 Ford Fulkerson

    4/30

    (i,j) .

    ? ConservationCondition? Untuk setiap vertex j , dimana j bukansumber s

    atau tujuan t, maka penjumlahan aliran

    yg masukke j sama dengan aliran yang ke luar dari j.

    ? feasibleflow.? Aliran yang memenuhi disebutconservation

    condition feasible flow.

    4

    maximum flow

  • 7/23/2019 BAB 8 Ford Fulkerson

    5/30

    5

    flow

    ? flow? flow (aliran) dlm jaringan adalah nilaiinteger

    fungsi f yg didefinisikan di tiap edge.

    ? 0 f(i,j) c(i,j) untuk setiap edge(i,j) .? ConservationCondition

    ? Untuk setiap vertex j , dimana j bukansumber s

    atau tujuan t, maka penjumlahan aliran

  • 7/23/2019 BAB 8 Ford Fulkerson

    6/30

    ? tiga hal penting yang perlu diperhatikan dalam kaitannya dengan metodemenggunakan algoritma Ford-Fulkerson, yaitu:

    ? Residual network? Flow Augmenting Path

    ? Minimum Cutset

    7

    residual capacity

  • 7/23/2019 BAB 8 Ford Fulkerson

    7/30

    rc flowflow rc

    i j i j

    Forward edge Backward edge

    8

    Residual network

    ? Residual network berisikan edges dengan flow yang lebih. Berikut diberikancontoh dari grafik residual network

  • 7/23/2019 BAB 8 Ford Fulkerson

    8/30

    ? Syarat dilakukan Flow Aughmenting Path? = ci,jfi,j0

    ? Langkah Flow Aughmenting Path:?

    Menaikkanflow forwardlinksampaimenujuci,j? Menurunkan flowarahbackwardlinksampai

    menuju 0 (kapasitas terendah)

    10

  • 7/23/2019 BAB 8 Ford Fulkerson

    9/30

    11

  • 7/23/2019 BAB 8 Ford Fulkerson

    10/30

    12

    Example: Augmenting

    Path3/8 6/7 2/6 4/9

    st

    5 3 1 6 2 4 5 4

    st

  • 7/23/2019 BAB 8 Ford Fulkerson

    11/30

    excess flow capacity dari sebuahaugmentingpath sama dengan minimum dariresidual

    capacities dari setiap edge dalampath.

    4 4 0 7 1 5 4 5

    st

  • 7/23/2019 BAB 8 Ford Fulkerson

    12/30

    X W

    4 55

    s t

    6 4

    4

    Z Y

    4

    0s

    6

    3 0

    0 X W 55

    0

    0 t0

    04 04

    0

  • 7/23/2019 BAB 8 Ford Fulkerson

    13/30

    3X W

    2

    5

    1 3

    3s 0 t

    3

    06

    40

    0 4ZY

    16

    Augmenting path

  • 7/23/2019 BAB 8 Ford Fulkerson

    14/30

    4s 1 t

    4

    6

    0

    4

    400

    Z Y

    17

    Augmenting path

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

    0

  • 7/23/2019 BAB 8 Ford Fulkerson

    15/30

    18

    Augmenting path

    ?At this point, there are no remainingaugmenting paths! Therefore the flow

    is a maximum = 8.

    4/43/3X

    W

    3/5

  • 7/23/2019 BAB 8 Ford Fulkerson

    16/30

    Minimum cut-set

    ?Minimum cut-set yaitu suatu metodepemecahan jaringan menjadi beberapa subnet. Minimum cut-set akan

    membentuk suatu partisi

    (membentuk dua buah jaringanbaru)

  • 7/23/2019 BAB 8 Ford Fulkerson

    17/30

    21

    Al it F d F lk

  • 7/23/2019 BAB 8 Ford Fulkerson

    18/30

    yg mempunyai f < c untuk seluruh arahfoward dan f> 0 untuk seluruh arah backward. JikaRoutine Amenemukan 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:

    22

    Theorem.

    Sebuah flow f mempunyai nilai

  • 7/23/2019 BAB 8 Ford Fulkerson

    19/30

    23

    Tahapan-TahapanAlgoritmaFord- Fulkerson

    ? Terdapat dua tahapan dalam melakukan algoritmaFord-Fulkerson, yaitu:

    1. Tahap pelabelan, terdiri atas beberapa tahap

    a. 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)) di mana

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

    Arah aliran dari i ke j

    a. Bila i merupakan simpul yang sudah dilabelkan, jsimpul yang belum dilabelkan dan fj,i > 0, buat label

  • 7/23/2019 BAB 8 Ford Fulkerson

    20/30

    b. untuk simpul-simpulyangterlabelkandengan

    cara 1.c maka aliran dikurangifj,i=fi,j e(t)c. Setelahprosedurselesai,hapuslabel-labeltadi.

    Kemudianulangiprosedurhinggatidak ditemukanlagi

    aughmentingpath.

    25

    Tahapan-TahapanAlgoritmaFord- Fulkerson

    ?Jika kita mulai dengan setiap feasibleflow (e.g., f = 0). Secara umum, sebuah node dalam tiga kondisi

    berikut:

  • 7/23/2019 BAB 8 Ford Fulkerson

    21/30

    nned.

    26

    contohaliran

    kapasitas

    (6,3)24

  • 7/23/2019 BAB 8 Ford Fulkerson

    22/30

    27

    Prosedur pelabelan

    1. Labelkan simpul satu dengan (+0,)

    2. Pilih simpul yg SL (sudah label) tapi BS ( belumscan)?simpul 1dipilih

    3. Simpul 1 sebagai simpul i. simpul i SL dan dan

    labelkan setiapsimpul 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)) dimanae(j)=min(e(i),fji)

  • 7/23/2019 BAB 8 Ford Fulkerson

    23/30

    Bila i merupakan simpul yang sudah dilabelkan danfi,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

    (6,3)

    (+2,3)

    4

    (+0,)77

    1

  • 7/23/2019 BAB 8 Ford Fulkerson

    24/30

    Contoh penambahanaliranTujuan SL (sudah label)

    Tambahkan fij+e=7+2=9(+1,3)

    2

    (6,3)

    (+2,3)

    4

    (+0,)77

  • 7/23/2019 BAB 8 Ford Fulkerson

    25/30

    Contoh penambahanaliran(6

    ,5)2

    4

    9 9

    16

    3

  • 7/23/2019 BAB 8 Ford Fulkerson

    26/30

    Setelah prosedur selesai, hapus

    label-label tadi. Kemudian ulangi prosedur hingga tidak ditemukan lagi

    aughmenting path.

    32

  • 7/23/2019 BAB 8 Ford Fulkerson

    27/30

    99

    16

    3

    (8,7)5

    ? Tidak bisa dilabelkan sampaitujuan,

    artinya aliran jaringan sudahoptimal

    33

  • 7/23/2019 BAB 8 Ford Fulkerson

    28/30

    )2

    4

    (2,2)

    9 9

    16

    3

    (8,1)5

    ? Sumber di node 1 dan tujuan di

  • 7/23/2019 BAB 8 Ford Fulkerson

    29/30

    35

  • 7/23/2019 BAB 8 Ford Fulkerson

    30/30

    We start with the flow set equal to 0 everywhere:

    36