计算机代写 Lecture 23: Maximum Flow

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