[SOLVED] 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. 10020 10s 300 t10 2000Flow value = 0 The University of SydneyPage 282 Towards a Max Flow AlgorithmGreedy 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 s3 0 X0 2 0t t20 X02001010020X0 2 0Flow value = 20 The University of SydneyPage 292 Towards a Max Flow AlgorithmAugmenting greedy flow to get optimal flow1120 0 20 1020 10 20 10s 3020 t s 3010 t10 20 10 200 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 30 Towards a Max Flow AlgorithmAugmenting greedy flow to get optimal flow – Send 10 units on (s,2) edge1120 0 20 1020 10 20 10s 3020 t s 3010 t10 20 10 2010 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 31 Towards a Max Flow AlgorithmAugmenting 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 21120 0 20 1020 10 20 10s 3010 t s 3010 t10 20 10 2010 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 32 Towards a Max Flow AlgorithmAugmenting 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 11120 10 20 1020 10 20 10s 3010 t s 3010 t10 20 10 2010 20 10 2022TgherUeniverdsityof=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 ÎEcapacityu 17 v6flowresidual capacity vresidual capacity u 11 6– Residual graph: Gf = (V, Ef ).– Residual edges with positive residual capacity. – Ef ={e:f(e) 0}.
– 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/mPage 69 Edmonds-Karp #1Pick 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.ABt< F/m s The University of Sydney< F/mPage 70 Edmonds-Karp #1Theorem: 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/eSet x = m ln F Þ F × (1-1/m)m ln F < F × (1/e)ln F = 1 The University of SydneyPage 73 ApplicationsThe University of SydneyPage 74– Bipartite matching– Perfect matching– Disjoint paths– Network connectivity – Circulation problems – Image segmentation – Baseball elimination – Project selection SummaryThe University of SydneyPage 751. 2. 3.4. 5.Max flow problemMin cut problemFord-Fulkerson:1. Residual graph 2. correctness3. complexityMax-Flow Min-Cut theorem Edmonds-Karp Appendix: Alternate proof of flow value lemmaFlow 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 amountleaving 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 SydneyPage 76e out of Ae into A = fout(A) – fin(A)