# CS代考程序代写 data mining ER algorithm Lecture 8 –

Lecture 8 –

Flow networks I

The University of Sydney

Page 1

General techniques in this course

– Greedy algorithms [Lecture 3]

– Divide & Conquer algorithms [Lectures 4 and 5]

– Dynamic programming algorithms [Lectures 6 and 7] – Network flow algorithms [today and 2 May]

– Theory [today]

– Applications [2 May]

– NP and NP-completeness – Coping with hardness

The University of Sydney

Page 2

Soviet Rail Network, 1955

The University of Sydney

Page 4

Reference: On the history of the transportation and maximum flow problems. Alexander Schrijver in Math Programming, 91: 3, 2002.

Maximum Flow and Minimum Cut

– Max flow and min cut.

– Two very rich algorithmic problems.

– Cornerstone problems in combinatorial optimization.

– Mathematical duality.

– Nontrivial applications / reductions.

– Data mining.

– Open-pit mining.

– Project selection.

– Airline scheduling.

– Bipartite matching.

– Baseball elimination.

– Image segmentation.

– Network connectivity.

– Network reliability.

– Distributed computing.

– Egalitarian stable matching.

– Securityofstatisticaldata.

– Network intrusion detection.

– Multi-camera scene reconstruction.

– Manymanymore…

The University of Sydney

Page 5

Flow network

– Abstraction for material flowing through the edges.

– G = (V, E): a directed graph with no parallel edges.

– Two distinguished nodes: s = source, t = sink.

– The source has no incoming edges and the sink has no outgoing edges.

– c(e) = capacity of edge e. 295

10

sources 5 3 8 6

4

15 15

10

10 tsink 10

Page 6

capacity

The University of Sydney

15

46

15 4 30 7

Flows

– Definition: An s-t flow is a function that satisfies: – For each e Î E: 0 £ f(e) £ c(e)

– We say e is saturated if f(e) = c(e)

– For each v Î V – {s, t}: å f(e) =

(capacity) (conservation)

e in to v

– Definition: The value of a flow f is:

å f(e) e out of v

v( f ) = 2 9 5

å f (e) . e out of s

0

10

4

0

10

capacity 10 flow 4

0

15 15 0

44

s 5 3 8 6 10 t

04

15

0

40 6 150 0

4 30 7

The University of Sydney

0

Value =P4age 7

0

Flows

– Definition: An s-t flow is a function that satisfies: – For each e Î E: 0 £ f(e) £ c(e)

– We say e is saturated if f(e) = c(e)

– For each v Î V – {s, t}: å f(e) =

(capacity) (conservation)

e in to v

– Definition: The value of a flow f is:

å f(e) e out of v

v( f ) = 2 9 5

å f (e) . e out of s

6

10

8

6

capacity 10

15 15 0 0

44

s 5 3 8 6 10 t

flow 10 38

15

11

40 6 150 1

4 30 7

10

10

The University of Sydney

11

Value = 2Pa4ge 8

Maximum Flow Problem

– Max flow problem. Find s-t flow of maximum value.

– Question: How to characterize optimal solution?

– DP and D&C uses a recurrence equation. Not known if max flows admit such a recurrence.

2 9 5

9

capacity 10

15 15 0 1

9

10

9

40

s 5 3 8 6 10 t

flow 10 48

15

14

40 6 150 4

4 30 7

10

10

The University of Sydney

14

Value = 2Pa8ge 9

Characterizing Max Flow

f is a max flow if:

– f saturates every edge OR

– f saturates every edge out of s

2 9 5

9

capacity 10

15 15 0 1

9

10

9

40

s 5 3 8 6 10 t

flow 10 48

15

14

40 6 150 4

4 30 7

10

10

The University of Sydney

14

Value =P2ag8e 10

Cuts

Definitions:

– Ans-tcutisapartition(A,B)ofVwithsÎAandtÎB.

– The capacity of a cut (A, B) is: cap(A, B) = 295

å c(e) e out of A

10

4

15 15

10

s 5 3 8 6 10 t A

15

46

10

15 4 30 7

Capacity = 10 + 5 + 15

The University of Sydney

= 30

Page 11

Cuts

Definitions:

– Ans-tcutisapartition(A,B)ofVwithsÎAandtÎB.

– The capacity of a cut (A, B) is: cap(A, B) = 2 9 5

10

å c(e) e out of A

15 15

s 5 3 8 6 10 t

4

10

A

The University of Sydney

15 4 30 7

15

46

10

Capacity = 9 + 15 + 8 + 30

= 62

Page 12

Minimum Cut Problem

Min s-t cut problem:

Find an s-t cut of minimum capacity.

– Question: How to characterize optimal solution?

– Not known if min cuts admit a DP-style recurrence.

2 9 5

10

4

15

s 5 3 8 6 10 t

15

10

A

The University of Sydney

15

46

4 30 7

10

15

Capacity = 10 + 8 + 10

= 28

Page 13

Max-Flow = Min-Cut

1. Max-Flow ≤ Min-Cut

2. AlgorithmforMax-Flowfindsaflowfandacut(A,B)such that v(f) = cap(A,B)

2 9 5

9

capacity 10

15 15 0 1

9

10

9

40

s 5 3 8 6 10 t

flow 10 48

15

14

40 6 150 4

4 30 7

10

10

The University of Sydney

14

Value =P2ag8e 14

Notation

– Given a vertex u, define fout(u) = total flow on edges leaving u

– Given a vertex subset S, define fout(S) = total flow on edges leaving S

– Similarly, define fin(u) and fin(S) on edges entering u and S, resp.

– Can rewrite v(f) = fout(s) and fin(u) = fout(u) for v not s,t

6

2 9 5

10

10

44

0

15 15 0

6

10

388

s 5 3 8 6 10 t

The University of Sydney

4 30 7

A

1

40 6 150

11

10

10

15

11

Value = 10+3+11 = 24Page 15

Flows and Cuts

Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount

leaving s.

v(f) = fout(A) – fin(A) 6

2 9 5

10

10

44

0

15 15 0

6

10

388

s 5 3 8 6 10 t

The University of Sydney

4 30 7

A

1

40 6 150

11

10

10

15

11

Value = 10+3+11 = 24Page 18

Flows and Cuts

Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount

leaving s.

v(f) = fout(A) – fin(A) 6

2 9 5

10

10

44

0

15 15 0

6

10

388

s 5 3 8 6 10 t

A

1

40 6 150

11

10

10

15

11

Value = 6 + 0 + 8 – 1 + 11 = 24 Page 19

The University of Sydney

4 30 7

Flows and Cuts

Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount

leaving s.

v(f) = fout(A) – fin(A) 6

2 9 5

10

10

44

0

15 15 0

6

10

388

s 5 3 8 6 10 t

A

1

40 6 150

11

10

10

15

11

Value = 10 – 4 + 8 – 0 + 10 = 24 Page 20

The University of Sydney

4 30 7

Flowvaluelemmacziven flow f

f

f 174

finfu FOH

f sforetCA Pt by induction on IAI

Inductive case A I Let u c Aks

The University of Sydney

Page 22

Equiv

WTS

f

want

f UtfAl u3 fin fat A fin A

fat CA fo’t’CAl a3

Alfie

finCA finCA

cut A B fatCA fin A

fztfz

re

f fout EB finS3

s

to

A 1243

O

Inc in fin 4 11

Increase in fo

tz f Flow conservation

fg fg

Flows and Cuts

– Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut, i.e.

v(f) ≤ cap(A, B)

Cut capacity = 30 Þ Flow value £ 30 2 9 5

10

4

15 15

10

s 5 3 8 6 10 t A

15

46

10

15 4 30 7

The University of Sydney

Capacity = P3ag0e 23

Flows and Cuts

– Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut, i.e.

v(f) ≤ cap(A, B)

Cut capacity = 28 Þ Flow value £ 28 2 9 5

10

4

15 15

10

s 5 3 8 6 10 t A

15 4 30 7

15

46

10

The University of Sydney

Capacity = P2ag8e 24

Flows and Cuts

Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut, i.e.,

Proof:

v(f) = ≤ =

≤ =

fout(A) – fin(A)

fout(A)

S f(e) e out

of A

Sc(e) e out

of A c(A,B)

A

8

B

t

v(f) £ cap(A, B).

4

s

7

6

The University of Sydney

Page 25

Certificate of Optimality

Corollary: Let f be any flow, and let (A, B) be any cut.

If v(f) = cap(A, B) then f is a max flow and (A, B) is a min cut.

Value of flow = 28

Cut capacity = 28 Þ Flow value £ 28

9

2 9 5

10

10

1

15 15 0

9

10

40 489

s 5 3 8 6 10 t

4

A 15 40 6 150

10

10

The University of Sydney

4 30 7

Page 26

14

14

Summary (so far)

The University of Sydney

Page 27

1. Max flow problem

2. Min cut problem

3. Theorem: Max flow ≤ Min cut

Towards a Max Flow Algorithm

Greedy algorithm.

– Startwithf(e)=0foralledgeeÎE.

– Find an s-t path P where each edge has f(e) < c(e).
– Augment flow along path P.
– Repeat until you get stuck. 1
00
20 10
s 300 t
10 20
00
Flow value = 0
The University of Sydney
Page 28
2
Towards a Max Flow Algorithm
Greedy algorithm.
– Startwithf(e)=0foralledgeeÎE.
– Find an s-t path P where each edge has f(e) < c(e).
– Augment as much flow as possible along path P.
– Repeat until you get stuck. 1
s s
3 0 X0 2 0
t t
20 X0
20
0
10
10
0
20
X0 2 0
Flow value = 20
The University of Sydney
Page 29
2
Towards a Max Flow Algorithm
Augmenting greedy flow to get optimal flow
11
20 0 20 10
20 10 20 10
s 3020 t s 3010 t
10 20 10 20
0 20 10 20
22
TgherUeniverdsityof=Syd2ne0y opt = 30 Page 30
Towards a Max Flow Algorithm
Augmenting greedy flow to get optimal flow – Send 10 units on (s,2) edge
11
20 0 20 10
20 10 20 10
s 3020 t s 3010 t
10 20 10 20
10 20 10 20
22
TgherUeniverdsityof=Syd2ne0y opt = 30 Page 31
Towards a Max Flow Algorithm
Augmenting greedy flow to get optimal flow
– Send 10 units on (s,2) edge
– “Undo” 10 units on (1,2) edge to preserve conservation at vertex 2
11
20 0 20 10
20 10 20 10
s 3010 t s 3010 t
10 20 10 20
10 20 10 20
22
TgherUeniverdsityof=Syd2ne0y opt = 30 Page 32
Towards a Max Flow Algorithm
Augmenting greedy flow to get optimal flow – Send 10 units on (s,2) edge
– “Undo” 10 units on (1,2) edge to preserve conservation at vertex 2 – Send 10 units on (1,t) edge to preserve conservation at vertex 1
11
20 10 20 10
20 10 20 10
s 3010 t s 3010 t
10 20 10 20
10 20 10 20
22
TgherUeniverdsityof=Syd2ne0y opt = 30 Page 33
Build a Residual Graph Gf = (V, Ef )
– Original edge: e = (u, v) Î E. – Flow f(e), capacity c(e).
– Residual edge.
– "Undo" flow sent.
– e=(u,v)andeR =(v,u). – Residual capacity:
cf(e)=ìíc(e)-f(e) ifeÎE îf(e) if eR ÎE
capacity
u 17 v
6
flow
residual capacity v
residual capacity
u 11 6
– Residual graph: Gf = (V, Ef ).
– Residual edges with positive residual capacity. – Ef ={e:f(e)

– Max flow of Gf = (Max flow of G) – v(f) (Exercise) The University of Sydney

Page 34

Build a Residual Graph Gf = (V, Ef )

– The residual capacity of an edge in Gf tells us how much flow we can send, given the current flow.

residual capacity

u 11 v

6

residual capacity

The University of Sydney

Page 35

Augmenting Path Algorithm

Notations:

P = a simple s-t path in Gf

bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.

u 20

G

s

10

10 30

t 20

v

u 10 Gf 20

s 30 10

v

t 20

The University of Sydney

Page 36

Augmenting Path Algorithm

Notations:

P = a simple s-t path in Gf

bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.

0/10

s

v

u 20/30

G

20/20 s

0/10

t 20/20

v

u Gf

t

The University of Sydney

Page 37

Augmenting Path Algorithm

Notations:

P = a simple s-t path in Gf

bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.

u 20/30

20/20 s

0/10

v

0/10

G

t 20/20

u Gf 10

20

s 10

v

20 10

t 20

The University of Sydney

Page 38

Augmenting Path Algorithm

Notations:

P = a simple s-t path in Gf

bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.

u 20/30

G

t 20/20

u Gf 10

Augment(f,P) {

b ¬ bottleneck(P,f) foreach e =(u,v) Î P {

if e is a forward edge then

increase f(e) in G by b

else (e is a backward edge)

decrease f(e) in G by b

}

return f }

20/20 s

0/10

v

0/10

20

s 10

v bottleneck

20 10

t 20

The University of Sydney

Page 39

Augmenting Path Algorithm

Notations:

P = a simple s-t path in Gf

bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.

u s 10/30

G

Augment(f,P) {

b ¬ bottleneck(P,f) foreach e =(u,v) Î P {

if e is a forward edge then

increase f(e) in G by b

else (e is a backward edge)

decrease f(e) in G by b

}

return f }

20/20

t

10/10

10/10

v

u Gf 10

20/20

20

s 10

v

20 10

t 20

The University of Sydney

Page 40

Augment(f,P) gives a new flow f’ in G

Augmenting Path Algorithm

Ford-Fulkerson(G,s,t) { foreach e Î E

f(e) ¬ 0

Gf ¬ residual graph

while (there exists augmenting path P in Gf){ f ¬ Augment(f,P)

update Gf }

return f }

Augment(f,P) {

b ¬ bottleneck(P,f) foreach e =(u,v) Î P {

if e is a forward edge then

increase f(e) in G by b

else (e is a backward edge)

decrease f(e) in G by b

}

return f }

Page 41

The University of Sydney

Ford-Fulkerson Algorithm

244

10 2 8 6 10

s 10 3 9 5 10 t

G:

capacity

The University of Sydney Page 42

Ford-Fulkerson Algorithm

0

2 4 4

flow

capacity

G:

s 10 3 9 5 10 t

0 10208 6010

00 000

The University of Sydney

Page 43

Flow value = 0

Ford-Fulkerson Algorithm

0

2 4 4

flow

capacity

G:

s 10 3 9 5 10 t

0 10208 6010

8X0 0 X8

0 0 8X0

Flow value = 0

244

residual capacity 10

Gf:

10

2

86

s 10 3 9 5 10 t

The University of Sydney

Page 44

Ford-Fulkerson Algorithm

G:

0

2 4 4

1 0 X8 8

10208 6010

s 10 3 X 5 t 9 10

X

0 2 02 10X8

0

2 4 4

Flow value = 8

Gf:

8

2

86

10

2 s 10 3

9 5 2 t 8

The University of Sydney

Page 45

Ford-Fulkerson Algorithm

G:

0

2 4 4

X0 6 1022 X10

X06

s 10 3 X 5

2 4 4

10 2 8 6 10

10 8

860

28

9 10

t

Flow value = 10

6 10

Gf:

s 10 3 7 5 10 t 2

The University of Sydney

Page 46

Ford-Fulkerson Algorithm

2 4 4

02 X

G:

s 10 3 9 5 10 t

X6 8 10 22 8 66 10

10 8 X0

X68 8 10

Flow value = 16

Gf:

2 4 4

10 2 8 6 4

6

s 4 3 1 5 10 t

The University of Sydney

Page 47

6

8

Ford-Fulkerson Algorithm

G:

23 X

2 4 4

X8 9 10 20 8 66 10

10 87 X

X8 9 8 9 1 0 s 10 3 X 5

t

Flow value = 18

8

9 10

Gf:

2

2 2 4

10 2 8 6 2

s 2 3 1 5 10 t

The University of Sydney

Page 48

8

8

Ford-Fulkerson Algorithm

3

2 4 4

G:

s 10 3 9 5 10 t

9 10 20 8 66 10

10 7

9 9 10

3

2 1 4

Gf: 1 9

Flow value = 19

10 2 7

6 1

s 1 3 9 5 10 t 9

The University of Sydney

Page 49

Ford-Fulkerson Algorithm

3

2 4 4

G:

s 10 3 9 5 10 t

9 10 20 8 66 10

10 7

9 9 10

Cut capacity = 19 Flow value = 19

3

2 1 4

Gf: 1 9

10 2 7

6 1

s 1 3 9 5 10 t 9

The University of Sydney

Page 50

Augmenting Path Algorithm

Ford-Fulkerson(G,s,t) { foreach e Î E

f(e) ¬ 0

Gf ¬ residual graph

while (there exists augmenting path P in Gf){ f ¬ Augment(f,P)

update Gf }

return f }

Augment(f,P) {

b ¬ bottleneck(P,f) foreach e =(u,v) Î P {

if e is a forward edge then

increase f(e) in G by b

else (e is a backward edge)

decrease f(e) in G by b

}

return f }

Page 51

The University of Sydney

Max-Flow Min-Cut Theorem

Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths.

Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]

Proof strategy: We prove both simultaneously. Let f be a flow. Then the following are equivalent:

(i) There exists a cut (A, B) such that v(f) = cap(A, B). (ii) Flow f is a max flow.

(iii) There is no augmenting path relative to f.

– (i) Þ (ii) This was the corollary to the weak duality lemma.

– (ii) Þ (iii) We show contrapositive.

– Letfbeaflow.Ifthereexistsanaugmentingpath,thenwecanimprovef

by sending flow along a path P and augment the flow in G.

The University of Sydney Page 52

Proof of Max-Flow Min-Cut Theorem

– (iii) Þ (i)

– Let f be a flow with no augmenting paths.

– Let A be set of vertices reachable from s in residual graph. – BydefinitionofA,sÎA.

– Bydefinitionoff,tÏA.

v(f)= X f(e) X f(e) e out of A e into A

A

B

t

s

The University of Sydney

original network

Page 53

Proof of Max-Flow Min-Cut Theorem

– (iii) Þ (i)

– Let f be a flow with no augmenting paths.

– Let A be set of vertices reachable from s in residual graph. – BydefinitionofA,sÎA.

– Bydefinitionoff,tÏA.

v(f)= X f(e) X f(e) e out of A e into A

A

B

t

No augmenting path from A to B => every edge leaving A saturated, every edge entering A is empty

s

The University of Sydney

original network

Page 54

Proof of Max-Flow Min-Cut Theorem

– (iii) Þ (i)

– Let f be a flow with no augmenting paths.

– Let A be set of vertices reachable from s in residual graph. – BydefinitionofA,sÎA.

– Bydefinitionoff,tÏA.

v(f)= X f(e) X f(e) e out of A e into A

= c(e) e out of a

= cap(A, B)

No augmenting path from A to B => every edge leaving A saturated, every edge entering A is empty

A

B

t

s

The University of Sydney

original network

Page 55

Max-Flow Min-Cut Theorem

Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths.

Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]

Proof strategy: We prove both simultaneously. Let f be a flow. Then the following are equivalent:

(i) There exists a cut (A, B) such that v(f) = cap(A, B). (ii) Flow f is a max flow.

(iii) There is no augmenting path relative to f.

Note: This implies we can check if a given flow f is max flow in time O(n + m)!

The University of Sydney Page 56

Ford-Fulkerson: Analysis

Assumption. All initial capacities are integers.

Lemma. At every intermediate stage of the Ford-Fulkerson algorithm

the flow values and the residual graph capacities in Gf are integers.

Proof: (proof by induction)

Base case: Initially the statement is correct. Induction hyp.: True after j iterations.

Induction step: Since all the residual capacities in Gf are integers the bottleneck-value must be an integer. Thus the flow will have integer values and hence also the capacities in the new residual graph.

Integrality theorem. If all capacities are integers, then there exists a max flow f for which every flow value f(e) is an integer.

The University of Sydney Page 57

Ford-Fulkerson: Running Time

Observation:

Let f be a flow in G, and let P be a simple s-t path in Gf. v(f’) = v(f) + bottleneck(f,P)

and since bottleneck(f,P)>0 v(f’) > v(f).

Þ The flow value strictly increases in an augmentation

The University of Sydney

Page 58

Ford-Fulkerson: Running Time

Notation: C = S c(e) e out

of s

Observation: C is an upper bound on the maximum flow.

Theorem. The algorithm terminates in at most v(fmax) £ C iterations. Proof: Each augmentation increase flow value by at least 1.

5

2

8

s

3

The University of Sydney

Page 59

Ford-Fulkerson: Running Time

Corollary:

Ford-Fulkerson runs in O((m+n)C) time, if all capacities are integers.

Proof: C iterations.

Path in Gf can be found in O(m+n) time using BFS. Augment(P,f) takes O(n) time.

Updating Gf takes O(n) time.

The University of Sydney

Page 60

7.3 Choosing Good Augmenting Paths

Is O(C(m+n)) a good time bound?

• Yes, if C is small.

• If C is large, can the number of iterations be as bad as C?

The University of Sydney Page 61

Ford-Fulkerson: Exponential Number of Augmentations

Question: Is generic Ford-Fulkerson algorithm polynomial in

input size?

Answer: No. If max capacity is D, then algorithm can take D iterations.

1

1X0 0

DD

s 1X01 t

m, n, and log C

D

D

00 X1

2

The University of Sydney

Page 62

Ford-Fulkerson: Exponential Number of Augmentations

Question: Is generic Ford-Fulkerson algorithm polynomial in

input size?

Answer: No. If max capacity is D, then algorithm can take D iterations.

11

1 X0 0 1 X0 X0 1 DDDD

s 1X01 t s 1X0X10 t DDDD

0 0 10 X01 X1X

m, n, and log C

22

The University of Sydney

Page 63

Choosing Good Augmenting Paths

– Use care when selecting augmenting paths.

– Some choices lead to exponential algorithms.

– Clever choices lead to polynomial algorithms.

– If capacities are irrational, algorithm not guaranteed to terminate!

– Goal: choose augmenting paths so that: – Can find augmenting paths efficiently.

– Few iterations.

– Choose augmenting paths with: [Edmonds-Karp 1972, Dinitz 1970] – Max bottleneck capacity.

– Sufficiently large bottleneck capacity.

– Fewest number of edges.

The University of Sydney Page 64

Choosing Good Augmenting Paths

– Ford Fulkerson

Choose any augmenting path (C iterations)

– Edmonds Karp #1 (m log C iterations) Choose max flow path

– Improved Ford Fulkerson via capacity scaling (log C iterations) Choose max flow path

– Edmonds Karp #2 (O(nm) iterations)

Choose minimum link path [Edmonds-Karp 1972, Dinitz 1970]

The University of Sydney Page 65

Edmonds-Karp #1

Pick the augmenting path with largest capacity [maximum bottleneck path]

The University of Sydney Page 66

Edmonds-Karp #1

Pick the augmenting path with largest capacity [maximum bottleneck path]

Claim: If maximum flow in G is F, there must exists a path from s to t with bottleneck capacity at least F/m.

The University of Sydney Page 67

Edmonds-Karp #1

Pick the augmenting path with largest capacity [maximum bottleneck path]

Claim: If maximum flow in G is F, there must exists a path from s to t with bottleneck capacity at least F/m.

Proof:

Delete all edges of capacity less than F/m.

Is the graph still connected?

F=24 m=15

6 10 t

2 9

15 s 5 3 8

5

15 10

10

4

15

4 6 15 4 30 7

10

The University of Sydney

Page 68

Edmonds-Karp #1

Pick the augmenting path with largest capacity [maximum bottleneck path]

Claim: If maximum flow in G is F, there must exists a path from s to t with bottleneck capacity at least F/m.

Proof:

Delete all edges of capacity less than F/m.

Is the graph still connected?

Yes, otherwise we have a cut of value less than F.

A

B

t

< F/m
s
The University of Sydney
< F/m
Page 69
Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
Claim: If maximum flow in residual graph Gf is F, there must exists a path from s to t with bottleneck capacity at least F/m.
Proof:
Delete all edges of capacity less than F/m.
Is the graph still connected?
Yes, otherwise we have a cut of value less than F.
A
B
t
< F/m
s
The University of Sydney
< F/m
Page 70
Edmonds-Karp #1
Theorem: Edmonds-Karp #1 makes at most O(m log F) iterations.
Proof:
At least 1/m of remaining flow is added in each iteration.
Û
Remaining flow reduced by a factor of (1-1/m) per iteration. #iterations until remaining flow <1? Þ F×(1-1/m)x <1?
We know: (1-1/m)m < 1/e
Set x = m ln F Þ F × (1-1/m)m ln F < F × (1/e)ln F = 1 The University of Sydney
Page 73
Applications
The University of Sydney
Page 74
– Bipartite matching
– Perfect matching
– Disjoint paths
– Network connectivity – Circulation problems – Image segmentation – Baseball elimination – Project selection
Summary
The University of Sydney
Page 75
1. 2. 3.
4. 5.
Max flow problem
Min cut problem
Ford-Fulkerson:
1. Residual graph 2. correctness
3. complexity
Max-Flow Min-Cut theorem Edmonds-Karp
Appendix: Alternate proof of flow value lemma
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
Proof:
v(f) = fout(A) – fin(A)
v(f) = fout(s) = fout(s) – fin(s)
by flow conservation, all terms except v = s are 0, i.e. fout(v) - fin(v) = 0
= S (fout(v) – fin(v)) vÎA
=S f(e)–Sf(e)
The University of Sydney
Page 76
e out of A
e into A = fout(A) – fin(A)