Question? Leave a message!




maxflow-mincut theorem

maxflow-mincut theorem
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 6.4 MAXIMUM FLOW introduction ‣ Ford-Fulkerson algorithm ‣ maxflow-mincut theorem ‣ Algorithms FOUR TH EDITION analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣6.4 MAXIMUM FLOW introduction ‣ Ford-Fulkerson algorithm ‣ maxflow-mincut theorem ‣ Algorithms analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Mincut problem Input. An edge-weighted digraph, source vertex s, and target vertex t. each edge has a positive capacity capacity 9 15 10 4 15 10 s 8 10 t 5 15 6 10 4 15 16 3Mincut problem Def. A st-cut (cut) is a partition of the vertices into two disjoint sets, with s in one set A and t in the other set B. Def. Its capacity is the sum of the capacities of the edges from A to B. 10 s t 5 15 capacity = 10 + 5 + 15 = 30 4Mincut problem Def. A st-cut (cut) is a partition of the vertices into two disjoint sets, with s in one set A and t in the other set B. Def. Its capacity is the sum of the capacities of the edges from A to B. 10 s t 8 don't count edges from B to A 16 capacity = 10 + 8 + 16 = 34 5Mincut problem Def. A st-cut (cut) is a partition of the vertices into two disjoint sets, with s in one set A and t in the other set B. Def. Its capacity is the sum of the capacities of the edges from A to B. Minimum st-cut (mincut) problem. Find a cut of minimum capacity. 10 s t 8 10 capacity = 10 + 8 + 10 = 28 6Mincut application (RAND 1950s) "Free world" goal. Cut supplies (if cold war turns into real war). rail network connecting Soviet Union with Eastern European countries (map declassified by Pentagon in 1999) Figure 2 7 From Harris and Ross 1955: Schematic diagram of the railway network of the Western So- vietUnionandEasternEuropeancountries, withamaximumflowofvalue163,000tonsfrom Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as ‘The bottleneck’.Potential mincut application (2010s) Government-in-power’s goal. Cut off communication to set of people. 815 10 6 15 Maxflow problem Input. An edge-weighted digraph, source vertex s, and target vertex t. each edge has a positive capacity capacity 9 15 4 s t 5 8 10 15 4 16 9 10 1010 / 15 5 / 10 0 / 6 5 / 15 Maxflow problem Def. An st-flow (flow) is an assignment of values to the edges such that: Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity. Local equilibrium: inflow = outflow at every vertex (except s and t). capacity flow inflow at v = 5 + 5 + 0 = 10 5 / 9 outflow at v = 10 + 0 = 10 0 / 15 0 / 4 s t 5 / 5 5 / 8 10 / 10 0 / 15 0 / 4 10 / 16 10 10 / 10 10 / 10 v10 / 15 5 / 10 0 / 6 5 / 15 Maxflow problem Def. An st-flow (flow) is an assignment of values to the edges such that: Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity. Local equilibrium: inflow = outflow at every vertex (except s and t). Def. The value of a flow is the inflow at t. we assume no edges point to s or from t 5 / 9 0 / 15 0 / 4 s t value = 5 + 10 + 10 = 25 5 / 5 5 / 8 10 / 10 0 / 15 0 / 4 10 / 16 11 10 / 10 10 / 1013 / 15 8 / 10 3 / 6 2 / 15 Maxflow problem Def. An st-flow (flow) is an assignment of values to the edges such that: Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity. Local equilibrium: inflow = outflow at every vertex (except s and t). Def. The value of a flow is the inflow at t. Maximum st-flow (maxflow) problem. Find a flow of maximum value. 8 / 9 0 / 15 0 / 4 s t value = 8 + 10 + 10 = 28 5 / 5 8 / 8 10 / 10 0 / 15 0 / 4 13 / 16 12 10 / 10 10 / 10Maxflow application (Tolstoǐ 1930s) Soviet Union goal. Maximize flow of supplies to Eastern Europe. flow capacity rail network connecting Soviet Union with Eastern European countries (map declassified by Pentagon in 1999) Figure 2 13 From Harris and Ross 1955: Schematic diagram of the railway network of the Western So- vietUnionandEasternEuropeancountries, withamaximumflowofvalue163,000tonsfrom Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as ‘The bottleneck’.Potential maxflow application (2010s) "Free world" goal. Maximize flow of information to specified set of people. facebook graph 1413 / 15 8 / 10 3 / 6 2 / 15 Summary Input. A weighted digraph, source vertex s, and target vertex t. Mincut problem. Find a cut of minimum capacity. Maxflow problem. Find a flow of maximum value. 8 / 9 0 / 4 0 / 15 10 s 8 / 8 t s t 5 / 5 10 / 10 8 0 / 4 0 / 15 10 13 / 16 value of flow = 28 capacity of cut = 28 Remarkable fact. These two problems are dual 15 10 / 10 10 / 106.4 MAXIMUM FLOW introduction ‣ Ford-Fulkerson algorithm ‣ maxflow-mincut theorem ‣ Algorithms analysis of running time ‣ Java implementation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣0 / 15 0 / 10 0 / 6 0 / 15 Ford-Fulkerson algorithm Initialization. Start with 0 flow. flow capacity initialization 0 / 9 0 / 4 0 / 15 value of flow s 0 0 / 5 0 / 10 t 0 / 8 0 / 4 0 / 15 0 / 16 17 0 / 10 0 / 100 / 15 0 / 10 0 / 6 10 — 0 / 15 0 / 15 Idea: increase flow along augmenting paths Augmenting path. Find an undirected path from s to t such that: Can increase flow on forward edges (not full). Can decrease flow on backward edge (not empty). st 1 augmenting path bottleneck capacity = 10 0 / 9 0 / 4 0 / 15 10 s 0 + 10 = 10 0 / 5 — 0 / 10 0 / 10 t 0 / 8 0 / 4 0 / 15 0 / 16 18 10 — 0 / 10 0 / 10 0 / 1010 0 / 15 0 / 15 — 0 / 10 0 / 6 10 / 15 Idea: increase flow along augmenting paths Augmenting path. Find an undirected path from s to t such that: Can increase flow on forward edges (not full). Can decrease flow on backward edge (not empty). nd 2 augmenting path 0 / 9 0 / 4 0 / 15 s 10 + 10 = 20 0 / 5 10 / 10 t 0 / 8 0 / 4 0 / 15 10 — 0 / 16 0 / 16 19 10 / 10 10 — 0 / 10 0 / 1010 / 15 5 — 0 / 10 0 / 10 0 / 6 5 10 / 15 10 / 15 — Idea: increase flow along augmenting paths Augmenting path. Find an undirected path from s to t such that: Can increase flow on forward edges (not full). Can decrease flow on backward edge (not empty). rd 3 augmenting path backward edge 5 (not empty) — 0 / 9 0 / 9 0 / 4 0 / 15 5 5 s 20 + 5 = 25 — 0 / 5 0 / 5 — 10 / 10 t 0 / 8 0 / 8 0 / 4 0 / 15 10 / 16 20 10 / 10 10 / 10