CS计算机代考程序代写 data structure discrete mathematics ER algorithm 7. NETWORK FLOW I

7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks
Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on Sep 8, 2013 6:40 AM

SECTION 7.1
7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks

Vancouver i
Kamloops Edmonton Ottawa
250 → Toronto yo
is
Seattle
Kooy Billings
: to
not

Flow network
・Abstraction for material flowing through the edges. ・Digraph G = (V, E) with source s ∈ V and sink t ∈ V.
Nonnegative integer capacity c(e) for each e ∈ E.
capacity
no parallel edges no edge enters s no edge leaves t
9 4 15
15 10 s5 8 10t
10
15
4 6 15 10 16
3

Maximum flow problem
D・ef. An st-flow (flow) f is a function that satisfies:
・For each e ∈ E: 0 ≤ f(e) ≤ c(e) [capacity]
∑ f(e) = ∑ f(e)
For each v ∈ V – {s, t}: €
€
e in to v
e out of v
capacity
[flow conservation]
flow
5 / 9
inflow at v = outflow at v =
5 + 5 + 0 10 + 0
= 10 = 10
s 5 / 5
5 / 8
10 / 10
t
0 /4
0 / 15
v
0 / 15
0 /4
10 / 16
7
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10

Maximum flow problem
D・ef. An st-flow (flow) f is a function that satisfies:
・For each e ∈ E: 0 ≤ f(e) ≤ c(e) [capacity]
For each v ∈ V – {s, t}: ∑ f(e) = ∑ f(e) e in to v e out of v
v( f ) = Def. The value of a flow f is: val(f) =
€
∑ f (e) . eoutof s
€ €
5/ 9
[flow conservation]
s
5 + 10 + 10 = 25
5 / 5
5 / 8
10 / 10 t
0 /4
0 / 15
value =
10 / 16
0 /4
0 / 15
8
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10

Maximum flow problem
D・ef. An st-flow (flow) f is a function that satisfies:
・For each e ∈ E: 0 ≤ f(e) ≤ c(e) [capacity]
For each v ∈ V – {s, t}: ∑ f(e) = ∑ f(e) [flow conservation] e in to v e out of v
v( f ) = ∑ f (e) . Def. The value of a flow f is: val(f) =
eoutof s Max-flow problem. Find a flow of maximum value.
€
€ €
8/ 9
s
8 + 10 + 10 = 28
5 / 5
8 / 8
10 / 10 t
0 /4
0 / 15
value =
13 / 16
0 /4
0 / 15
9
8 / 10
2 / 15
10 / 10
13 / 15
3 /6
10 / 10

Minimum cut problem
Def. A st-cut (cut) is a partition (A, B) of the vertices with s ∈ A and t ∈ B. Def. Its capacity is the sum of the capacities of the edges from A to B.
€
cap(A,B) = ∑ c(e) e out of A
10
s5t 15
capacity = 10 + 5 + 15 = 30
4

Minimum cut problem
Def. A st-cut (cut) is a partition (A, B) of the vertices with s ∈ A and t ∈ B. Def. Its capacity is the sum of the capacities of the edges from A to B.
€
A
–
‘
e””n.
10 (y-
e’
e
”
cap(A,B) =
∑ c(e) e out of A
B
sn8t ‘
don’t count edges from B to A
capacity = 10 + 8 + 16 = 34
y ,
16Y’ l’
5

Minimum cut problem
Def. A st-cut (cut) is a partition (A, B) of the vertices with s ∈ A and t ∈ B. Def. Its capacity is the sum of the capacities of the edges from A to B.
CA, B)
t- . t t #
s8t A
10
cap(A,B) = ∑ c(e) e out of A
Min-cut problem. Find a cut of minimum capacity. €
10
v Ift E cap
“‘ for
all flows
capacity = 10 + 8 + 10 = 28
6
B

Towards a max-flow algorithm
Greedy algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an s􏰉t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. network G 0/ 4 0 / 10 0 /8 0 / 10 s 0 / 10 0 / 9 0 / 10 value of flow t 0 0 /2 0 / 6 flow capacity 11 Towards a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for all edge e ∈ E. ・Find an s􏰉t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. flow capacity network G 0/ 4 s 0 / 10 0 / 9 0 / 10 value of flow t 0 0 /2 0 / 6 11 0 / 10 0 /8 0 / 10 Towards a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for all edge e ∈ E. ・Find an s􏰉t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. network G 0/ 4 s 0 / 10 0 / 9 8 —0 / 10 t 0 + 8 = 8 0 /2 0 / 6 12 0 / 10 8 —0 / 10 8 —0 / 8 Towards a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for all edge e ∈ E. ・Find an s􏰉t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. network G 0/ 4 s 0 / 10 — t 8 + 2 = 10 2 —0 / 2 0 / 6 2 G2IO —8 / 10 0/ 9 13 0 / 10 10 —8 / 10 8 /8 Towards a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for all edge e ∈ E. ・Find an s􏰉t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. network G 0/ 4 s —0 / 10 —2 / 9 10 / 10 t 10 + 6 = 16 2 / 2 6 —0 / 6 68 14 6 —0 / 10 8 /8 10 / 10 Towards a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for all edge e ∈ E. ・Find an s􏰉t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. network G ending flow value = 16 0/ 4 s 6 / 10 8 / 9 10 / 10 t 16 2 /2 6 / 6 15 6 / 10 8 /8 10 / 10 Towards a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for all edge e ∈ E. ・Find an s􏰉t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. but max-flow value = 19 network G 3/ 4 s 9 / 10 9 / 9 10 / 10 t 19 0 /2 6 / 6 16 9 / 10 7 /8 10 / 10 residual -Define Vl Towards a solution : the graph residual graph ✓ ( Gf ) 61 := Forward edges : f-(e) accel, residual capacity cle ) - Hel e = Curl sit. add e to Gf with For edge -Backward edges , Claim If then ' flow is a graph flow in the original graph : add For - f e ' - is a f tf ' Hel 70 Chul to Gf with residual capacity f-let edge e = Curl S.t. i n residual Gf , G. Claim Prout: f ' is a flow graph flow in the original graph If then ff' is a + i n residual Gf , G. Suppose f ' is a flow in residual graph . For any flow assigned to forward edge e , reside capacity ensures that f-Cel tf'let E Recall : O e f'let s cle ) - f- le ) ⇒ c Cel. J, O E f-let+f'lets feeltale)- Hel= cle) tresidcapacitt Claim Prout: If then Suppose f ' is a f tf ' flow is a graph flow in the original graph i n residual Gf , G. f ' is a flow in residual graph . For any flow assigned to backward edge , w e only f flow of f backward edge Recall that ⇒ fluid ) z - fluid =o (decreases no lower than o ( vial r-esid capacity oe E fluid tf'la, v1 f'(vial flu id f' v. oz H - ( ul Clum Z Cvn - z - -f' ) fluid Residual graph Original edge: e = (u, v) ∈ E. ・Flow f (e). ・Capacity c(e). R・esidual edge. ・"Undo" flow sent. ・e = (u, v) and eR = (v, u). Residual capacity: cf(e)=$%c(e)−f(e) ife∈E &f(e) if eR ∈E original graph G u 6/17 v flow capacity residual graph Gf residual capacity R・esidual graph: Gf = (V, Ef ). €・Residual edges with positive residual capacity. ・E = {e : f (e) < c(e)} ∪ {eR : f (e) > 0}. f
where flow on a reverse edge negates flow on a forward edge
u 11 v 6
Key property: f ‘ is a flow in G iff f + f ‘ is a flow in G. f
17

Augmenting path
Def. An augmenting path is a simple s􏰉t path P in the residual graph Gf . Def. The bottleneck capacity of an augmenting P is the minimum
residual capacity of any edge in P.
Key property. Let f be a flow and let P be an augmenting path in Gf .
Then f ‘ is a flow and val(f ‘) = val(f) + bottleneck(Gf, P). AUGMENT (f, c, P)
________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
b ← bottleneck capacity of path P. FOREACH edge e ∈ P
www.krlc-PEBTTT-yysgiforwardedgethenfu IF(e∈E) f(e) ← f(e) + b., v1 ←
tb IFENG.gs#ackgnedT7thenflv.ut-flr, u l
fluid ELSE If f(eR)←f(eR) – b.
-b
RETURN f. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
18

Ford-Fulkerson algorithm
F・ord-Fulkerson augmenting path algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an augmenting path P in the residual graph G . f
・Augment flow along path P. Repeat until you get stuck.
FORD-FULKERSON (G, s, t, c) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH edgee∈E:f(e)←0.
Gf ←residualgraph.
WHILE (there exists an augmenting path P in Gf )
f ← AUGMENT (f, c, P).
Update Gf. RETURN f.
} _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
19

Ford-Fulkerson algorithm demo
network G
flow
capacity
0/ 6
0/ 4
s 0 / 10
residual graph Gf
0 / 9
0 / 10
value of flow t 0
0/ 2
4
residual capacity
26
s10 9 10t
20
10
0 / 10
0 / 10
10
0 /8
8

Ford-Fulkerson algorithm demo
network G
0/ 4
s 0 / 10
residual graph Gf
0 / 9
8
—0 / 10
t 0 + 8 = 8
0/ 2
0/ 6
4
26
s10 9 10t
21
10
8
—0 / 10
0 / 10
10
8
—0 / 8
8

Ford-Fulkerson algorithm demo
network G
0/ 4
s 0 / 10
residual graph Gf
22
— —8 / 10 0/ 9
t 8 + 2 = 10
2 —0 / 2
0 / 6
4
26
s10 9 2t 8
22
8
2
10
—8 / 10
0 / 10
10
8 /8
8

Ford-Fulkerson algorithm demo
network G
0/ 4
2 / 2
6 —0 / 6
68
s —0 / 10 — 2/ 9
10 / 10
t 10 + 6 = 16
residual graph Gf
4
26
s10 7 10t 2
23
10
10 / 10
6
—0 / 10
10
8 /8
8

Ford-Fulkerson algorithm demo
network G
2
—0 / 4
s —6 / 10
residual graph Gf
8 / 9
10 / 10
t 16 + 2 = 18
8
0 —2 / 2
6 / 6
4
26
s4 1 10t 68
24
10
10 / 10
8
—6 / 10
4
6
8 /8
8

Ford-Fulkerson algorithm demo
network G
3
—2 / 4
s —8 / 10 — 8/ 9
10 / 10
t 18 + 1 = 19
0/ 2
6/ 6
99
residual graph Gf
2
2
26
s2 1 10t 88
25
10
10 / 10
9
—8 / 10
2
8
7
—8 / 8
8

Ford-Fulkerson algorithm demo
network G
min cut
3/ 4
0/ 2
6/ 6
max flow
s 9 / 10
9 / 9
3
1
10 / 10
t 19
residual graph Gf
nodes reachable from s
26
s1 9 10t 9
26
10
10 / 10
9 / 10
1
9
7 /8
7 1

R-untime analysis o f
Ford – Fulkerson

SECTION 7.2
7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks

Relationship between flows and cuts
Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
∑f(e) − ∑f(e) = v(f) e out of A e in to A
netflowacrosscut = 5+10+10= 25
s
5 / 5
5 / 8
10 / 10
t value of flow = 25
€
5/ 9
0 /4
0 / 15
0 /4
0 / 15
10 / 16
28
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10

Relationship between flows and cuts
Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
∑f(e) − ∑f(e) = v(f) e out of A e in to A
netflowacrosscut = 10+5+10= 25
€
5/ 9
s
5 / 5
5 / 8
10 / 10
t value of flow = 25
0 /4
0 / 15
0 /4
0 / 15
10 / 16
29
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10

Relationship between flows and cuts
Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
∑f(e) − ∑f(e) = v(f) e out of A e in to A
netflowacrosscut = (10+10 +5+10+0+0)–(5+5+0+0) = 25
s
5 / 5
5 / 8
10 / 10
€
5/ 9
0 /4
0 / 15
edges from B to A
t value of flow = 25
0 /4
0 / 15
10 / 16
30
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10

Relationship between flows and cuts
Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
∑f(e) − ∑f(e) = v(f)
Pf.
€
v(f) v(f)
= =
∑ f(e) ∑ f(e)
by flow conservation, all terms except v = s are 0
%( %(
€ €
€
e out of A
e in to A
v(f)
=
∑ f(e) e out of s
= =
∑%∑f(e)−∑f(e)( ∑’∑f(e)−∑f(e)*
=
∑’∑f(e)−∑f(e)*
= =
e in to v ∑f(e)− ∑f(e).
=
∑f(e)− ∑f(e). ∑f(e)− ∑f(e).
▪
e out of s e out of s
‘&
v ∈A &e out of v
e in to v e in to v
*) )
v ∈A &e out of v v ∈ A e out of v
)
e out of A e out of A
e in to A e in to A
e out of A
e in to A
31

€
8 /9
7 / 8
12 / 16
Relationship between flows and cuts
Weak duality. Let f be any flow and (A, B) be any cut. Then, v( f ) ≤ cap(A, B).
Pf. v(f)
= ∑ f(e)− ∑ f(e)
v(f) v(f) v(f)
flow-value lemma
= ∑ f(e)− ∑ f(e) = ∑ f(e)− ∑ f(e) = eout∑ofAf(e)−ein∑toAf(e)
e out of A e out of A e out of A
e in to A e in to A e in to A
≤ ∑ f(e)
≤ ∑ f(e) ≤ ∑ f(e) ≤ e out∑of Af (e)
e out of A eoutofA e out of A
≤ ∑ c(e)
≤ ∑ c(e) ≤ ∑ c(e) ≤ e out∑of Ac(e)
e out of A e out of A e out of A
= cap(A,B)
= cap(A,B) = cap(A,B) = cap(A,B)
▪
10 9 / 10 t s 5
15
€ € €
0 /4
0 /4
0 / 15
0 / 15
s
5 /5
t
value of flow = 27
≤
capacity of cut = 30
32
8 / 10
2 / 15
10 / 10
12 / 15
2/ 6
10 / 10

Max-flow min-cut theorem
Augmenting path theorem. A flow f is a max-flow iff no augmenting paths. Max-flow min-cut theorem. Value of the max-flow = capacity of min-cut.
Pf. The following three conditions are equivalent for any flow f : i. There exists a cut (A, B) such that cap(A, B) = val(f ).
ii. f is a max-flow.
iii. There is no augmenting path with respect to f.
[ i ⇒ ii ]
・Suppose that (A, B) is a cut such that cap(A, B) = val(f ).
・Then, for any flow f ‘, val(f ‘) ≤ cap(A, B) = val(f ).
・Thus, f is a max-flow. ▪
weak duality by assumption
33

Max-flow min-cut theorem
Augmenting path theorem. A flow f is a max-flow iff no augmenting paths. Max-flow min-cut theorem. Value of the max-flow = capacity of min-cut.
Pf. The following three conditions are equivalent for any flow f : i. There exists a cut (A, B) such that cap(A, B) = val(f ).
ii. f is a max-flow.
iii. There is no augmenting path with respect to f.
[ ii ⇒ iii ] We prove contrapositive: ~iii ⇒ ~ii.
・Suppose that there is an augmenting path with respect to f. ・Can improve flow f by sending flow along this path. ・Thus, f is not a max-flow. ▪
34

Max-flow min-cut theorem
[・iii⇒i]
・Let f be a flow with no augmenting paths.
・Let A be set of nodes reachable from s in residual graph Gf. ・By definition of cut A, s ∈ A.
By definition of flow f, t ∉ A.
edge e = (v, w) with v ∈ B, w ∈ A must have f(e) = 0
B
v(f) = v(f) = v(f) =
= = = = = =
∑f(e)− ∑f(e) ∑f(e)− ∑f(e)
original network G
A
e out of A e in to A ∑f(e)− ∑f(e)
flow-value lemma
€ € €
e out of A
∑ c(e)
t
e out of A
∑ c(e)
e in to A e in to A
eoutofA
∑ c(e)
e out of A cap(A,B)
e out of A cap(A,B)
cap(A,B)
s
edge e = (v, w) with v ∈ A, w ∈ B must have f(e) = c(e)
35

SECTION 7.3
7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks

Running time
Assumption. Capacities are integers between 1 and C.
Integrality invariant. Throughout the algorithm, the flow values f (e)
and the residual capacities cf (e) are integers.
Theorem. The algorithm terminates in at most val (f *) ≤ n C iterations.
Pf. Each augmentation increases the value by at least 1. ▪ Corollary. The running time of Ford-Fulkerson is O(m n C).
Corollary. If C = 1, the running time of Ford-Fulkerson is O(m n).
Integrality theorem. Then exists a max-flow f * for which every flow value f *(e) is an integer.
Pf. Since algorithm terminates, theorem follows from invariant. ▪
37

Bad case for Ford-Fulkerson
Q. Is generic Ford-Fulkerson algorithm poly-time in input size?
m, n, and log C
A. No. If max capacity is C, then algorithm can take ≥ C iterations.
・s→v→w→t
・s→w→v→t
each augmenting path sends only 1 unit of flow (# augmenting paths = 2C)
vCt
C1C
sCw
・s→v→w→t ・
・s→w→v→t ・…
・s→v→w→t s→w→v→t
38

Choosing good augmenting paths
Use care when selecting augmenting paths.
・Some choices lead to exponential algorithms.
・Clever choices lead to polynomial algorithms.
・If capacities are irrational, algorithm not guaranteed to terminate!
Goal. Choose augmenting paths so that: ・Can find augmenting paths efficiently. ・Few iterations.
39

Choosing good augmenting paths
C・hoose augmenting paths with:
・Max bottleneck capacity. ・Sufficiently large bottleneck capacity.
Fewest number of edges.
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
JACK EDMONDS
University of Waterloo, Waterloo, Ontario, Canada
AND
RICHARD M. KARP
University of California, Berkeley, California
ABSTRACT. This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem, and the general minimum-cost flow problem. Upper bounds on the numbers of steps in these algorithms are derived, and are shown to compale favorably with upper bounds on the numbers of steps required by earlier algorithms.
First, the paper states the maximum flow problem, gives the Ford-Fulkerson labeling method
for its solution, and points out that an improper choice of flow augmenting paths can lead to
Edmonds-Karp 1972 (USA)
Dinic 1970 (Soviet Union)
severe computational difficulties. Then rules of choice that avoid these difficulties are given.
We show that, if each flow augmentation is made along an augmenting path having a minimum number of arcs, then a maximum flow in an n-node network will be obtained after no more than ~(na – n) augmentations; and then we show that if each flow change is chosen to produce a maximum increase in the flow value then, provided the capacities are integral, a maximum flow will be determined within at most 1 + logM/(M–1) if(t, S) augmentations, wheref*(t, s) is the value of the maximum flow and M is the maximum number of arcs across a cut.
Next a new algorithm is given for the minimum-cost flow problem, in which all shortest-path computations are performed on networks with all weights nonnegative. In particular, this algorithm solves the n X n assigmnent problem in O(n3)steps. Following that we explore a “scaling” technique for solving a minimum-cost flow problem by treating a sequence of derived problems with “scaled down” capacities. It is shown that, using this technique, the solution of a Iiitchcock transportation problem with m sources and n sinks, m ~ n, and maximum flow B, requires at most (n + 2) log2 (B/n) flow augmentations. Similar results are also given for the general minimum-cost flow problem.
40
An abstract stating the main results of the present paper was presented at the Calgary
International Conference on Combinatorial Structures and Their Applications, June 1969. In a paper by l)inic (1970) a result closely related to the main result of Section 1.2 is obtained.
Dinic shows that, in a network with n nodes and p arcs, a maximum flow can be computed in

Capacity-scaling algorithm
Intuition. Choose augmenting path with highest bottleneck capacity: it increases flow by max possible amount in given iteration.
・Don’t worry about finding exact highest bottleneck path.
・Maintain scaling parameter Δ.
・Let G (Δ) be the subgraph of the residual graph consisting only of f
arcs with capacity ≥ Δ. ss
1
tt
Gf Gf(Δ), Δ=100
41
110
170
110
170
102
122
102
122

Capacity-scaling algorithm
CAPACITY-SCALING(G, s, t, c) __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH edgee∈E:f(e)←0. Δ ← largest power of 2 ≤ C.
WHILE (Δ ≥ 1)
Gf (Δ) ← Δ-residual graph.
WHILE (there exists an augmenting path P in Gf (Δ))
f ← AUGMENT (f, c, P).
Update Gf (Δ). Δ ← Δ / 2.
RETURN f. __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
42

Capacity-scaling algorithm: proof of correctness
Assumption. All edge capacities are integers between 1 and C. Integrality invariant. All flow and residual capacity values are integral.
Theorem. If capacity-scaling algorithm terminates, then f is a max-flow. Pf.
・By integrality invariant, when Δ = 1 ⇒ G (Δ) = G . ff
・Upon termination of Δ = 1 phase, there are no augmenting paths. ▪
43

Capacity-scaling algorithm: analysis of running time
Lemma 1. The outer while loop repeats 1 + ‘log2 C( times.
Pf. Initially C / 2 < Δ ≤ C; Δ decreases by a factor of 2 in each iteration. ▪ Lemma 2. Let f be the flow at the end of a Δ-scaling phase. Then, the value of the max-flow ≤ val(f) + m Δ. proof on next slide Lemma 3. There are at most 2m augmentations per scaling phase. P・f. ・Let f be the flow at the end of the previous scaling phase. ・LEMMA 2 ⇒ val( f *) ≤ val( f ) + 2 m Δ . Each augmentation in a Δ-phase increases val( f ) by at least Δ. ▪ Theorem. The scaling max-flow algorithm finds a max flow in O(m log C) augmentations. It can be implemented to run in O(m2 log C) time. Pf. Follows from LEMMA 1 and LEMMA 3. ▪ 44 Capacity-scaling algorithm: analysis of running time Lemma 2. Let f be the flow at the end of a Δ-scaling phase. Then, the value of the max-flow ≤ val(f) + m Δ. P・f. ・We show there exists a cut (A, B) such that cap(A, B) ≤ val(f) + m Δ. ・Choose A to be the set of nodes reachable from s in G (Δ). ・By definition of cut A, s ∈ A. By definition of flow f, t ∉ A. f edge e = (v, w) with v ∈ B, w ∈ A val(f) v(f) = v(f) = v(f) = ≥ v(f) = ≥ ≥ = ≥ = = ≥ = ≥ ≥ ≥ ∑ f(e)− ∑ f(e) eout∑ofAf(e) −ein∑toAf(e) original network A must have f(e) ≤ Δ B eout∑ofAf(e) −ein∑toAf(e) ∑(c(e)−Δ)−∑Δ ∑ f(e)− ∑ f(e) e out of A e in to A t eout∑ofA(c(e)−Δ) −ein∑toA Δ e out of A e in to A eout∑ofA(c(e)−Δ) −ein∑toA Δ ∑c(e)−∑Δ−∑Δ ∑(c(e)−Δ)−∑Δ e out of A e in to A eout∑ofAc(e)−eou∑tofAΔ−ein∑toAΔ e out of A e in to A eout∑ofAc(e)−eou∑tofAΔ−ein∑toAΔ cap(A, B) - mΔ s ∑c(e)−∑Δ−∑Δ e out of A e out of A e in to A cap(A, B) - mΔ e out of A e out of A e in to A cap(A, B) - mΔ cap(A, B) - mΔ edge e = (v, w) with v ∈ A, w ∈ B must have f(e) ≥ c(e) – Δ 45 SECTION 17.2 7. NETWORK FLOW I ‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm ‣ max-flow min-cut theorem ‣ capacity-scaling algorithm ‣ shortest augmenting paths ‣ blocking-flow algorithm ‣ unit-capacity simple networks Shortest augmenting path Q. Which augmenting path? A. The one with the fewest number of edges. can find via BFS SHORTEST-AUGMENTING-PATH(G, s, t, c) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ FOREACH e∈E:f(e)←0. Gf ←residualgraph. WHILE (there exists an augmenting path in Gf ) P ← BREADTH-FIRST-SEARCH (Gf, s, t). f ← AUGMENT (f, c, P). Update Gf. RETURN f. _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 47 Shortest augmenting path: overview of analysis L1. Throughout the algorithm, length of the shortest path never decreases. L2. After at most m shortest path augmentations, the length of the shortest augmenting path strictly increases. Theorem. The shortest augmenting path algorithm runs in O(m2 n) time. Pf. ・O(m + n) time to find shortest augmenting path via BFS. ・O(m) augmentations for paths of length k. ・If there is an augmenting path, there is a simple one. ⇒1≤k n1/2. ・Level graph has more than n1/2 levels.
Let 1 ≤ h ≤ n1/2 be layer with min number of nodes: |Vh | ≤ n1/2.
level graph LG for flow f
V0V1 Vh
Vn1/2
86

Unit-capacity simple networks: analysis
L・EMMA 2. After at most n1/2 phases, | f | ≥ | f *| – n1/2.
・After n1/2 phases, length of shortest augmenting path is > n1/2.
・Level graph has more than n1/2 levels.
・Let 1 ≤ h ≤ n1/2 be layer with min number of nodes: |Vh | ≤ n1/2.
・Let A = {v : l(v) < h} ∪ {v : l(v) = h and v has ≤ 1 outgoing residual edge}. residual graph Gf A residual edges capf(A,B) ≤ |Vh| ≤ n1/2 ⇒ |f| ≥ |f*| – n1/2. ▪ V0V1 Vh Vn1/2 87

Related Posts