程序代写代做代考 algorithm CSC373H Lecture 7

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