Flow Networks

Flow Networks 05 — 08 — 2009

¨ ren Wellho ¨ fer So

Introduction Definitions Problems / Solutions References

Table of Contents

1 Introduction 2 Definitions 3 Problems / Solutions 4 References

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Flow network

Abstract • Directed graph • Source s and sink t

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Flow network

a

Abstract • Directed graph • Source s and sink t

s

t

• Edges have capacity

b

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Flow network

a

Abstract

1

5

• Directed graph • Source s and sink t

s

3

t

• Edges have capacity • Flow: s → t

2

5 b

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Flow network

a

Abstract

1

5

• Directed graph • Source s and sink t

s

3

t

• Edges have capacity • Flow: s → t

2

5 b

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Flow network

a

Abstract

1/1

3/5

• Directed graph • Source s and sink t

s

2/ 3

t

• Edges have capacity • Flow: s → t

2/2

4/ 5 b

• Flow from s

equals flow into t

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Flow network

a

Abstract

1/1

3/5

• Directed graph • Source s and sink t

s

2/ 3

t

• Edges have capacity • Flow: s → t

2/2

4/ 5 b

• Flow from s

equals flow into t

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Formal definition Nf = G (V , E ) V

u, v ∈ V

S¨ oren Wellh¨ ofer

Set of vertices (nodes)

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Formal definition Nf = G (V , E ) V

u, v ∈ V

(u, v ) ∈ E

Set of vertices (nodes) Set of edges (arcs)

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Formal definition Nf = G (V , E ) V

u, v ∈ V

Set of vertices (nodes)

(u, v ) ∈ E

Set of edges (arcs)

c(u, v )

Real-valued edge capacity

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Formal definition Nf = G (V , E ) V

u, v ∈ V

Set of vertices (nodes)

(u, v ) ∈ E

Set of edges (arcs)

c(u, v )

Real-valued edge capacity

f (u, v )

Net-flow from u to v

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Formal definition Nf = G (V , E ) V

u, v ∈ V

Set of vertices (nodes)

(u, v ) ∈ E

Set of edges (arcs)

c(u, v )

Real-valued edge capacity

f (u, v )

Net-flow from u to v

s, t ∈ V

Source and sink

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Formal definition Nf = G (V , E ) V

u, v ∈ V

Set of vertices (nodes)

(u, v ) ∈ E

Set of edges (arcs)

c(u, v )

Real-valued edge capacity

f (u, v )

Net-flow from u to v

s, t ∈ V

Source and sink

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network Properties Capacity constraints

0 ≤ f (u, v ) ≤ c(u, v )

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network Properties Capacity constraints

0 ≤ f (u, v ) ≤ c(u, v ) Skew symmetry

f (u, v ) = −f (v , u)

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network Properties Capacity constraints

0 ≤ f (u, v ) ≤ c(u, v ) Skew symmetry

f (u, v ) = −f (v , u)

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Properties Flow conservation

P

u∈V

f (u, w ) = 0,

if u 6= s ∧ u 6= t

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Properties Flow conservation

P

u∈V

f (u, w ) = 0,

if u 6= s ∧ u 6= t

Net flow to node = 0

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Properties Flow conservation

P

u∈V

f (u, w ) = 0,

if u 6= s ∧ u 6= t

Net flow to node = 0

S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Properties Flow conservation

P

u∈V

f (u, w ) = 0,

if u 6= s ∧ u 6= t

Net flow to node = 0

3

1 n 2

S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Properties Flow conservation

P

u∈V

f (u, w ) = 0,

if u 6= s ∧ u 6= t

Net flow to node = 0

3

-1 n -2

S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Properties Flow conservation

P

u∈V

f (u, w ) = 0,

if u 6= s ∧ u 6= t

Net flow to node = 0

-1

3

P

n

=0

S¨ oren Wellh¨ ofer

-2

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Capacity of a Path a 1

5 s

t

3 2

5 b p = (s, a, b, t)

S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Capacity of a Path a 1

5 s

t

3 2

5 b p = (s, a, b, t)

c(p) = min(c(s, a), c(a, b), c(b, t))

S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Capacity of a Path a 1

5 s

t

3 2

5 b p = (s, a, b, t)

c(p) = min(c(s, a), c(a, b), c(b, t))

S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Capacity of a Path a 1

5 s

t

3 2

5 b p = (s, a, b, t)

c(p) = min(c(s, a), c(a, b), c(b, t)) c(p) = min(5, 3, 5) S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Capacity of a Path a 1

5 s

t

3 2

5 b p = (s, a, b, t)

c(p) = min(c(s, a), c(a, b), c(b, t)) c(p) = min(5, 3, 5) = 3 S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Capacity of a Path a 1

5 s

t

3 2

5 b p = (s, a, b, t)

c(p) = min(c(s, a), c(a, b), c(b, t)) c(p) = min(5, 3, 5) = 3 S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Residual Network Nr = Gr (V , Er )

S¨ oren Wellh¨ ofer

Er ... residual edges

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

... residual edge capacity

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

... residual edge capacity

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

... residual edge capacity

a 1/1

3/5 2/3

s 2/2

t 4/5

b S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

... residual edge capacity

a 1/1

3/5 -3 2/3

s 2/2

t 4/5

b S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

... residual edge capacity

a 1/1

3/5 -3

-1 2/3 -2

s -2 2/2

t -4 4/5

b S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

... residual edge capacity

a 0

2 3 s

1 1

3 4

2 0

t 1

b S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

... residual edge capacity

a 0

2 3 s

1

3

t

pa = (s, a, b, t)

4

2 0

Augmenting path:

1

1 b S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

... residual edge capacity

a 0

2 3 s

1

3

t 4

2 0

Augmenting path:

1

pa = (s, a, b, t) cr (pa ) = min(2, 1, 1) = 1

1 b S¨ oren Wellh¨ ofer

Flow Networks

Formal definition Network Properties Path capacity Residual network Network cuts

Introduction Definitions Problems / Solutions References

Residual Network Nr = Gr (V , Er )

Er ... residual edges

cr (u, v ) = c(u, v ) − f (u, v )

... residual edge capacity

a 0

2 3 s

1

3

t 4

2 0

Augmenting path:

1

pa = (s, a, b, t) cr (pa ) = min(2, 1, 1) = 1

1 b S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network cut Partition of G into two sets S and T

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network cut Partition of G into two sets S and T

S¨ oren Wellh¨ ofer

Flow Networks

s ∈S ∧t ∈T

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network cut Partition of G into two sets S and T

S¨ oren Wellh¨ ofer

Flow Networks

s ∈S ∧t ∈T

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network cut Partition of G into two sets S and T

a 1

5 s

3

t

2

5 b S¨ oren Wellh¨ ofer

Flow Networks

s ∈S ∧t ∈T

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network cut Partition of G into two sets S and T

a 1

5 s

3

t

2

5 b S¨ oren Wellh¨ ofer

Flow Networks

s ∈S ∧t ∈T

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network cut Partition of G into two sets S and T

a 1

5 s

3

t

S 2

5 b S¨ oren Wellh¨ ofer

Flow Networks

s ∈S ∧t ∈T

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network cut s ∈S ∧t ∈T

Partition of G into two sets S and T

a

s

3 S 2

Cut Capacity: P c(S, T ) = u∈S∧v ∈T c(u, v )

1

5

t T =G −S 5 b S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network cut s ∈S ∧t ∈T

Partition of G into two sets S and T

a

s

3 S 2

Cut Capacity: P c(S, T ) = u∈S∧v ∈T c(u, v )

1

5

t T =G −S 5 b S¨ oren Wellh¨ ofer

c(S, T ) = 5 + 5 = 10

Flow Networks

Introduction Definitions Problems / Solutions References

Formal definition Network Properties Path capacity Residual network Network cuts

Network cut s ∈S ∧t ∈T

Partition of G into two sets S and T

a

s

3 S 2

Cut Capacity: P c(S, T ) = u∈S∧v ∈T c(u, v )

1

5

t T =G −S 5 b S¨ oren Wellh¨ ofer

c(S, T ) = 5 + 5 = 10

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Maximum Flow Flow at max if no augmenting paths in G

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Maximum Flow Flow at max if no augmenting paths in G

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Maximum Flow Flow at max if no augmenting paths in G

a 1/1

3/5 s

2/3 2/2

t 4/5

b S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Maximum Flow Flow at max if no augmenting paths in G

a 0

2 1

3 s

1

4

2 0

S¨ oren Wellh¨ ofer

t

3 1 b Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Maximum Flow Flow at max if no augmenting paths in G

a 0

2 1

3 s

1

4

2 0

S¨ oren Wellh¨ ofer

t

3 1 b Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Maximum Flow Flow at max if no augmenting paths in G

a 0

1 1

3 s

0

4

2 0

S¨ oren Wellh¨ ofer

t

3 0 b Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Maximum Flow Flow at max if no augmenting paths in G

a 1/1

4/5 s

3/3

t

2/2

5/5 b

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm • 1956, L. Ford and D. Fulkerson

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm • 1956, L. Ford and D. Fulkerson • Compute maximum flow of Nf in O(|E | · f )

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm • 1956, L. Ford and D. Fulkerson • Compute maximum flow of Nf in O(|E | · f ) • Might not find max flow • Termination not guaranteed

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm • 1956, L. Ford and D. Fulkerson • Compute maximum flow of Nf in O(|E | · f ) • Might not find max flow • Termination not guaranteed

Idea:

While there exist augmenting paths, increase flow along those.

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm • 1956, L. Ford and D. Fulkerson • Compute maximum flow of Nf in O(|E | · f ) • Might not find max flow • Termination not guaranteed

Idea:

While there exist augmenting paths, increase flow along those.

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation

while

∃pa ∈ Gr

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation

while

∃pa ∈ Gr

S¨ oren Wellh¨ ofer

(there exist augmenting paths)

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation

while ∃pa ∈ Gr · compute cr (pa )

S¨ oren Wellh¨ ofer

(there exist augmenting paths)

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation

while ∃pa ∈ Gr · compute cr (pa ) · ∀(u, v ) ∈ pa

S¨ oren Wellh¨ ofer

(there exist augmenting paths)

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation (there exist augmenting paths) while ∃pa ∈ Gr · compute cr (pa ) · ∀(u, v ) ∈ pa f (u, v ) += cr (pa )

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation (there exist augmenting paths) while ∃pa ∈ Gr · compute cr (pa ) · ∀(u, v ) ∈ pa (forward arc) f (u, v ) += cr (pa )

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation (there exist augmenting paths) while ∃pa ∈ Gr · compute cr (pa ) · ∀(u, v ) ∈ pa (forward arc) f (u, v ) += cr (pa ) f (v , u) -= cr (pa )

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation (there exist augmenting paths) while ∃pa ∈ Gr · compute cr (pa ) · ∀(u, v ) ∈ pa (forward arc) f (u, v ) += cr (pa ) (backward arc) f (v , u) -= cr (pa )

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Initialization

∀(u, v ) ∈ E → f (u, v ) = 0 Augmentation (there exist augmenting paths) while ∃pa ∈ Gr · compute cr (pa ) · ∀(u, v ) ∈ pa (forward arc) f (u, v ) += cr (pa ) (backward arc) f (v , u) -= cr (pa )

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Demo a 0/1

0/5 s

0/3

t

0/2

0/5 b

f (s, t) =

P

u∈V

f (s, u) =

P

=0 S¨ oren Wellh¨ ofer

Flow Networks

u∈V

f (u, t)

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Demo a 1/1

1/5 s

0/3

t

0/2

0/5 b

f (s, t) =

P

u∈V

f (s, u) =

P

=1 S¨ oren Wellh¨ ofer

Flow Networks

u∈V

f (u, t)

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Demo a 1/1

4/5 s

3/3

t

0/2

3/5 b

f (s, t) =

P

u∈V

f (s, u) =

P

=4 S¨ oren Wellh¨ ofer

Flow Networks

u∈V

f (u, t)

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Demo a 1/1

4/5 s

3/3

t

2/2

5/5 b

f (s, t) =

P

u∈V

f (s, u) =

P

=6 S¨ oren Wellh¨ ofer

Flow Networks

u∈V

f (u, t)

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm Demo a 1/1

4/5 3/3

s

t

2/2

5/5 b

f (s, t) =

P

u∈V

f (s, u) =

P

fmax (s, t) = 6 S¨ oren Wellh¨ ofer

Flow Networks

u∈V

f (u, t)

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Minimum-cut Maximum-flow theorem • Minimum cut: cut of smallest capacity c(S, T ) = min

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Minimum-cut Maximum-flow theorem • Minimum cut: cut of smallest capacity c(S, T ) = min

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Minimum-cut Maximum-flow theorem • Minimum cut: cut of smallest capacity c(S, T ) = min

a 1

5 s

t

3 2

5 b

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Minimum-cut Maximum-flow theorem • Minimum cut: cut of smallest capacity c(S, T ) = min

a 1

5 s

t

3 2

5 b

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Minimum-cut Maximum-flow theorem • Minimum cut: cut of smallest capacity c(S, T ) = min

a 1

5 s

t

3 2

5 b

cmin (S, T ) = 5 + 1 = 6 S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Minimum-cut Maximum-flow theorem • Minimum cut: cut of smallest capacity c(S, T ) = min

a 1/1

4/5 s

t

3/3 2/2 b

5/5

fmax (s, t) = cmin (S, T ) = 6 S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Summary • Directed graph, capacities, flow • Residual network, network cuts

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Summary • Directed graph, capacities, flow • Residual network, network cuts • Maximum flow, Ford-Fulkerson algorithm,

Min-cut Max-flow theorem

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Summary • Directed graph, capacities, flow • Residual network, network cuts • Maximum flow, Ford-Fulkerson algorithm,

Min-cut Max-flow theorem

Practical applications • Pipe networks

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Summary • Directed graph, capacities, flow • Residual network, network cuts • Maximum flow, Ford-Fulkerson algorithm,

Min-cut Max-flow theorem

Practical applications • Pipe networks • Traffic flow modeling

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Summary • Directed graph, capacities, flow • Residual network, network cuts • Maximum flow, Ford-Fulkerson algorithm,

Min-cut Max-flow theorem

Practical applications • Pipe networks • Traffic flow modeling • Commodity/Market flow

S¨ oren Wellh¨ ofer

Flow Networks

Introduction Definitions Problems / Solutions References

Maximum Flow Ford-Fulkerson Algorithm

Summary • Directed graph, capacities, flow • Residual network, network cuts • Maximum flow, Ford-Fulkerson algorithm,

Min-cut Max-flow theorem

Practical applications • Pipe networks • Traffic flow modeling • Commodity/Market flow

S¨ oren Wellh¨ ofer

Flow Networks

Graph Theory Bondy, Murty Graduate Texts in Mathematics, Springer, 2008 Graphs, Flows, and the Ford-Fulkerson Algorithm Vince Vatter, 2004 Network flows Kevin Weyn, 2005 A simple Min-cut algorithm Mechthild Stoer, Frank Wagner Freie Universit¨at Berlin, 1997 Flow network, Ford-Fulkerson algorithm, Maximum-flow minimum-cut theorem Wikipedia, [http://en.wikipedia.org/wiki], 2009

Introduction Definitions Problems / Solutions References

Flow Networks 05 — 08 — 2009

¨ ren Wellho ¨ fer So

S¨ oren Wellh¨ ofer

Flow Networks