COMP251: Network flows (2)
Jérôme Waldispühl School of Computer Science
McGill University
Based on slides from M. Langer (McGill)
Recap Network Flows
G = (V, E) directed.
Each edge (u, v) has a capacity c(u, v) ≥ 0. If (u,v) Ï E, then c(u,v) = 0.
Source vertex s, sink vertex t, assume s
v t for all v ∈ V. 2/3
1/3
s 0/1 2/2
1/3
2/2
1/1 2/3
2/3
1/2
t
1/2
Problem: Given G, s, t, and c, find a flow whose value is maximum.
Application
Maximize flow of supplies in eastern europe!
Recap (residual graphs)
0/2
Flow s 3/4 t
0/2
0/2
3/3
3/3
0/3
0/2
Residual graph
0/3
s 0/3 t
0/1
0/2
0/2
0/3
0/3
Recap (Ford-Fulkerson algorithm)
f ¬0 Gf¬G
while (there is a s-t path in Gf) do f.augment(P)
update Gf based on new f
0/2
3/3
0/2
s 3/4 t
3/3
0/3
0/2
2/2 2/2 3/3 s1/4 t
3/3
2/3
2 20
s2t 0
2 2
2/2
0
Recap graph cuts
A graph cut is a partition of the graph vertices into two sets.
S V-S
ThecrossingedgesfromStoV-Sare{(u,v)| u∈S,v∈V-S}, also called the cut set.
Cuts in flow networks Definition: An s-t cut of a flow network is a cut A, B such that
s∈A and t∈B.
Notation: We write cut(A,B) the set of edges from A to B.
Definition: The capacity of an s-t cut is
c(e) e∈cut(A,B)
∑
0/5 s 0/3
0/1 Examples 0/5
s 0/1 0/3
t 0/4
s 0/1 0/3
t 0/4
0/4 1+5=6 0/5 s 0/1
0/2
1+2=3
0/2 t
0/5
0/3
0/2 t 0/4
5+3+4=12
0/2
2+4=6
Objectives For any flow network:
• Maximum value of a flow = the minimum capacity of any cut.
• Ford-Fulkerson gives the “max flow” and the “min cut”.
Application
The bottleneck
How to cut supplies if cold war turns into real war!
Flow through a cut
Claim: Given a flow network. Let f be a flow and A, B be a s-t cut.
Then,
Notation: |f| = fout(A) – fin(A)
f= ∑ f(e)− ∑ f(e) e∈cut(A,B) e∈cut(B,A)
4 s31t
2
A
1 5
B
|f|=9-4=5
Flow through a cut • for any u∈ V–{s,t}, we have fout(u)=fin(u).
• Summingoveru∈A-{s}: ∑ fout(u)= ∑ fin(u) u∈A−{s} u∈A−{s}
Proof:
• •
f = fout(s)=∑fout(u)−∑fin(u) u∈A u∈A
Each edge e=(u,v) with u,v∈ A contributes to both sums, and can be removed (Note: fin(s) = 0).
f= ∑ f(e)− ∑ f(e) e∈cut(A,B) e∈cut(B,A)
≡ fout(A)− fin(A)
Upper bound on flow through cuts Claim: For any network flow f, and any s-t cut(A,B)
Proof:
f≤ ∑c(e) e∈cut(A,B)
f =fout(A)−fin(A)
≤ fout(A)
≤ ∑ c(e) e∈cut(A,B)
Observations
• Some cuts have greater capacities than others.
• Some flows are greater than others.
• But every flow must be ≤ capacity of every s-t cut.
• Thus, the value of the maximum flow is less than capacity of the minimum cut.
Value of flow in Ford-Fulkerson
• Ford-Fulkersonterminateswhenthereisnoaugmentingpath in the residual graph Gf.
• LetAbethesetofverticesreachablefromsinGf,andB=V-A.
• A,Bisas-tcutinGf.
• A,B is an s-t cut in G (G and Gf have the same vertices).
• |f|=fout(A)-fin(A)
• Wewanttoshow: f = ∑ c(e)
• Andinparticular:
e∈cut(A,B)
1 fout(A)= ∑ c(e) 2 fin(A)=0 e∈cut(A,B)
Value of flow in Ford-Fulkerson (1) For any e=(u,v) ∈ cut(A,B), f(e)=c(e).
• f(e)
• v reachable from s in Gf ⇒ contradiction.n
(2) fin(A)=0: ∀ e=(v,u)∈E such that v∈B, u∈A, we have f(e)=0.
• f(e)>0 ⇒ ∃ backward edge (u,v) in Gf such that cf(e)=f(e)
• v is reachable from s in Gf ⇒ contradiction.n
Max flow = Min cut
• Ford-Fulkersonterminateswhenthereisnopaths-tinthe residual graph Gf
• ThisdefinesacutinA,BinG(A=nodesreachablefroms) • f=fout(A)−fin(A)
= ∑ f(e)− ∑ f(e) e∈cut(A,B) e∈cut(B,A)
• Ford-Fulkerson flow = ∑
c(e)−0 e∈cut(A,B)
= capacity of cut(A,B) Note: We did not proved uniqueness.
Computing the min cut
Q: Given a flow network, how can we compute a minimum cut?
Answer:
• Run Ford-Fulkerson to compute a maximum flow (it gives us Gf) • RunBFSorDFSofs.
• The reachable vertices define the set A for the cut
Example (min cut with Ford-Fulkerson)
(1) Initial flow net G
0/3 0/3
(2) Compute max flow (FF)
2/3 2/3
0/3
s 0/4 t
3/3
s 1/4 t
0/4 0/2
(3) Compute Gf and vertices
accessible from s 1
0/4
3/4 2/2 2/4
(4) Vertices accessible from s in
Gf determine the min cut 2/3
1 3 2/3 3/3
s231 ts 1/4 t 3
1 2 2 3/4 2/2 2/4
Bipartite matching
Suppose we have an undirected graph bipartite graph G=(V,E). AB
Q: How can we find the maximal matching? (Recall Lecture 11) AB
Bipartite matching with network flows
Define a flow network G’=(V’,E’) such that:
• V’=VÈ{s,t}
• E’={(u,v)|u∈A,v∈B,(u,v)∈E} È{(s,u)|u∈A}È{(v,t)|v∈B} • Capacities of every edge = 1.
s
A1B
t
11 1
Motivation: Max flow ⇒ max matching.
Max flow in bipartite graphs
A1B
111 11
s
1111 11
1
t
Exercise: The maximal flow found by Ford-Fulkerson defines a maximal matching in the original graph G (the maximal set of edges (u,v) u∈A & v∈B such that f(u,v)=1).
Max matching with Ford-Fulkerson
Ford-Fulkerson will find an augmenting path with β=1 at each iteration. They are of the form:
G’f
s
AB
t
Or have more than one zig-zag in Gf
Note:
• NoedgefromBtoAinE’.Thebackedgesareintheresidualgraph.. • Edgesesuchthatc(e)=0arenotshown.
Running time
Q: How long will it take to find a maximal matching with Ford- Fulkerson?
• The general complexity of Ford-Fulkerson is O(C.|E|),
where
• Suppose |A|=|B|=n
• Then, C=|A|=n and |E’|= |E|+2n = m+2n (Assume m>n)
• Thus,C.|E’|=n.(m+2n)
• Running time is O(nm)
C = ∑c(s, u) u
Example
What is max flow? What is min cut? AB
s
t
Example
What is the max flow? What is the min cut? AB
s
t
Max flow |f|=2.
Note: there are other flows with |f|=2. What is the minimum cut?
Example
Find any min cut with capacity 2.
stst
Not a cut!
Not a min cut!
tst
s
Not a cut! min cut!
Example
To find a min cut compute a max flow.
Flow s
0
0
1
1
1
t
1 11
00
backward
forward
t
Residual graph
s
Example
To find the cut run BFS (or DFS) from s on the residual graph. The reachable vertices define the (min) cut.
Residual
graph s t with DFS
Min cut (in G!)
s
t