Lecture 23: Maximum Flow
Input: A directed connected graph
every edge
Copyright By PowCoder代写 加微信 powcoder
a source vertex
, where , such that
Output: A flow For all
𝒆 𝐨𝐮𝐭 𝐨𝐟 𝒗
(capacity)
(conservation)
has a capacity ; and a target vertex .
15 15 0 044
s 5 3 8 6 10 t
capacity 15
every edge
a source vertex
Input: A directed connected graph
, where from to , such that
𝒆 𝐨𝐮𝐭 𝐨𝐟 𝒗 𝒆 𝐢𝐧𝐭𝐨 𝒗 2
Output: A flow For each
(capacity)
(conservation)
has a capacity ; and a target vertex .
15 15 1 047
s 5 3 8 6 10 t
capacity 15
Maximum Flow
Def: The value of a flow is
The maximum flow problem is to find the flow with maximum value. Example: The flow below is a maximum flow.
Q: How can we be sure this flow achieves the maximum value possible?
15 15 0 489
s 5 3 8 6 10 t
capacity 15
Value = 28
Def: An s-t cut is a partition of with and .
Def: The capacity of the cut is
Claim: The value of any s-t flow cannot exceed the capacity of any s-t cut.
Observation (proved later): An s-t cut with capacity matching the value of a flow is a “proof” that the flow is a max flow.
s 5 3 8 6 10 t
Capacity(S,T) = 10 + 8 + 10 = 28
Direct applications
Water flowing in pipes
Electricity flows
Vehicle traffic flows
Communication network traffic flows
Indirect applications
Bipartite matching
Circulation-demand problem
Baseball elimination
Airline scheduling
Fairness in car sharing (carpool) …
Flow Applications
Antiparallel edges
Models two-way traffic
Causes problems in algorithms
But can be removed by adding an auxiliary vertex
Will assume no antiparallel edges
Assumptions
Also assume
No edges going into
No edges going out of
Greedy algorithm.
Towards a Algorithm
Start with for all edge .
Find an s-t path where each edge has .
Augment flow along path .
Repeat until you get stuck.
Flow value = 0
Greedy algorithm.
Towards a Algorithm
Start with for all edge .
Find an s-t path where each edge has .
Augment flow along path .
Repeat until you get stuck.
Flow value = 20
Greedy algorithm.
Towards a Algorithm
Start with for all edge .
Find an s-t path where each edge has .
Augment flow along path .
Repeat until you get stuck.
Flow value = 20
Greedy algorithm.
Towards a Algorithm
Start with for all edge .
Find an s-t path where each edge has .
Augment flow along path .
Repeat until you get stuck.
Flow value = 20
Greedy algorithm.
Towards a Algorithm
Start with for all edge .
Find an s-t path where each edge has .
Augment flow along path .
Repeat until you get stuck.
1 Note: Adding flow along a path at each step maintains flow
conservation at every vertex
Flow value = 25
Greedy algorithm.
Towards a Algorithm
Start with for all edge .
Find an s-t path where each edge has .
Augment flow along path .
Repeat until you get stuck.
Doesn’t Work:
local optimality ≠ global optimality
20 0 20 10
20 10 20 10
s 3020 t s 3010 t
10 25 10 25
0 20 10 20
greedy = 25 2 opt = 30 2
Original edge:
Flow , capacity . Create (New) Residual edges:
Residual Graph
, it has one residual edge
with residual capacity
, it has one residual edge
with residual capacity
, it has two residual edges:
Residual graph:
Vertices are the same vertices
Edges are all the residual edges
Residual capacity is “available remaining capacity”
residual capacity u 17 v
residual capacity u 17 v
residual capacity
residual capacity
A Graph G, flow f and associated residual Graph Gf
s 10 3 9 5 10 t
Flow value = 16
10 2 8 6 4
s 4 3 1 5 10 t
Ford-Fulkerson(𝐺, 𝑠, 𝑡) for each (𝑢,𝑣) ∈ 𝐸 do
𝑐 𝑢,𝑣 ←𝑐(𝑒) 𝑐 𝑣,𝑢 ←0
while there exists path 𝑝 in residual graph 𝐺 do 𝑐 𝑝 ←min{𝑐 𝑒:𝑒∈𝑝}
for each edge 𝑢,𝑣 ∈𝑝 do
if 𝑢,𝑣 ∈𝐸 then
𝑓𝑢,𝑣 ←𝑓𝑢,𝑣 +𝑐 𝑝 𝑐 𝑢,𝑣 ←𝑐 𝑢,𝑣 −𝑐 𝑝 𝑐 𝑣,𝑢 ←𝑐 𝑣,𝑢 +𝑐 𝑝
Forward edge
𝑓𝑣,𝑢 ←𝑓𝑣,𝑢 −𝑐 𝑝 𝑐 𝑣,𝑢 ←𝑐 𝑣,𝑢 +𝑐 𝑝 𝑐 𝑢,𝑣 ←𝑐 𝑢,𝑣 −𝑐 𝑝
Backward edge
Greedy algorithm.
1. Start with for all edges .
2. Construct Residual Graph Gf for current flow f(e)=0
3. While there exists some s-t path IN Gf
This is the maximum amount of flow that can
be pushed through residual capacity of ’s edges
5. For every edge , push units of flow along the edge
– by adding to for every
– by subtracting from for every
6. Construct Residual Graph Gf for new current flow f(e)
Claim 1: New at each step is also a flow & its value is more than that of old flow.
Claim 2: When algorithm gets stuck, current flow is maximal!
capacity 10
s 10 3 9 5 10 t
Flow value = 0
capacity 10
s 10 3 9 5 10 t
Flow value = 0
residual capacity 10
s 10 3 9 5 10 t
0 2 02 10X8
Flow value = 8
s 10 3 9 5 2 t 8
X0 6 10 22 X 10
X06 28 610
Flow value = 10
10 2 8 6 10
s 10 3 7 5 10 t 2
s 10 3 9 5 10 t
Flow value = 16
10 2 8 6 4
s 4 3 1 5 10 t
Flow value = 18
8 10 2 8 6 2
s 2 3 1 5 10 t
s 10 3 9 5 10 t
Flow value = 19
10 2 71 6 1
s 1 3 9 5 10 t 9
No s-t path exists in Gf. Algorithm stops! Current flow is optimally maximal. 24
s 10 3 9 5 10 t
Cut capacity = 19
Flow value = 19
10 2 71 6 1
s 1 3 9 5 10 t 9
Def: Let be any flow, and let across the cut is
be any s-t cut. Then, the net flow
Net flow and cuts
Net flow lemma: For any s-t cut 295
s 5 3 8 6 10 t
Value = 24
Def: Let be any flow, and let across the cut is
be any s-t cut. Then, the net flow
Net flow and cuts
Net flow lemma: For any s-t cut 295
s 5 3 8 6 10 t
Value = 6 + 0 + 8 – 1 + 11 = 24
Def: Let be any flow, and let across the cut is
be any s-t cut. Then, the net flow
Net flow and cuts
Net flow lemma: For any s-t cut 295
s 5 3 8 6 10 t
Value = 6 + 8 + 10 = 24
Net flow lemma: Let
Net flow and cuts
be any flow, and let be any s-t cut. Then,
By flow conservation, for any vertex
Sum (2) over all
For every edge
For every edge
For every edge
, together with (1). We see that
Lemma is thus proved!
inside , both from to , only from to , only
and appear appear
How Can we prove flows optimal (maximal)?
We just saw tools for calculating the value of a flow.
Given flow, how can we prove that the flow is optimal, or can it be improved?
For example, the flow below has value=24.
This can be improved to have value=28
s 5 3 8 6 10 t
Value = 10 + 3 + 11 = 24
How Can we prove flows optimal (maximal)?
We just saw tools for calculating the value of a flow.
Given flow, how can we prove that the flow is optimal, i.e., can it be improved?
For example, the flow below has value=24.
This can be improved to have value=28
Is this the best? How can we be sure?
s 5 3 8 6 10 t
Value = 10 + 4 + 14 = 28
Flow and Cuts
Def: The capacity of the cut is
Claim: For any flow Proof:
and any s-t cut , .
s 5 3 8 6 10 t
Capacity = 10 + 8 + 10 = 28
Flow and Cuts
Def: The capacity of the cut is
Claim: For any flow and any s-t cut , .
Example Usage: A few pages ago, we found a flow with value the graph below. The cut , with has
flow is maximum, since no flow can be better!
We now make this into a theorem! 295
for so that
s 5 3 8 6 10 t
Capacity = 10 + 8 + 10 = 28
Need to find an s-t cut By net flow lemma,
a) all edges
Correctness of Ford-
Max-Flow min-cut theorem: Let be any flow.
Then the following three statements are equivalent:
(1) is a maximum flow.
(2) The residual graph has no path from to . (3) for some s-t cut .
Proof: (1) (2), or (2)
(1): If there is a path in , we can improve . such that
, so must find a cut such that are full, i.e.,
set of all nodes reachable from in .
And this cut must meet the two conditions above! (1): By the claim from last page.
are empty, i.e.,
cannot include due to (2), so it is a valid s-t cut
b) all edges Consider
Ford-Fulkerson: Running time analysis
Q: Which path to choose in the residual graph?
A: Ford-Fulkerson doesn’t specify.
The choice does not affect correctness
But it does affect running time
Note that one iteration of the loop can find one augmenting path in
time using BFS or DFS so full run-time of FF is
Claim: When all capacities are integers, Ford-Fulkerson takes at most
iterations, where ∗ is a maximum flow.
Proof: Each iteration increases by at least 1.
Integrality property: if all edge capacities are integers, then there exists a max flow for which every flow value is an integer and the F-F algorithm constructs such a flow.
Proof: The flow created by F-F is an integral flow since all (residual) capacities created are integral, so all changes to flows are additions/subtractions of integers.
Bad example
(a) U (b) U (c) U ststst
ststst VVV
This up/down process will continue, adding only 1 unit of flow per augmenting path. The final algorithm will require 1,000,000 augmenting steps!
If we had chosen s,u,t as first augmenting path, algorithm only uses 2 steps!
When capacities are irrational numbers, the algorithm might never terminate!
Edmonds-Karp: Choosing the shortest augmenting path
Idea: Choose the shortest (in terms of # edges) path in residual graph Can be done in time using BFS.
Theorem: If we always choose the shortest path in the residual graph to augment the flow, then the Ford-Fulkerson algorithm terminates in
iterations.
Proof: See textbook (not required).
Corollary: The Ford-Fulkerson algorithm can be implemented to run in
More advanced algorithms
Push-relabel algorithms,
time, and perform well in practice
(see textbook for details)
Theoretically best algorithm:
time [King, Rao, Tarjan, 1994] [Orlin, 2013]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com