W6

Wyk lad 7- sem letni 2012/2013

Algorytm maksymalnego przep lywu

• Dany graf zorientowany G = (N, A)

• liczby cij - przyporzadkowane lukom (i, j) tworza

przep lyw w sieci G = (N, A) jeśli: zasada zachowania przep lywu: przep lyw wychodzacy

z wez la jest równy przep lywowi wchodzacemu,

wszystko co wychodzi ze źród la dochodzi do ujścia

 v

gdy xi = s



cij −

cij =

−v gdy xi = t

 0

gdy x

j ∈Γ(xi )

xj∈Γ−(xi)

i 6= s, t

oraz cij ≤ qij (ograniczenie przepustowości)

• znaleźć cij - przep lyw w sieci taki, by przepustowość sieci

v =

cij =

cij

xj ∈Γ(s)

xj∈Γ−(t)

by la maksymalna

Algorytm Forda-Fulkersona

• ka żdy weze l może znajdować sie w jednym z

trzech stanów:

– jest mu przypisana etykieta i wez ly sasiednie

sa przebadane

– jest mu przypisana etykieta i conajmniej jeden weze l sasiedni jest nie jest przebadany

– nie jest mu przypisana etykieta

• etykieta dowolnego wez la x

i jest jednego z dwóch

typów:

– (+xj, δ), gdzie +xj oznacza, że przep lyw na luku (xj, xi) może być zwiekszony

– (−xj, δ), gdzie −xj oznacza, że przep lyw na luku (xi, xj) może być zmniejszony

– δ - maksymalna wielkość uzupe lniajacego

przep lywu

– w momencie poczatkowym wez ly nie posi-

adaja etykiet

• algorytm rozpoczyna dzia lanie od przep lywu poczatkowego c

ij = 0

Γ(xi) = {xj : (xi, xj) ∈ A}, Γ−1(xi) = {xj : (xj, xi) ∈ A}

• Krok 1: źród lo=weze l= x

1 uzyskuje etykiete֒

(+x1, ∞) i jest ’przebadany’, pozosta le wez ly

nie maja etykiet

• Krok 2: I. Zbiór wez lów

{xj ∈ Γ(xi), cij < qij, xj nie zaetykietowana}

xj uzyskuje etykiete (+x

i, δ(xj )),

δ(xj) = min{δ(xi), qij − cij}

{xj ∈ Γ(x1), c1j < q1j, xj nie zaetykietowana} = {x2, x4}

x2 otrzymuje etykiete֒

(+x1, min{δ(x1), 14 − c12}) = (+x1, min{∞, 14 − 0}) tzn (+x1, 14)

x4 otrzymuje etykiete֒

(+x1, min{δ(x1), 23 − c14}) = (+x1, min{∞, 23 − 0}) tzn (+x1, 23)

• Krok 2: II. Zbiór wez lów

{xj ∈ Γ−1(xi), cji > 0, xj niezaetykietowana}

xj uzyskuje etykiete (−x

i, δ(xj )), δ(xj ) = min{δ(xi), cji}

{xj ∈ Γ−1(x1), cj1 > 0, xj niezaetykietowana} = {∅}

czyli x1 zaetykietowana i przebadana, x2, x4 zaetykietowane i nieprzebadane, pozosta le wez ly

niezaetykietowane

• powtarzamy Krok 2 i rozpatrujemy x2

• Krok 2: I. Zbiór wez lów

{xj ∈ Γ(x2), c2j < q2j, xj niezaetykietowana} = {x3}

– x3 otrzymuje etykiete (+x

2, min{14, 10 − 0})

tzn (+x2, 10)

• Krok 2: II. Zbiór wez lów

{xj ∈ Γ−1(x2), cj2 > 0, xj niezaetykietowana} = {∅}

czyli x1 i x2 zaetykietowane i przebadane, x3 i x4 zaetykietowane i nieprzebadane, pozosta le wez ly sa niezaetykietowane

• powtarzamy Krok 2 i rozpatrujemy x3

• Krok 2: I. Zbiór wez lów

{xj ∈ Γ(x3), c3j < q3j, xj niezaetykietowana} = {x5, x8}

– x5 otrzymuje etykiete (+x

3, min{10, 12 − 0})

tzn (+x3, 10)

– x8 otrzymuje etykiete (+x

3, min{10, 18 − 0})

tzn (+x3, 10)

• Krok 2: II. Zbiór wez lów

{xj ∈ Γ−1(x3), cj3 > 0, xj niezaetykietowana} = {∅}

teraz wez ly x

1, x2, x3 zaetykietowane i prze-

badane, x4, x5, x8 zaetykietowane i nieprzebadane, pozosta le wez ly nie maja etykiet

• powtarzamy Krok 2 i rozpatrujemy x4

• Krok 2: I. Zbiór wez lów

{xj ∈ Γ(x4), c4j < q4j, xj niezaetykietowana} = {∅}

• Krok 2: II. Zbiór wez lów

{xj ∈ Γ−1(x4), cj4 > 0, xj niezaetykietowana} = {∅}

wez ly x

1, x2, x3, x4 zaetykietowane i przebadane, x5, x8 zaetykietowane i nieprzebadane, pozosta le wez ly nie maja etykiet

• powtarzamy Krok 2 i rozpatrujemy x5

• Krok 2: I. Zbiór wez lów

{xj ∈ Γ(x5), c5j < q5j, xj niezaetykietowana} = {x6, x7}

– x6 otrzymuje etykiete (+x

5, min{10, 25 − 0})

tzn (+x5, 10)

– x7 otrzymuje etykiete (+x

5, min{10, 4 − 0})

tzn (+x5, 4)

• Krok 2: II. Zbiór wez lów

{xj ∈ Γ−1(x5), cj5 > 0, xj niezaetykietowana} = {∅}

wez ly x

1, x2, x3, x4, x5 zaetykietowane i przebadane, x6, x7, x8 zaetykietowane i nieprzebadane, pozosta le wez ly nie maja etykiet

• powtarzamy Krok 2 i rozpatrujemy x6

• Krok 2: I. Zbiór wez lów

{xj ∈ Γ(x6), c6j < q6j, xj niezaetykietowana} = {∅}

• Krok 2: II. Zbiór wez lów

{xj ∈ Γ−1(x6), cj6 > 0, xj niezaetykietowana} = {∅}

wez ly x

1, x2, x3, x4, x5, x6 zaetykietowane i przebadane, x7, x8 zaetykietowane i nieprzebadane, pozosta le wez ly nie maja etykiet

• powtarzamy Krok 2 i rozpatrujemy x7

• Krok 2: I. Zbiór wez lów

{xj ∈ Γ(x7), c7j < q7j, xj niezaetykietowana} = {x9}

– x9 otrzymuje etykiete (+x

7, min{4, 15 − 0})

tzn (+x7, 4)

• Krok 2: II. Zbiór wez lów

{xj ∈ Γ−1(x7), cj7 > 0, xj niezaetykietowana} = {∅}

• Krok 3: I. weze l x

: przejście

9 uzyska l etykiete֒

do kroku 4

• Krok 3: II. jeśli weze l x

9 = t nie uzyska etyki-

ety i lista wez lów do przebadania jest pusta

to algorytm kończy dzia lanie z maksymalnym przep lywem c

• Uwaga: jeśli X0 zbiór wez lów zaetykietowanych

i ˜

X0 = N\X0 zbiór wez lów niezaetykietowanych

to X0 → ˜

X0 jest minimalnym przekrojem!!

• Krok 4: x = t i przejście do kroku 5

• Krok 5 ( wyznaczenie nowego polepszonego przep lywu): I. jeśli etykieta w weźle x jest

(+z, δ(x)) to zmiana przep lywu na luku (z, x) z c(z, x) na c(z, x) + δ(t)

• II. jeśli etykieta w weźle x jest (−z, δ(x)) to

zmiana przep lywu na luku (x, z) z c(x, z) na c(x, z) − δ(t)

• Krok 6:jeśli z = s to skasować wszystkie etyki-ety i przejść do kroku 1 z polepszonym przep lywem cij znalezionym w kroku 5; jeśli z 6= s to x = z i przejść do kroku 5

• krok 4-5:

x = x9 c7,9 := 0 + 4 = 4

x = x7 c5,7 := 4

x = x5 c3,5 := 4

x = x3 c2,3 := 4

x = x2 c1,2 := 4

• Iteracja II: powrót do kroku 1 z nowym przep lywem cij, etykieta x1 jest (+x1, ∞)

• krok 2 dla x1: I.

{xj ∈ Γ(x1), c1j < q1j, xj nie zaetykietowana} = {x2, x4}

x2 otrzymuje etykiete֒

(+x1, min{δ(x1), 14 − c12}) = (+x1, min{∞, 14 − 4}) tzn (+x1, 10)

x4 otrzymuje etykiete֒

(+x1, min{δ(x1), 23 − c14}) = (+x1, min{∞, 23 − 0}) tzn (+x1, 23)

• Krok 2: II.

{xj ∈ Γ−1(x1), cj1 > 0, xj niezaetykietowana} = {∅}

czyli x1 zaetykietowana i przebadana, x2, x4 zaetykietowane i nieprzebadane, pozosta le wez ly

niezaetykietowane

• powtarzamy Krok 2 i rozpatrujemy x2

• Krok 2: I.

{xj ∈ Γ(x2), c2j < q2j, xj niezaetykietowana} = {x3}

– x3 otrzymuje etykiete (+x

2, min{δ(x2, qij−cij } =

(+x2, min{10, 10 − 4}) tzn (+x2, 6)

• Krok 2: II.

{xj ∈ Γ−1(x2), cj2 > 0, xj niezaetykietowana} = {∅}

czyli x1 i x2 zaetykietowane i przebadane, x3 i x4 zaetykietowane i nieprzebadane, pozosta le wez ly sa niezaetykietowane

• powtarzamy Krok 2 i rozpatrujemy x3

• Krok 2: I.

{xj ∈ Γ(x3), c3j < q3j, xj niezaetykietowana} = {x5, x8}

– x5 otrzymuje etykiete (+x

3, min{δ(x3, qij−cij } =

(+x3, min{6, 12 − 4}) tzn (+x3, 6)

– x8 otrzymuje etykiete (+x

3, min{δ(x3, qij−cij } =

(+x3, min{6, 18 − 0}) tzn (+x3, 6)

• Krok 2: II.

{xj ∈ Γ−1(x3), cj3 > 0, xj niezaetykietowana} = {∅}

• x1, x2, x3, x4 zaetykietowane i przebadane, x5,x8

zaetykietowane

• powtarzamy Krok 2 i rozpatrujemy x5

• Krok 2: I.

{xj ∈ Γ(x5), c5j < q5j, xj niezaetykietowana} = {x6}

– x6 otrzymuje etykiete (+x

5, min{δ(x5, qij−cij } =

(+x5, min{6, 25 − 0}) tzn (+x5, 6)

• Krok 2: II.

{xj ∈ Γ−1(x5), cj3 > 0, xj niezaetykietowana} = {∅}

• x1, x2, x3, x4, x5 zaetykietowane i przebadane, x6, x8 zaetykietowane

• powtarzamy Krok 2 i rozpatrujemy x6

• Krok 2: I.

{xj ∈ Γ(x6), c6j < q6j, xj niezaetykietowana} = {x7}

– x7 otrzymuje etykiete (+x

6, min{δ(x6, qij−cij } =

(+x6, min{6, 7 − 0}) tzn (+x6, 6)

• Krok 2: II.

{xj ∈ Γ−1(x6), cj6 > 0, xj niezaetykietowana} = {∅}

• x1, x2, x3, x4, x5, x6 zaetykietowane i przebadane, x7, x8 zaetykietowane

• powtarzamy Krok 2 i rozpatrujemy x7

• Krok 2: I.

{xj ∈ Γ(x7), c7j < q7j, xj niezaetykietowana} = {x9}

– x9 otrzymuje etykiete (+x

7, min{δ(x7, qij−cij } =

(+x7, min{6, 15 − 4}) tzn (+x7, 6)

• Krok 2: II.

{xj ∈ Γ−1(x7), cj7 > 0, xj niezaetykietowana} = {∅}

• x1, x2, x3, x4, x5, x6, x7, x8 zaetykietowane i przebadane, x9 zaetykietowane

• przejście do kroku 4-5 nowe wielkości przep lywu x = x9 c7,9 := 4 + 6 = 10

x = x7 c6,7 := 0 + 6 = 6

x = 6

c5,6 := 0 + 6 = 6

x = x5 c3,5 := 4 + 6 = 10

x = x3 c2,3 := 4 + 6 = 10

x = x1 c1,2 := 4 + 6 = 10