Princeton University • COS 226 • Algorithms and Data Structures • Spring 2004 • Kevin Wayne • http://www.Princeton.EDU/~cos226Max Flow, Min CutMinimum cutMaximum flowMax-flow min-cut theoremFord-Fulkerson augmenting path algorithmEdmonds-Karp heuristicsBipartite matching2n Network reliability.n Security of statistical data.n Distributed computing.n Egalitarian stable matching.n Distributed computing.n Many many more . . .Maximum Flow and Minimum CutMax flow and min cut.n Two very rich algorithmic problems.n Cornerstone problems in combinatorial optimization.n Beautiful mathematical duality.Nontrivial applications / reductions.n Network connectivity.n Bipartite matching.n Data mining.n Open-pit mining. n Airline scheduling.n Image processing.n Project selection.n Baseball elimination.3Soviet Rail Network, 1955Source: On the history of the transportation and maximum flow problems.Alexander Schrijver in Math Programming, 91: 3, 2002.4Network: abstraction for material FLOWING through the edges.n Directed graph.n Capacities on edges.n Source node s, sink node t.Min cut problem. Delete "best" set of edges to disconnect t from s.Minimum Cut Problemcapacitys234567t155301510815961010101544sinksource5A cut is a node partition (S, T) such that s is in S and t is in T.n capacity(S, T) = sum of weights of edges leaving S.Cutss234567t155301510815961010101544Capacity = 30S6A cut is a node partition (S, T) such that s is in S and t is in T.n capacity(S, T) = sum of weights of edges leaving S.Cutss234567t155301510815961010101544SCapacity = 627A cut is a node partition (S, T) such that s is in S and t is in T.n capacity(S, T) = sum of weights of edges leaving S.Min cut problem. Find an s-t cut of minimum capacity.Minimum Cut Problems234567t155301510815961010101544SCapacity = 288Network: abstraction for material FLOWING through the edges.n Directed graph.n Capacities on edges.n Source node s, sink node t.Max flow problem. Assign flow to edges so as to:n Equalize inflow and outflow at every intermediate vertex.n Maximize flow sent from s to t.Maximum Flow Problemsame input as min cut problems234567t155301510815961010101544capacitysinksource9A flow f is an assignment of weights to edges so that:n Capacity: 0 £ f(e) £ u(e). n Flow conservation: flow leaving v = flow entering v.Flowss234567t15530151081596101010154440000004404000Value = 4except at s or t0capacityflow10A flow f is an assignment of weights to edges so that:n Capacity: 0 £ f(e) £ u(e). n Flow conservation: flow leaving v = flow entering v.Flowss234567t15530151081596101010154410661111038804000Value = 2411capacityflowexcept at s or t11Max flow problem: find flow that maximizes net flow into sink.Maximum Flow Problems234567t15530151081596101010154410991441048910000Value = 2814capacityflow12Observation 1. Let f be a flow, and let (S, T) be any s-t cut. Then, the net flow sent across the cut is equal to the amount reaching t.Flows and Cutss234567t155301510815961010101544106601048804000S1010Value = 24131066100104880400Observation 1. Let f be a flow, and let (S, T) be any s-t cut. Then, the net flow sent across the cut is equal to the amount reaching t.Flows and Cutss234567t155301510815961010101544S010Value = 24141066100104880400Observation 1. Let f be a flow, and let (S, T) be any s-t cut. Then, the net flow sent across the cut is equal to the amount reaching t.Flows and Cutss234567t1553015108159610101015440S10Value = 2415Observation 2. Let f be a flow, and let (S, T) be any s-t cut. Then the value of the flow is at most the capacity of the cut.Flows and Cutss234567t155301510815961010101544SCut capacity = 30 Þ Flow value £ 3016Max Flow and Min CutObservation 3. Let f be a flow, and let (S, T) be an s-t cut whose capacity equals the value of f. Then f is a max flow and (S, T) is a min cut.Cut capacity = 28 Þ Flow value £ 28Flow value = 28s234567t15530151081596101010154410991541048910000S1517Max-Flow Min-Cut TheoremMax-flow min-cut theorem. (Ford-Fulkerson, 1956): In any network, the value of max flow equals capacity of min cut.n Proof IOU: we find flow and cut such that Observation 3 applies.Min cut capacity = 28 Û Max flow value = 28s234567t15530151081596101010154410991541048910000S1518Towards an AlgorithmFind s-t path where each arc has f(e) < u(e) and "augment" flow along it.s4253 t40000004044101310Flow value = 0flowcapacity19Towards an AlgorithmFind s-t path where each arc has f(e) < u(e) and "augment" flow along it.n Greedy algorithm: repeat until you get stuck.s4253 t40000004044101310101010XXXFlow value = 10Bottleneck capacity of path = 10flowcapacity20Towards an AlgorithmFind s-t path where each arc has f(e) < u(e) and "augment" flow along it.n Greedy algorithm: repeat until you get stuck.n Fails: need to be able to "backtrack."s4253 t1013104441061044444Flow value = 10Flow value = 14s4253 t40000004044101310101010XXXflowcapacity21Residual GraphOriginal graph.n Flow f(e).n Edge e = v-wResidual edge.n Edge e = v-w or w-v.n "Undo" flow sent.Residual graph.n All the edges that havestrictly positive residual capacity.v w176capacity = u(e)v w116residual capacity = u(e) – f(e)residual capacity = f(e)flow = f(e)22Augmenting PathsAugmenting path = path in residual graph.n Increase flow along forward edges.n Decrease flow along backward edges.s4253 t10131040010101004044s4253 t1010104444344644XXXXXoriginalresidual23Augmenting PathsObservation 4. If augmenting path, then not yet a max flow.Q. If no augmenting path, is it a max flow?Flow value = 14s4253 t1061044447residuals4253 t10131040010101004044original44644XXXXX24Ford-Fulkerson Augmenting Path AlgorithmFord-Fulkerson algorithm. Generic method for solving max flow.Questions.n Does this lead to a maximum flow? yes n How do we find an augmenting path? s-t path in residual graphn How many augmenting paths does it take?n How much effort do we spending finding a path?while (there exists an augmenting path) {Find augmenting path PCompute bottleneck capacity of PAugment flow along P}25Max-Flow Min-Cut TheoremAugmenting path theorem. A flow f is a max flow if and only if there are no augmenting paths. We prove both simultaneously by showing the following are equivalent:(i) f is a max flow.(ii) There is no augmenting path relative to f.(iii) There exists a cut whose capacity equals the value of f. (i) Þ (ii) equivalent to not (ii) Þ not (i), which was Observation 4(ii) Þ (iii) next slide(iii) Þ (i) this was Observation
View Full Document
Unlocking...