algoritma karzanov

7/30/2019 Algoritma Karzanov

1/14

Algoritma Karzanov

Oleh:

Rudi Tri Yulianto 5109100031

Hishniyatul Millah 5109100118

Mamluatul Hikmah 5109100708


2/14

Algoritma Karzanov

Algoritma ini memaksakan preflow dari verteksource melalui edge-edge network yang manatelah dibagi ke dalam layer-layer ke tujuan atau

sink kemudian menyeimbangkannya.Akan tetapi dengan proses tersebut dapatmenghasilkan beberapa vertex v dengan flowyang berlebihan.


3/14

Algoritma Karzanov -2-

Algoritma ini dijalankan seperti stack, yaknidimulai dari layer network yang paling akhiruntuk menyeimbangkan vertek-vertek tersebut,

baru kemudian memaksakan flow lagi padalayer yang sama.

Untuk edge yang terhubung dengan vertekyang telah diseimbangkan dan tidak dapatdigunakan lagi maka edge tersebut akan diblokatau tidak boleh dilewati lagi agar tidak ada flowyang dapat melewatinya.


4/14

Algoritma Karzanov -3-

Proses utama dari algoritma karzanov adalahsebagai berikut.

1. Membentuk atau membuat layer-layernetwork.

2. Memaksa masuk Preflow (push preflow).

3. Menyeimbangkan Preflow (rebalance preflow).


5/14

Studi Kasus

Diberikan directed graph seperti gambar di atas,dimana s adalah source atau vertek sumber dant sebagai sink atau vertek akhir sebagaitujuannya

s t1 2

3

4

2

1

5

4

6

73


6/14

Studi Kasus -2-

Langkah 0: Membuat network layer

4

t1 2

3

s

Layer 1 Layer 2 Layer 3 Layer 4

Indeks layer tersebutsesuai dengan panjangjalur terpendek jikapanjang tiap edge-nya

didefinisikan 1. Olehkarena itu tidak akanterdapat backwardedge.


7/14

Studi Kasus -3-

perhitungankapasitas suatuvertek adalah

jumlah nilai yangmasuk dan jumlahnilai yang keluar ituharus seimbangatau sama

4 + 2 > 1 (capacity limit)

Unbalance

1

4:5

2:3 1:11


8/14

Studi Kasus -4-

Langkah 1: Menekan Preflow (push preflow)

4

t1 2

3

s


8,[8]

5,[5] 4,[4]

5,[5]

6,[6]

2,[7] 2,[4]


9/14

Studi Kasus -5-

Langkah 2: Menyeimbangkan Preflow (rebalance preflow)

4

t1 2

3

s


8,[8]

5,[5] 4,[4]

5,[5]

1,[6]

2,[7] 2,[4]

Pada layer 3, vertek2 itu seharusnyadiseimbangkansehingga flow padaedge (1-2) itu

dirubah nilainyamenjadi 1


10/14

Studi Kasus -6-Dan karena edge (3-2), (2-t), serta (1-2)sudah penuh maka edge tersebut sudahtidak dapat dilewati lagi sehingga vertek 2diblok.

4

t1 2

3

s


8,[8]

5,[5] 4,[4]

5,[5]

1,[6]

2,[7] 2,[4]


11/14

Studi Kasus -7-Langkah 1: Menekan Preflow (bagian kedua)

Dari proses sebelumnya didapatkan edge (1-4) dan (4-t) itu masih terbuka

(belum diblok) maka langkah 1 ini diterapkan pada edge tersebut,

4

t1 2

3

s


8,[8]

5,[5] 4,[4]

5,[5]

1,[6]

7,[7] 4,[4]


12/14

Studi Kasus -8-

Langkah 2: Menyeimbangkan Preflow (bagian kedua)

Vertek 4diseimbangkanyakni jumlah nilaimasuk 4 dankeluarnya juga 4

kemudian diblok,sehingga edge (4-t)dan (1-4) ditutup.

4

t1 2

3

s


8,[8]

5,[5] 4,[4]

5,[5]

1,[6]

4,[7] 4,[4]


13/14

Studi Kasus -9-

Langkah 2: Menyeimbangkan Preflow (bagian ketiga)

Pada bagian ketiga inimenyeimbangkanedge pada layer 2,dan didapatkan vertek1 dan vertek 3 yang

harus diseimbangkan

4

t1 2

3

s


5,[8]

4,[5] 4,[4]

5,[5]

1,[6]

4,[7] 4,[4]


14/14

Kompleksitas

Kompleksitas Algoritma Karzanov untukmaximum flow dalam layered network adalahO(V2) dan dikarenakan kemungkinan aka nada

n-1 proses push-rebalance atau prosesmenekan flow dan menyeimbangkannya makatotal kompleksitas waktunya adalah O(V3).

algoritma karzanov

Documents