Page 1 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Maximum Flow 2 Contents Contents. ¦ Maximum flow problem. ¦ Minimum cut problem. ¦ Max-flow min-cut theorem. ¦ Augmenting path algorithm. ¦ Capacity-scaling. ¦ Shortest augmenting path. 3 ¦ Network reliability. ¦ Security of statistical data. ¦ Distributed computing. ¦ Egalitarian stable matching. ¦ Distributed computing. ¦ Many many more . . . Maximum Flow and Minimum Cut Max flow and min cut. ¦ Two very rich algorithmic problems. ¦ Cornerstone problem in combinatorial optimization. ¦ Beautiful mathematical duality. Nontrivial applications / reductions. ¦ Network connectivity. ¦ Bipartite matching. ¦ Data mining. ¦ Open-pit mining. ¦ Airline scheduling. ¦ Image processing. ¦ Project selection. ¦ Baseball elimination. 4 Max flow network: G = (V, E, s, t, u) . ¦ (V, E) = directed graph, no parallel arcs. ¦ Two distinguished nodes: s = source, t = sink. ¦ u(e) = capacity of arc e. Max Flow Network Capacity s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Page 2 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Maximum Flow 2 Contents Contents. ¦ Maximum flow problem. ¦ Minimum cut problem. ¦ Max-flow min-cut theorem. ¦ Augmenting path algorithm. ¦ Capacity-scaling. ¦ Shortest augmenting path. 3 ¦ Network reliability. ¦ Security of statistical data. ¦ Distributed computing. ¦ Egalitarian stable matching. ¦ Distributed computing. ¦ Many many more . . . Maximum Flow and Minimum Cut Max flow and min cut. ¦ Two very rich algorithmic problems. ¦ Cornerstone problem in combinatorial optimization. ¦ Beautiful mathematical duality. Nontrivial applications / reductions. ¦ Network connectivity. ¦ Bipartite matching. ¦ Data mining. ¦ Open-pit mining. ¦ Airline scheduling. ¦ Image processing. ¦ Project selection. ¦ Baseball elimination. 4 Max flow network: G = (V, E, s, t, u) . ¦ (V, E) = directed graph, no parallel arcs. ¦ Two distinguished nodes: s = source, t = sink. ¦ u(e) = capacity of arc e. Max Flow Network Capacity s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 5 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) Flows = v e v e e f e f of out to in ) ( ) ( s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 4 0 0 0 0 0 0 0 4 4 0 4 0 0 0 Capacity Flow = ? E w v w v e w v f e f ) , ( : of out ) , ( : ) ( = ? E v w w v e v w f e f ) , ( : to in ) , ( : ) ( 6 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 4 0 0 0 0 0 0 0 4 4 0 4 0 Value = 4 = s e e f f of out ) ( 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 7 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 6 6 11 11 1 10 3 8 8 0 4 0 Value = 24 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 8 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 9 9 14 14 4 10 4 8 9 1 0 0 Value = 28 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( Page 3 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Maximum Flow 2 Contents Contents. ¦ Maximum flow problem. ¦ Minimum cut problem. ¦ Max-flow min-cut theorem. ¦ Augmenting path algorithm. ¦ Capacity-scaling. ¦ Shortest augmenting path. 3 ¦ Network reliability. ¦ Security of statistical data. ¦ Distributed computing. ¦ Egalitarian stable matching. ¦ Distributed computing. ¦ Many many more . . . Maximum Flow and Minimum Cut Max flow and min cut. ¦ Two very rich algorithmic problems. ¦ Cornerstone problem in combinatorial optimization. ¦ Beautiful mathematical duality. Nontrivial applications / reductions. ¦ Network connectivity. ¦ Bipartite matching. ¦ Data mining. ¦ Open-pit mining. ¦ Airline scheduling. ¦ Image processing. ¦ Project selection. ¦ Baseball elimination. 4 Max flow network: G = (V, E, s, t, u) . ¦ (V, E) = directed graph, no parallel arcs. ¦ Two distinguished nodes: s = source, t = sink. ¦ u(e) = capacity of arc e. Max Flow Network Capacity s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 5 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) Flows = v e v e e f e f of out to in ) ( ) ( s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 4 0 0 0 0 0 0 0 4 4 0 4 0 0 0 Capacity Flow = ? E w v w v e w v f e f ) , ( : of out ) , ( : ) ( = ? E v w w v e v w f e f ) , ( : to in ) , ( : ) ( 6 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 4 0 0 0 0 0 0 0 4 4 0 4 0 Value = 4 = s e e f f of out ) ( 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 7 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 6 6 11 11 1 10 3 8 8 0 4 0 Value = 24 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 8 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 9 9 14 14 4 10 4 8 9 1 0 0 Value = 28 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 9 Networks communication Network telephone exchanges, computers, satellites Nodes Arcs cables, fiber optics, microwave relays Flow voice, video, packets circuits gates, registers, processors wires current mechanical joints rods, beams, springs heat, energy hydraulic reservoirs, pumping stations, lakes pipelines fluid, oil financial stocks, currency transactions money transportation airports, rail yards, street intersections highways, railbeds, airway routes freight, vehicles, passengers chemical sites bonds energy 10 An s-t cut is a node partition (S, T) such that s ? S, t ? T. ¦ The capacity of an s-t cut (S, T) is: Min s-t cut: find an s-t cut of minimum capacity. Cuts ? ? ? = T w S v E w v S e w v u e u , ) , ( of out ). , ( : ) ( s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 30 11 An s-t cut is a node partition (S, T) such that s ? S, t ? T. ¦ The capacity of an s-t cut (S, T) is: Min s-t cut: find an s-t cut of minimum capacity. Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 62 ? ? ? = T w S v E w v S e w v u e u , ) , ( of out ). , ( : ) ( 12 An s-t cut is a node partition (S, T) such that s ? S, t ? T. ¦ The capacity of an s-t cut (S, T) is: Min s-t cut: find an s-t cut of minimum capacity. Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 28 ? ? ? = T w S v E w v S e w v u e u , ) , ( of out ). , ( : ) ( Page 4 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Maximum Flow 2 Contents Contents. ¦ Maximum flow problem. ¦ Minimum cut problem. ¦ Max-flow min-cut theorem. ¦ Augmenting path algorithm. ¦ Capacity-scaling. ¦ Shortest augmenting path. 3 ¦ Network reliability. ¦ Security of statistical data. ¦ Distributed computing. ¦ Egalitarian stable matching. ¦ Distributed computing. ¦ Many many more . . . Maximum Flow and Minimum Cut Max flow and min cut. ¦ Two very rich algorithmic problems. ¦ Cornerstone problem in combinatorial optimization. ¦ Beautiful mathematical duality. Nontrivial applications / reductions. ¦ Network connectivity. ¦ Bipartite matching. ¦ Data mining. ¦ Open-pit mining. ¦ Airline scheduling. ¦ Image processing. ¦ Project selection. ¦ Baseball elimination. 4 Max flow network: G = (V, E, s, t, u) . ¦ (V, E) = directed graph, no parallel arcs. ¦ Two distinguished nodes: s = source, t = sink. ¦ u(e) = capacity of arc e. Max Flow Network Capacity s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 5 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) Flows = v e v e e f e f of out to in ) ( ) ( s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 4 0 0 0 0 0 0 0 4 4 0 4 0 0 0 Capacity Flow = ? E w v w v e w v f e f ) , ( : of out ) , ( : ) ( = ? E v w w v e v w f e f ) , ( : to in ) , ( : ) ( 6 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 4 0 0 0 0 0 0 0 4 4 0 4 0 Value = 4 = s e e f f of out ) ( 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 7 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 6 6 11 11 1 10 3 8 8 0 4 0 Value = 24 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 8 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 9 9 14 14 4 10 4 8 9 1 0 0 Value = 28 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 9 Networks communication Network telephone exchanges, computers, satellites Nodes Arcs cables, fiber optics, microwave relays Flow voice, video, packets circuits gates, registers, processors wires current mechanical joints rods, beams, springs heat, energy hydraulic reservoirs, pumping stations, lakes pipelines fluid, oil financial stocks, currency transactions money transportation airports, rail yards, street intersections highways, railbeds, airway routes freight, vehicles, passengers chemical sites bonds energy 10 An s-t cut is a node partition (S, T) such that s ? S, t ? T. ¦ The capacity of an s-t cut (S, T) is: Min s-t cut: find an s-t cut of minimum capacity. Cuts ? ? ? = T w S v E w v S e w v u e u , ) , ( of out ). , ( : ) ( s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 30 11 An s-t cut is a node partition (S, T) such that s ? S, t ? T. ¦ The capacity of an s-t cut (S, T) is: Min s-t cut: find an s-t cut of minimum capacity. Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 62 ? ? ? = T w S v E w v S e w v u e u , ) , ( of out ). , ( : ) ( 12 An s-t cut is a node partition (S, T) such that s ? S, t ? T. ¦ The capacity of an s-t cut (S, T) is: Min s-t cut: find an s-t cut of minimum capacity. Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 28 ? ? ? = T w S v E w v S e w v u e u , ) , ( of out ). , ( : ) ( 13 L1. Let f be a flow, and let (S, T) be a cut. Then, the net flow sent across the cut is equal to the amount reaching t. Flows and Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 f e f e f e f s e S e S e = = - of out to in of out ) ( ) ( ) ( Value = 24 10 6 6 10 10 0 10 4 8 8 0 4 0 0 0 14 10 6 6 10 10 0 10 4 8 8 0 4 0 0 0 L1. Let f be a flow, and let (S, T) be a cut. Then, the net flow sent across the cut is equal to the amount reaching t. Flows and Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 f e f e f e f s e S e S e = = - of out to in of out ) ( ) ( ) ( Value = 24 15 10 6 6 10 10 0 10 4 8 8 0 4 0 0 L1. Let f be a flow, and let (S, T) be a cut. Then, the net flow sent across the cut is equal to the amount reaching t. Flows and Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 f e f e f e f s e S e S e = = - of out to in of out ) ( ) ( ) ( Value = 24 0 16 Let f be a flow, and let (S, T) be a cut. Then, Proof by induction on |S|. ¦ Base case: S = { s }. ¦ Inductive hypothesis: assume true for |S| < k. – consider cut (S, T) with |S| = k – S = S’ ¨ { v } for some v „ s, t, |S’ | = k-1 cap(S’, T’) = | f |. – adding v to S’ increase cut capacity by Flows and Cuts . ) ( ) ( to in of out = - S e S e f e f e f 0 ) ( ) ( to in of out = - v e v e e f e f s v t After s v t S’ Before S Page 5 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Maximum Flow 2 Contents Contents. ¦ Maximum flow problem. ¦ Minimum cut problem. ¦ Max-flow min-cut theorem. ¦ Augmenting path algorithm. ¦ Capacity-scaling. ¦ Shortest augmenting path. 3 ¦ Network reliability. ¦ Security of statistical data. ¦ Distributed computing. ¦ Egalitarian stable matching. ¦ Distributed computing. ¦ Many many more . . . Maximum Flow and Minimum Cut Max flow and min cut. ¦ Two very rich algorithmic problems. ¦ Cornerstone problem in combinatorial optimization. ¦ Beautiful mathematical duality. Nontrivial applications / reductions. ¦ Network connectivity. ¦ Bipartite matching. ¦ Data mining. ¦ Open-pit mining. ¦ Airline scheduling. ¦ Image processing. ¦ Project selection. ¦ Baseball elimination. 4 Max flow network: G = (V, E, s, t, u) . ¦ (V, E) = directed graph, no parallel arcs. ¦ Two distinguished nodes: s = source, t = sink. ¦ u(e) = capacity of arc e. Max Flow Network Capacity s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 5 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) Flows = v e v e e f e f of out to in ) ( ) ( s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 4 0 0 0 0 0 0 0 4 4 0 4 0 0 0 Capacity Flow = ? E w v w v e w v f e f ) , ( : of out ) , ( : ) ( = ? E v w w v e v w f e f ) , ( : to in ) , ( : ) ( 6 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 4 0 0 0 0 0 0 0 4 4 0 4 0 Value = 4 = s e e f f of out ) ( 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 7 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 6 6 11 11 1 10 3 8 8 0 4 0 Value = 24 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 8 An s-t flow is a function f: E ?´ that satisfies: ¦ For each e ? E: 0 £ f(e) £ u(e) (capacity) ¦ For each v ? V – {s, t}: (conservation) MAX FLOW: find s-t flow that maximizes net flow out of the source. Flows s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 9 9 14 14 4 10 4 8 9 1 0 0 Value = 28 0 0 Capacity Flow = v e v e e f e f of out to in ) ( ) ( 9 Networks communication Network telephone exchanges, computers, satellites Nodes Arcs cables, fiber optics, microwave relays Flow voice, video, packets circuits gates, registers, processors wires current mechanical joints rods, beams, springs heat, energy hydraulic reservoirs, pumping stations, lakes pipelines fluid, oil financial stocks, currency transactions money transportation airports, rail yards, street intersections highways, railbeds, airway routes freight, vehicles, passengers chemical sites bonds energy 10 An s-t cut is a node partition (S, T) such that s ? S, t ? T. ¦ The capacity of an s-t cut (S, T) is: Min s-t cut: find an s-t cut of minimum capacity. Cuts ? ? ? = T w S v E w v S e w v u e u , ) , ( of out ). , ( : ) ( s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 30 11 An s-t cut is a node partition (S, T) such that s ? S, t ? T. ¦ The capacity of an s-t cut (S, T) is: Min s-t cut: find an s-t cut of minimum capacity. Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 62 ? ? ? = T w S v E w v S e w v u e u , ) , ( of out ). , ( : ) ( 12 An s-t cut is a node partition (S, T) such that s ? S, t ? T. ¦ The capacity of an s-t cut (S, T) is: Min s-t cut: find an s-t cut of minimum capacity. Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 28 ? ? ? = T w S v E w v S e w v u e u , ) , ( of out ). , ( : ) ( 13 L1. Let f be a flow, and let (S, T) be a cut. Then, the net flow sent across the cut is equal to the amount reaching t. Flows and Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 f e f e f e f s e S e S e = = - of out to in of out ) ( ) ( ) ( Value = 24 10 6 6 10 10 0 10 4 8 8 0 4 0 0 0 14 10 6 6 10 10 0 10 4 8 8 0 4 0 0 0 L1. Let f be a flow, and let (S, T) be a cut. Then, the net flow sent across the cut is equal to the amount reaching t. Flows and Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 f e f e f e f s e S e S e = = - of out to in of out ) ( ) ( ) ( Value = 24 15 10 6 6 10 10 0 10 4 8 8 0 4 0 0 L1. Let f be a flow, and let (S, T) be a cut. Then, the net flow sent across the cut is equal to the amount reaching t. Flows and Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 f e f e f e f s e S e S e = = - of out to in of out ) ( ) ( ) ( Value = 24 0 16 Let f be a flow, and let (S, T) be a cut. Then, Proof by induction on |S|. ¦ Base case: S = { s }. ¦ Inductive hypothesis: assume true for |S| < k. – consider cut (S, T) with |S| = k – S = S’ ¨ { v } for some v „ s, t, |S’ | = k-1 cap(S’, T’) = | f |. – adding v to S’ increase cut capacity by Flows and Cuts . ) ( ) ( to in of out = - S e S e f e f e f 0 ) ( ) ( to in of out = - v e v e e f e f s v t After s v t S’ Before S 17 L2. Let f be a flow, and let (S, T) be a cut. Then, | f | £ cap(S, T). Proof. Corollary. Let f be a flow, and let (S, T) be a cut. If |f| = cap(S, T), then f is a max flow and (S, T) is a min cut. Flows and Cuts T) cap(S, ) ( ) ( ) ( ) ( of out of out to in of out = £ £ - = S e S e S e S e e u e f e f e f f s t S T 7 6 8 4 18 Max Flow and Min Cut Corollary. Let f be a flow, and let (S, T) be a cut. If |f| = cap(S, T), then f is a max flow and (S, T) is a min cut. s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 9 9 15 15 4 10 4 8 9 1 0 0 Flow value = 28 0 0 Cut capacity = 28 19 Max-Flow Min-Cut Theorem MAX-FLOW MIN-CUT THEOREM (Ford-Fulkerson, 1956): In any network, the value of the max flow is equal to the value of the min cut. ¦ "Good characterization." ¦ Proof IOU. s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 10 9 9 15 15 4 10 4 8 9 1 0 0 Flow value = 28 0 0 Cut capacity = 28 20 Towards an Algorithm Find an s-t path where each arc has u(e) > f(e) and "augment" flow along the path. s 4 2 5 3 t 4 0 0 0 0 0 0 4 0 4 4 Flow value = 0 10 13 10Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!