Network Flow Applications and Minimum s-t Cut Problem
Explore the concepts of network flow applications, minimum s-t cut problem, and s-t flows in combinatorial optimization. Learn about max flow, min cut, mathematical duality, and various applications such as data mining, project selection, and image segmentation. Dive into the Soviet Rail Network visualization and understand the goal of finding the minimum capacity cut in a directed graph to separate source and sink nodes effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE 421 Max Flow Min Cut Problem Yin Tat Lee 1
Soviet Rail Network Unclassified on May 21, 1999.
Network Flow Applications Max flow and min cut. Two very rich algorithmic problems. Cornerstone problems in combinatorial optimization. Beautiful mathematical duality. Nontrivial applications / reductions. Data mining. Project selection. Airline scheduling. Bipartite matching. Baseball elimination. Image segmentation. Network connectivity. 3
Minimum s-t Cut Problem Given a directed graph G = (V, E) = directed graph and two distinguished nodes: s = source, t = sink. Suppose each directed edge e has a nonnegative capacity ?(?) Goal: Find a cut separating ?,? that cuts the minimum capacity of edges. 2 9 5 10 15 15 10 4 source sink 5 8 10 s 3 6 t 15 4 6 10 15 capacity 30 4 7 4
s-t cuts Def. An s-t cut is a partition (A, B) of V with s A and t B. Def. The capacity of a cut (A, B): ??? ?,? = ?,? :? ?,? ??(?,?) ???????? = 10 + 5 + 15 = 30 9 2 5 10 15 15 10 4 5 8 10 s 3 6 t A 15 4 6 10 15 30 5 4 7
s-t cuts Def. An s-t cut is a partition (A, B) of V with s A and t B. Def. The capacity of a cut (A, B): ??? ?,? = ?,? :? ?,? ??(?,?) ???????? = 9 + 15 + 8 + 30 = 62 9 2 5 10 15 15 10 4 5 8 10 s 3 6 t A 15 4 6 10 15 30 6 4 7
Minimum s-t Cut Problem Given a directed graph G = (V, E) = directed graph and two distinguished nodes: s = source, t = sink. Suppose each directed edge e has a nonnegative capacity ?(?) Goal: Find a s-t cut of minimum capacity 9 2 5 ???????? = 10 + 8 + 10 = 28 10 15 15 10 4 source sink 5 8 10 s 3 6 t 15 4 6 10 15 capacity 30 4 7 7
s-t Flows Def. An s-t flow is a function that satisfies: For each ? ?:0 ? ? ?(?) For each ? ? {?,?}: ? in to ??(?) = ? out of ??(?) (conservation) (capacity) Def. The value of a flow f is: ? ? = ? out of ??(?) 0 9 2 5 4 0 0 10 15 15 0 10 4 4 0 5 4 4 8 10 s 3 6 t 0 0 0 15 4 6 0 10 capacity flow 15 0 Value = 4 0 30 8 4 7
s-t Flows Def. An s-t flow is a function that satisfies: For each ? ?:0 ? ? ?(?) For each ? ? {?,?}: ? in to ??(?) = ? out of ??(?) (conservation) (capacity) Def. The value of a flow f is: ? ? = ? out of ??(?) 6 9 2 5 10 6 0 10 15 15 0 10 4 4 3 5 8 8 8 10 s 3 6 t 1 10 0 15 4 6 0 10 capacity flow 15 11 Value = 24 11 30 9 4 7
Maximum s-t Flow Problem Goal: Find a s-t flow of largest value. 9 9 2 5 10 9 1 10 15 15 0 10 0 4 4 5 9 8 8 10 s 3 6 t 4 10 0 15 4 6 0 10 capacity flow 15 14 Value = 28 14 10 30 4 7
Flows and Cuts Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s. ? ? ? ? = ?(?) ? out of ? ? in to ? 6 9 2 5 10 6 0 10 15 15 0 10 4 4 3 5 8 8 8 10 s 3 6 t 1 10 0 15 4 6 0 10 capacity flow 15 11 Value = 24 11 30 11 4 7
Proof of Flow value Lemma Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s. ? ? ? ? = ?(?) ? out of ? ? in to ? Proof. ? ? = ?(?) ? out of ? = ? ? ?(?) By conservation of flow, all terms except v=s are 0 ? ? ? out of ? ? in to ? All contributions due to internal edges cancel out = ? ? ?(?) ? out of ? ? in to ? 12
Weak Duality of Flows and Cuts Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut. ? ? ???(?,?) v(f)=24, capacity=9+15+8+30=62 6 9 2 5 10 6 0 10 15 15 0 10 4 4 3 5 8 8 8 10 s 3 6 t 1 10 0 15 4 6 0 10 capacity flow 15 11 11 30 13 4 7
Weak Duality of Flows and Cuts Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut. ? ? ???(?,?) Proof. A B ? ? = ? ? ?(?) 4 ? ??? ?? ? ? ?? ?? ? 8 t 6 5 ?(?) s ? ??? ?? ? 7 6 ? ? = ???(?,?) ? ??? ?? ? 14
Certificate of Optimality Corollary: Suppose there is a s-t cut (A,B) such that ? ? = ??? ?,? Then, f is a maximum flow and (A,B) is a minimum cut. v(f)=28, cap(A,B)=28 9 2 5 10 9 1 10 15 15 0 10 0 4 4 5 9 8 8 10 s 3 6 t 4 10 0 15 4 6 0 10 capacity flow 15 14 14 15 30 4 7
A Greedy Algorithm for Max Flow 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. 1 20 0 0 20 10 20 t s 30 0 10 0 20 0 20 2 16
A Greedy Algorithm for Max Flow 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. 1 1 20 0 20 10 20 10 20 10 t t s s 30 20 30 10 10 0 20 20 10 10 20 20 2 2 Greedy = 20 OPT = 30 17
Residual Graph capacity Original edge: e = (u, v) E. Flow f(e), capacity c(e). Residual edge. "Undo" flow sent. e = (u, v) and eR = (v, u). Residual capacity: u v 17 6 flow residual capacity u v 11 ??? = ? ? ? ? ?? ? ? ? ? 6 ?? ?? ? residual capacity Residual graph: Gf = (V, Ef ). Residual edges with positive residual capacity. ?? = ? ? ? < ? ? {??: ?(?) > 0}. 18
Ford-Fulkerson Alg: Greedy on Gf 0 2 4 4 capacity 0 0 G: 0 6 0 8 10 10 2 0 10 s 3 5 t 10 9 0 0 0 Find Path 2 4 4 Gf: 6 8 10 10 2 10 s 3 5 t 10 9 19
Ford-Fulkerson Alg: Greedy on Gf 4 Update Flow 2 4 4 capacity 4 4 G: 0 6 0 8 10 10 2 0 10 s 3 5 t 10 9 0 0 0 2 4 4 Gf: 6 8 10 10 2 10 s 3 5 t 10 9 20
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 4 4 G: 0 6 0 8 10 10 2 0 10 s 3 5 t 10 9 0 0 0 4 Update Residual 2 4 Gf: 4 4 6 8 6 6 2 10 s 3 5 t 10 9 21
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 4 4 G: 0 6 0 8 10 10 2 0 10 s 3 5 t 10 9 0 0 0 4 Find Path 2 4 Gf: 4 4 6 8 6 6 2 10 s 3 5 t 10 9 22
Ford-Fulkerson Alg: Greedy on Gf 4 Update Flow 2 4 4 capacity 6 4 G: 0 6 0 8 10 10 2 2 10 s 3 5 t 10 9 2 2 0 4 2 4 Gf: 4 4 6 8 6 6 2 10 s 3 5 t 10 9 23
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 6 4 G: 0 6 0 8 10 10 2 2 10 s 3 5 t 10 9 2 2 0 4 Update Residual 2 4 Gf: 6 4 6 8 6 4 2 10 s 3 5 t 8 2 7 2 24
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 6 4 G: 0 6 0 8 10 10 2 2 10 s 3 5 t 10 9 2 2 0 4 Find Path 2 4 Gf: 6 4 6 8 6 4 2 10 8 s 3 5 t 7 2 2 25
Ford-Fulkerson Alg: Greedy on Gf Update Flow 4 2 4 4 capacity 10 4 G: 4 6 0 8 10 10 2 2 10 s 3 5 t 10 6 9 2 0 4 2 4 Gf: 6 4 6 8 6 4 2 10 8 s 3 5 t 7 2 2 26
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 10 4 G: 4 6 0 8 10 10 2 2 10 s 3 5 t 10 6 9 2 0 Update Residual 4 2 4 4 Gf: 10 4 6 4 6 2 10 4 s 3 5 t 7 2 6 27
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 10 4 G: 4 6 0 8 10 10 2 2 10 s 3 5 t 10 6 9 2 0 Find Path 4 2 4 4 Gf: 10 4 6 4 6 2 10 4 s 3 5 t 7 2 6 28
Ford-Fulkerson Alg: Greedy on Gf 4 Update Flow 2 4 4 capacity 10 6 G: 6 6 2 8 10 10 2 0 10 s 3 5 t 10 6 9 2 2 4 2 4 4 Gf: 10 4 6 4 6 2 10 4 s 3 5 t 7 2 6 29
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 10 6 G: 6 6 2 8 10 10 2 0 10 s 3 5 t 10 6 9 2 2 4 Update Residual 2 4 6 Gf: 10 6 4 2 4 2 2 8 4 s 3 5 t 7 2 2 6 30
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 10 6 G: 6 6 2 8 10 10 2 0 10 s 3 5 t 10 6 9 2 2 4 Find Path 2 4 6 Gf: 10 6 4 2 4 2 2 4 7 8 s 3 5 t 2 6 2 31
Ford-Fulkerson Alg: Greedy on Gf Update Flow 4 2 4 4 capacity 10 6 G: 6 6 2 8 10 10 2 0 10 s 3 5 t 10 10 9 6 6 4 2 4 6 Gf: 10 6 4 2 4 2 2 4 7 8 s 3 5 t 2 6 2 32
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 10 6 G: 6 6 2 8 10 10 2 0 10 s 3 5 t 10 10 9 6 6 Update Residual 4 2 4 6 Gf: 10 6 4 2 4 2 2 3 4 s 3 5 t 6 10 6 33
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 10 6 G: 6 6 2 8 10 10 2 0 10 s 3 5 t 10 10 9 6 6 Find Path 4 2 4 6 Gf: 10 6 4 2 4 2 2 3 4 s 3 5 t 6 10 6 34
Ford-Fulkerson Alg: Greedy on Gf 4 Update FLow 2 4 4 capacity 10 9 G: 6 6 5 8 10 10 2 0 10 9 s 3 5 t 10 10 9 9 4 2 4 6 Gf: 10 6 4 2 4 2 2 3 4 s 3 5 t 6 10 6 35
Ford-Fulkerson Alg: Greedy on Gf 4 2 4 4 capacity 10 9 G: 6 6 5 8 10 10 2 0 10 9 s 3 5 t 10 10 9 9 4 Find Path 2 4 6 Gf: 10 9 1 2 1 2 5 1 s 3 5 t 9 10 9 36
