Lecture Algorithm design - Chapter 7: Network flow I

Chia sẻ: You Can | Ngày: | Loại File: PDF | Số trang:87

Thêm vào BST

Báo xấu

50
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Lecture Algorithm design - Chapter 7 "Network flow I" include all of the following: 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lecture Algorithm design - Chapter 7: Network flow I

7. N ETWORK F LOW 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
7. N ETWORK F LOW 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 SECTION 7.1
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. no parallel edges no edge enters s no edge leaves t capacity 9 4 15 15 10 10 s 5 8 10 t 15 4 6 15 10 16 3
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 s 5 t 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. cap( A, B) = ∑ c(e) e out of A € 10 s 8 t don't count edges from B to A 16 capacity = 10 + 8 + 16 = 34 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. cap( A, B) = ∑ c(e) e out of A Min-cut problem. Find a cut of minimum capacity. € 10 s 8 t 10 capacity = 10 + 8 + 10 = 28 6
Maximum flow problem Def. 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 [flow conservation] € € flow capacity inflow at v = 5 + 5 + 0 = 10 5/9 outflow at v = 10 + 0 = 10 5 5 10 0/4 /1 0 / 15 / 10 / 5 10 s 5/5 5/8 v 10 / 10 t 10 / 0 0 / 15 10 15 0/4 /6 / 10 10 / 16 7
Maximum flow problem Def. 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 [flow conservation] Def. The value of a€flow f is:v(val( f ) f=) = ∑ f (e) . e out of s € € 5/9 5 5 10 0/4 /1 0 / 15 / 10 / 5 10 s 5/5 5/8 10 / 10 t 10 / 0 0 / 15 10 15 0/4 /6 / 10 value = 5 + 10 + 10 = 25 10 / 16 8
Maximum flow problem Def. 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 [flow conservation] Def. The value of a€flow f is:v(val( f ) f=) = ∑ f (e) . e out of s € Max-flow problem. Find a flow of maximum value. € 8/9 2 8 10 0/4 /1 0 / 15 / 10 / 5 10 s 5/5 8/8 10 / 10 t 13 / 3 0 / 15 10 15 0/4 /6 / 10 value = 8 + 10 + 10 = 28 13 / 16 9
7. N ETWORK F LOW 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 SECTION 7.1
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 0 0 / 10 0/2 /8 0/6 10 / 0 value of flow s 0 / 10 0/9 0 / 10 t 0 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. network G 0/4 8 — 0 0 / 8 10 0/2 /8 0/6 10 / 0 — 8 s 0 / 10 0/9 — 0 / 10 t 0 +8=8 12
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 8 / 10 10 2 — 0/2 /8 0/6 10 / 8 — 2 2 s 0 / 10 — 0/9 — 8 / 10 t 8 + 2 = 10 13
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 6 — 0 10 2/2 8 /8 6 — 0/6 / / 10 10 6 8 s — 0 / 10 — 2/9 10 / 10 t 10 + 6 = 16 14
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. ending flow value = 16 network G 0/4 6 10 2/2 8 /8 6/6 / / 10 10 s 6 / 10 8/9 10 / 10 t 16 15
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 9 10 0/2 7 /8 6/6 / / 10 10 s 9 / 10 9/9 10 / 10 t 19 16
Residual graph Original edge: e = (u, v) ∈ E. original graph G ・Flow f (e). u 6 / 17 v ・Capacity c(e). flow capacity Residual edge. ・"Undo" flow sent. ・e = (u, v) and eR = (v, u). residual graph Gf residual ・Residual capacity: capacity u 11 v ⎧c(e) − f (e) if e ∈ E 6 c f (e) = ⎨ ⎩ f (e) if e R ∈ E Residual graph: Gf = (V, Ef ). € ・Residual edges with positive residual capacity. negates where flow on a reverse edge flow on a forward edge ・Ef = {e : f (e) < c(e)} ∪ {e : f (e) > 0}. R ・Key property: f ' is a flow in Gf iff f + f ' is a flow in G. 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 IF (e ∈ E ) f (e) ← f (e) + b. ELSE f (eR) ← f (eR) – b. RETURN f. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 18
Ford-Fulkerson algorithm Ford-Fulkerson augmenting path algorithm. ・Start with f (e) = 0 for all edge e ∈ E. ・Find an augmenting path P in the residual graph Gf . ・Augment flow along path P. ・Repeat until you get stuck. FORD-FULKERSON (G, s, t, c) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ FOREACH edge e ∈ E : f (e) ← 0. Gf ← residual graph. 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/4 0 0 / 10 0/2 /8 0/6 10 / 0 value of flow s 0 / 10 0/9 0 / 10 t 0 residual graph Gf 4 residual capacity 8 10 2 6 10 s 10 9 10 t 20