CSC373H Lecture 7
Dan Zingaro
October 31, 2016
Residual Networks
Sometimes it is necessary to decrease flow along one or more edges to increase flow overall
We can formalize this idea by using a residual network Gf and finding augmenting paths in there instead of in G
We use the following rules. Exclude any edge with 0 capacity c(u,v)−f(u,v), if(u,v)∈E
cf(u,v)= f(v,u), if(v,u)inE 0, otherwise
Residual Network: Example (Overview)
Residual Network: Example (Flow Network)…
Residual Network: Example (Residual Network)…
Augmenting Paths, Take 2
Now let’s find an augmenting path in Gf and use it to augment flow in G
Define the residual capacity of an augmenting path p in the residual network to be cf (p) = min{cf (u,v) : (u,v) is on p}
Weaddcf(p)totheflowofeachforwardedgeinG and subtract cf (p) from the flow of each backward edge in G
This is the correct Ford-Fulkerson method
Ford-Fulkerson Method
ford-fulkerson(G, s, t):
for each edge (u, v) in E:
f(u, v) = 0
while there exists a path p from s to t in Gf:
cf(p) = min {cf(u, v) : (u, v) on p}
for each edge (u, v) on p:
if (u, v) is an edge in G:
f(u, v) = f(u, v) + cf(p)
else: # (v, u) is an edge in G
f(v, u) = f(v, u) – cf(p)
Correctness of Ford-Fulkerson: Any Flow?
Supposewehaveaflowf inG=(V,E)andanotherflowf′ in Gf
We can “add” these flows together to get another valid flow whose value is |f | + |f ′| (study the details in the textbook!)
Adding flows is referred to as augmenting one flow by another
f(u,v)+f′(u,v)−f′(v,u) if(u,v)∈E
0 otherwise
(f ↑f′)(u,v)=
Correctness of Ford-Fulkerson: Any Flow?…
OK. So we can find any flow with positive value in Gf and use it to increase |f |
But this alone doesn’t help us
HowarewesupposedtofindaflowinGf? Seemsjustas
difficult as finding a flow in G!
Two key insights of Ford-Fulkerson
An augmenting path in Gf is a flow in Gf Andthevalueofsuchaflowis>0
SoallwehavetodoisfindanaugmentingpathinGf,and that’s a perfectly good flow with positive value in Gf !
Correctness of Ford-Fulkerson: Augmenting Paths
Recall notation
cf (p) = min{cf (u,v) : (u,v) is on p} Also define
cf(p) if(u,v)isonp fp(u,v) = 0 otherwise
Claim: fp isaflowinGf with|fp|>0.
Correctness of Ford-Fulkerson: Augmenting Paths…
The proof involves showing four things about an augmenting path flow in Gf :
Flow on each edge is at least 0 (capacity constraint)
Flow on each edge is at most the edge capacity (capacity
constraint)
Flow conservation is satisfied
Thevalueoftheflowis>0
Correctness of Ford-Fulkerson
Ford-Fulkerson is correct iff we can prove two things
(1) If f is a maximum flow in G then Gf has no augmenting
paths
(2) If Gf has no augmenting paths then f is a maximum flow
in G
We can do part (1) of the proof now
Contradiction proof: suppose f is maximum flow but there is an augmenting path in Gf
Then we can use that augmenting path to get a better flow than the supposed maximum flow
But proving part (2) isn’t so easy
It’s easier if we take a scenic route to prove it using cuts . . .
Cuts
Acut(S,T)ofaflownetworkG=(V,E)isapartitionofV such that
s∈S
t∈T
S andT aredisjointandV =S∪T
Cuts…
We can define the flow and the capacity of a cut.
Flow f across cut (S,T) is the flow from S to T minus the flow from T to S
u∈S v∈T f(u,v)−u∈S v∈T f(v,u)
Capacity c of cut (S,T) is the capacity from S to T (has nothing to do with the capacity from T to S!)
u∈S v∈T c(u,v)
Cuts: Example
Consider cut ({s, v1, v2}, {v3, v4, t}). What is the flow across this cut? What is the capacity of the cut?
Cuts: Flow and Capacity
On the previous slide, we saw that the flow across the cut equaled |f |
And we saw that |f | was less or equal to the capacity of the cut
These are not coincidences
Wecanprovethatf(S,T)=|f|foranycut(S,T)andflowf
(study details in textbook)
Wecanalsoprovethat|f|≤c(S,T)foranycut(S,T)and
flow f . We’ll do this now!
Flow Values are Less than Cut Capacities
We show that for any flow f and cut (S,T), we have |f | ≤ c (S , T ).
|f | = f (S , T )
= f (u, v ) − f (v , u)
(previous slide) (flow across cut)
(capacity constraint)
(capacity constraint)
(capacity of cut)
u∈S v∈T
≤ f (u, v )
u∈S v∈T
≤ c(u,v) u∈S v∈T
= c(S,T)
u∈S v∈T
Consequence: value of a maximum flow is ≤ minimum capacity of any cut.
Max-Flow Min-Cut
Remember that our goal here is to prove that a flow is maximum iff the residual network contains no augmenting paths
We already proved one half: that if a flow is maximum then the residual network has no augmenting paths
We prove the other half in two steps
(A) Prove that if the residual network has no augmenting
paths then |f | = c (S , T ) for some cut (S , T )
(B)Provethatif|f|=c(S,T)forsomecut(S,T),thenf is
a maximum flow
Max-Flow Min-Cut…
(A) Prove that if the residual network has no augmenting paths then |f | = c (S , T ) for some cut (S , T ).
We assume that Gf has no augmenting paths (i.e. no path from s to t)
LetSbetheverticesreachablefromsinGf andT=V−S
(S,T)isacut:s∈Sandt̸∈Sbecausetisnotreachable
from s
ConsideruinSandvinT.(u,v)isnotinGf,otherwisev
would be reachable from s
If(u,v)∈E,thenc(u,v)−f(u,v)mustbe0tokeep(u,v)
out of Gf
Sointhiscase,f(u,v)=c(u,v)
If(v,u)∈E,thenf(v,u)mustbe0tokeep(u,v)outofGf |f | = f (S , T ) = f (u, v ) − f (v , u)
u∈S v∈T v∈T u∈S
= c(u,v) = c(S,T) u∈S v∈T
Max-Flow Min-Cut…
Provethatif|f|=c(S,T)forsomecut(S,T),thenf isa maximum flow.
Wehavealreadyestablishedthat|f|≤c(S,T)foranycut (S,T)
That is, |f| is at most c(S,T)
And we are given here that |f | is exactly that maximum value
c(S,T)
f is therefore a maximum flow
Choosing Bad Paths
Ford-Fulkerson can be terribly inefficient. Watch what happens if we choose the wrong augmenting paths in this flow network!
Runtime of Ford-Fulkerson
If we choose arbitrary augmenting paths: O(mf ∗), where f ∗ is the value of a maximum flow
This is not a polynomial-time algorithm!
Edmonds-Karp is based on the Ford-Fulkerson method, and
uses BFS to choose augmenting paths of fewest edges
If we do that, then we have O(nm2) — polynomial-time now!
There are even better techniques than this that we will not discuss
Reason: we want to use max-flow to solve other problems
You can use an existing, fast implementation of max-flow
The max-flow algorithm doesn’t change; only the problem that
we are solving changes