Propädeutikum Diskrete Mathematik (MA 1503) - Flüsse und ...€¦ · Propädeutikum Diskrete...

Propädeutikum Diskrete Mathematik (MA 1503)Flüsse und der Algorithmus von Ford und Fulkerson

Tina Janne Schmidt

Technische Universität München

Wintersemester 2012/2013

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 1

Gerichtete Graphen

Definition gerichteter GraphG = (V,A) ist ein gerichteter Graph, wenn A ⊂ V × V (und nicht E ⊂

(V2

)).

Definiere N−(x) = {y ∈ V : (y, x) ∈ A} und N+(x) = {y ∈ V : (x, y) ∈ A}.

In A sind Tupel, deren Elemente eineReihenfolge haben, enthalten, in EMengen. D.h. eine Kante einesgerichteten Graphen hat einen Anfangs-und einen Endknoten, z.B. wird dieKante (a, b) durch einen Pfeil von a nachb dargestellt.In gerichteten Graphen ist (a, b) 6= (b, a);in ungerichteten Graphen ist{v, w} = {w, v}. In gerichteten Graphensind Kanten von einem Knoten zu sichselbst möglich, z.B. (a, a); inungerichteten Graphen gibt es keineKanten der Form {v, v}.

e

a

d

b

c

A = {(a, b), (a, e), (b, c), (b, e),(c, c), (c, d), (e, b), (e, d)}

N+(a) = {b, e}, N−(d) = {e, c}

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 2

Netzwerke und Flüsse

Definition NetzwerkEin Netzwerk ist ein Tupel N = (V,A, s, t, c), wobei (V,A, c) ein gerichteterGraph mit Kapazitätsfunktion c : A→ R≥0 ist, s ∈ V Quelle und t ∈ V Senkezwei ausgezeichnete Knoten sind.

Definition FlussSei N = (V,A, s, t, c) ein Netzwerk. Eine Abbildung f : A→ R≥0 heißt s, t-Fluss(flow) in N , wenn

1 Flusserhaltung∑y∈N−(x)

f((y, x)) =∑

y∈N+(x)

f((x, y)) ∀ x ∈ V \ {s, t}

2 Zulässigkeitf((x, y)) ≤ c((x, y)) ∀ (x, y) ∈ A.

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 3

Netzwerke und Flüsse

Definition NetzwerkEin Netzwerk ist ein Tupel N = (V,A, s, t, c), wobei (V,A, c) ein gerichteterGraph mit Kapazitätsfunktion c : A→ R≥0 ist, s ∈ V Quelle und t ∈ V Senkezwei ausgezeichnete Knoten sind.

Definition FlussSei N = (V,A, s, t, c) ein Netzwerk. Eine Abbildung f : A→ R≥0 heißt s, t-Fluss(flow) in N , wenn

1 Flusserhaltung∑y∈N−(x)

f((y, x)) =∑

y∈N+(x)

f((x, y)) ∀ x ∈ V \ {s, t}

2 Zulässigkeitf((x, y)) ≤ c((x, y)) ∀ (x, y) ∈ A.

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 3

Netzwerke und Flüsse - Beispiel

gerichteter Graph mit zwei ausgezeichneten Knoten

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

a b

c d

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

Netzwerke und Flüsse - Beispiel

gerichteter Graph mit zwei ausgezeichneten Knoten

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

a b

c d

1

4

2

3

2

4

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

Netzwerke und Flüsse - Beispiel

gerichteter Graph mit zwei ausgezeichneten Knoten

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

a b

c d

1

4

2

3

2

4

1

1/

3/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

Netzwerke und Flüsse - Beispiel

gerichteter Graph mit zwei ausgezeichneten Knoten

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

a b

c d

1

4

2

3

2

4

1

1/

3/1/

2/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

Netzwerke und Flüsse - Beispiel

gerichteter Graph mit zwei ausgezeichneten Knoten

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

a b

c d

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

Netzwerke und Flüsse - Beispiel

gerichteter Graph mit zwei ausgezeichneten Knoten

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

a b

c d

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

1/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

Netzwerke und Flüsse - Beispiel

gerichteter Graph mit zwei ausgezeichneten Knoten

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

a b

c d

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

3/

1/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 4

FlüsseVereinbarung:Schreibe f(x, y) statt f((x, y)) und c(x, y) statt c((x, y)).

Bemerkung:In Zukunft gehen wir davon aus, dass für alle x, y ∈ V gilt

f(x, y) > 0 ⇒ f(y, x) = 0.

a b c d

4

3

⇓

a b c d

1

0

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 5

FlüsseVereinbarung:Schreibe f(x, y) statt f((x, y)) und c(x, y) statt c((x, y)).

Bemerkung:In Zukunft gehen wir davon aus, dass für alle x, y ∈ V gilt

f(x, y) > 0 ⇒ f(y, x) = 0.

a b c d

4

3

⇓

a b c d

1

0

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 5

FlüsseVereinbarung:Schreibe f(x, y) statt f((x, y)) und c(x, y) statt c((x, y)).

Bemerkung:In Zukunft gehen wir davon aus, dass für alle x, y ∈ V gilt

f(x, y) > 0 ⇒ f(y, x) = 0.

a b c d

4

3

⇓

a b c d

1

0

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 5

Wert eines Flusses

Definition WertDer Wert eines Flusses f ist definiert als

val(f) =∑

y∈N+(s)

f(s, y) −∑

y∈N−(s)

f(y, s).

Der Fluss f hat maximalen Wert im Netzwerk N , wenn val(f) ≥ val(f ′) für alleFlüsse f ′ in N gilt.

s t

a b

c d

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

3/

1/

val(f) = (3 + 1)− 0 = 4

PropositionJedes Netzwerk besitzt einenFluss maximalen Werts.

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 6

Wert eines Flusses

Definition WertDer Wert eines Flusses f ist definiert als

val(f) =∑

y∈N+(s)

f(s, y) −∑

y∈N−(s)

f(y, s).

Der Fluss f hat maximalen Wert im Netzwerk N , wenn val(f) ≥ val(f ′) für alleFlüsse f ′ in N gilt.

s t

a b

c d

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

3/

1/

val(f) = (3 + 1)− 0 = 4

PropositionJedes Netzwerk besitzt einenFluss maximalen Werts.

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 6

Wert eines Flusses

Definition WertDer Wert eines Flusses f ist definiert als

val(f) =∑

y∈N+(s)

f(s, y) −∑

y∈N−(s)

f(y, s).

Der Fluss f hat maximalen Wert im Netzwerk N , wenn val(f) ≥ val(f ′) für alleFlüsse f ′ in N gilt.

s t

a b

c d

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

3/

1/

val(f) = (3 + 1)− 0 = 4

PropositionJedes Netzwerk besitzt einenFluss maximalen Werts.

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 6

Restnetzwerk

Definition RestnetzwerkSei N = (V,A, s, t, c) ein Netzwerk und f ein Fluss in N . Wir erweitern zunächstdie Kapazitätsfunktion zu c : V × V → R≥0 durch c(x, y) = 0 für alle (x, y) /∈ A.Das Restnetzwerk Nf = (V,Af , s, t, cf ) ist definiert durchAf = {(x, y) : cf (x, y) > 0} und

cf (x, y) =

c(x, y)− f(x, y), falls f(x, y) > 0c(x, y) + f(y, x), falls f(y, x) > 0c(x, y), sonst.

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 7

Restnetzwerk - Beispiel

cf (x, y) =

c(x, y)− f(x, y), falls f(x, y) > 0c(x, y) + f(y, x), falls f(y, x) > 0c(x, y), sonst.

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

x

y

5

5

1

55

5

2

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 8

Restnetzwerk - Beispiel

cf (x, y) =

c(x, y)− f(x, y), falls f(x, y) > 0c(x, y) + f(y, x), falls f(y, x) > 0c(x, y), sonst.

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

x

y

5

5

1

55

5

2

4/

0/

1/

3/0/

1/

2/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 8

Restnetzwerk - Beispiel

cf (x, y) =

c(x, y)− f(x, y), falls f(x, y) > 0c(x, y) + f(y, x), falls f(y, x) > 0c(x, y), sonst.

Kapazitätsobergrenze c : A→ R≥0

s, t- Fluss f : A→ R≥0

s t

x

y

5

5

1

55

5

2

4/

0/

1/

3/0/

1/

2/

Restkapazitäten cf : A→ R≥ 0

s, t- Fluss f : A→ R≥0

s t

x

y

1

4

6

28

4

1

2

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 8

Wege im Restnetzwerk

Definition gerichteter WegSei G = (V,A) ein gerichteter Graph. Dann heißt (v1, v2, v3, . . . , vl) gerichteterWeg in G falls (vi, vi+1) ∈ A für alle i ∈ [l − 1].

s t

x

y

1

4

6

28

4

1

2

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 9

Fluss erhöhen - BeispielFluss

s t

x

y

5

5

1

55

5

2

4/

0/

1/

3/0/

1/

2/

Restnetzwerk

s t

x

y

1

4

6

28

4

1

2

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 10

Fluss erhöhen - BeispielFluss

s t

x

y

5

5

1

55

5

2

4/

0/

1/

3/0/

1/

2/

Weg im Restnetzwerk

s t

x

y6

8

4

4/

4/

4/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 10

Fluss erhöhen - BeispielFluss

s t

x

y

5

5

1

55

5

2

4/

0/

1/

3/0/

1/

2/

Weg im Restnetzwerk

s t

x

y6

8

4

4/

4/

4/

erhöhter Fluss

s t

x

y

5

5

1

55

5

2

4/

4/

1/

3/4/

5/

2/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 10

Fluss erhöhen - BeispielFluss

s t

x

y

5

5

1

55

5

2

4/

0/

1/

3/0/

1/

2/

Weg im Restnetzwerk

s t

x

y6

8

4

4/

4/

4/

erhöhter Fluss

s t

x

y

5

5

1

55

5

2

4/

3/

0/

0/1/

5/

2/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 10

Fluss erhöhen

SatzWenn f ein Fluss in N und W ein gerichteter s, t-Weg im Restnetzwerk Nf ist,dann kann f entlang W zu einem Fluss f ′ erhöht werden mit

val(f ′) = val(f) + δ,

wobei 0 < δ = min{cf (e) :W benutzt Kante e}.

SatzSei f Fluss in N . Wenn es in Nf keinen gerichteten s, t-Weg mehr gibt, dann hatf maximalen Wert.

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 11

Fluss erhöhen

SatzWenn f ein Fluss in N und W ein gerichteter s, t-Weg im Restnetzwerk Nf ist,dann kann f entlang W zu einem Fluss f ′ erhöht werden mit

val(f ′) = val(f) + δ,

wobei 0 < δ = min{cf (e) :W benutzt Kante e}.

SatzSei f Fluss in N . Wenn es in Nf keinen gerichteten s, t-Weg mehr gibt, dann hatf maximalen Wert.

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 11

Algorithmus 1 : Algorithmus von Ford und FulkersonInput : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile Es gibt einen s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 12

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

ends Quelle, t Senke

s t

v w

x y

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

ends Quelle, t Senkec Kapazitätsobergrenze

s t

v w

x y

1

4

2

3

2

4

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

0/

0/

0/

0/

0/

0/

0/

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

0/

0/

0/

0/

0/

0/

0/

cf Restkapazität

s t

v w

x y

1

4

2

3

2

4

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

0/

0/

0/

0/

0/

0/

0/

cf Restkapazität

s t

v w

x y

1

4

2

3

2

4

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

0/

0/

0/

0/

0/

0/

0/

cf Restkapazität

s t

w

x2

2

2

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

0/

2/

0/

0/

2/

2/

0/

cf Restkapazität

s t

w

x2

2

2

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

0/

2/

0/

0/

2/

2/

0/

cf Restkapazität

s t

v w

x y

1

2 2

2

3

2 22

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

0/

2/

0/

0/

2/

2/

0/

cf Restkapazität

s t

v w

x y

1

2 2

2

3

2 22

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

0/

2/

0/

0/

2/

2/

0/

cf Restkapazität

s t

v w

x y

1

1

1

1

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

1/

2/

1/

1/

1/

2/

1/

cf Restkapazität

s t

v w

x y

1

1

1

1

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

1/

2/

1/

1/

1/

2/

1/

cf Restkapazität

s t

v w

x y

1

2 2

1

1

21

11 2

2

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

1/

2/

1/

1/

1/

2/

1/

cf Restkapazität

s t

v w

x y

1

2 2

1

1

21

11 2

2

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

1/

2/

1/

1/

1/

2/

1/

cf Restkapazität

s t

w

x1

11

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

3/

1/

cf Restkapazität

s t

w

x1

11

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

3/

1/

cf Restkapazität

s t

v w

x y

1

1 3

1

1

21

2 13

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Fluss

s t

v w

x y

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

3/

1/

cf Restkapazität

s t

v w

x y

1

1 3

1

1

21

2 13

1

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13

Input : Netzwerk N = (V,A, s, t, c)Output : Fluss f mit maximalem Wert

in N

for (x, y) ∈ A do1

f(x, y)← 0;2

endwhile ∃ s, t-Weg W in Nf do3

Erhöhe f entlang von W ;4

end

s Quelle, t Senkec Kapazitätsobergrenzef Flussval(f) = 1 + 3− 0 = 4

s t

v w

x y

1

4

2

3

2

4

1

1/

3/

1/

1/

2/

3/

1/

cf Restkapazität

s t

v w

x y

1

1 3

1

1

21

2 13

1

val(f) = 1 + 3− 0 = 4

Tina Janne Schmidt (TU München) Diskrete Mathematik WS 12/13 Seite 13