Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 22 Prof. Charles E. Leiserson Introduction to Algorithms Day 38 L22.2? 2001 by Charles E. Leiserson Flow networks Definition. A flow network is a directed graph G = (V, E) with two distinguished vertices: a source s and a sink t. Each edge (u, v) ∈ E has a nonnegative capacity c(u, v). If (u, v) ? E, then c(u, v) = 0. Example: s s t t 3 2 3 32 2 3 3 1 2 1 Introduction to Algorithms Day 38 L22.3? 2001 by Charles E. Leiserson Flow networks Definition. A positive flow on G is a function p : V × V →R satisfying the following: ? Capacity constraint: For all u, v ∈ V, 0 ≤ p(u, v) ≤ c(u, v). ? Flow conservation: For all u ∈ V –{s, t}, 0),(),( =? ∑∑ ∈∈ VvVv uvpvup . The value of a flow is the net flow out of the source: ∑∑ ∈∈ ? VvVv svpvsp ),(),( . Introduction to Algorithms Day 38 L22.4? 2001 by Charles E. Leiserson A flow on a network s s t t 1:3 2:2 2:3 1 : 1 2:3 1:2 1:2 2:3 1:3 0:1 2:2 positive flow capacity The value of this flow is 1 – 0 + 2 = 3. Flow conservation (like Kirchoff’s current law): ? Flow into u is 2 + 1 = 3. ? Flow out of u is 0 + 1 + 2 = 3. u Introduction to Algorithms Day 38 L22.5? 2001 by Charles E. Leiserson The maximum-flow problem s s t t 2:3 2:2 2:3 1 : 1 2:3 1:2 2:2 3:3 0:3 0:1 2:2 The value of the maximum flow is 4. Maximum-flow problem: Given a flow network G, find a flow of maximum value on G. Introduction to Algorithms Day 38 L22.6? 2001 by Charles E. Leiserson Flow cancellation Without loss of generality, positive flow goes either from u to v, or from v to u, but not both. v v u u 2:3 1:2 v v u u 1:3 0:2 Net flow from u to v in both cases is 1. The capacity constraint and flow conservation are preserved by this transformation. INTUITION: View flow as a rate, not a quantity. Introduction to Algorithms Day 38 L22.7? 2001 by Charles E. Leiserson One summation instead of two. A notational simplification IDEA: Work with the net flow between two vertices, rather than with the positive flow. Definition. A (net) flow on G is a function f : V × V →R satisfying the following: ? Capacity constraint: For all u, v ∈ V, f (u, v) ≤ c(u, v). ? Flow conservation: For all u ∈ V –{s, t}, 0),( = ∑ ∈Vv vuf . ? Skew symmetry: For all u, v ∈ V, f (u, v) = –f (v, u). Introduction to Algorithms Day 38 L22.8? 2001 by Charles E. Leiserson Equivalence of definitions Theorem. The two definitions are equivalent. Proof. (?) Let f (u, v) = p(u, v) – p(v, u). ? Capacity constraint: Since p(u, v) ≤ c(u, v) and p(v, u) ≥ 0, we have f (u, v) ≤ c(u, v). ? Flow conservation: ( ) ∑∑ ∑∑ ∈∈ ∈∈ ?= ?= VvVv VvVv uvpvup uvpvupvuf ),(),( ),(),(),( ? Skew symmetry: f (u, v)= p(u, v) – p(v, u) = – (p(v, u) – p(u, v)) = – f (v, u). Introduction to Algorithms Day 38 L22.9? 2001 by Charles E. Leiserson Proof (continued) (?) Let p(u, v) = f (u, v) if f(u, v) > 0, 0 if f(u, v) ≤ 0. ? Capacity constraint: By definition, p(u, v) ≥ 0. Since f (u, v) ≤ c(u, v), it follows that p(u, v) ≤ c(u, v). ? Flow conservation: If f (u, v) > 0, then p(u, v) – p(v, u) = f (u, v). If f (u, v) ≤ 0, then p(u, v) – p(v, u) = – f (v, u) = f (u, v) by skew symmetry. Therefore, ∑∑∑ ∈∈∈ =? VvVvVv vufuvpvup ),(),(),( . Introduction to Algorithms Day 38 L22.10? 2001 by Charles E. Leiserson Notation Definition. The value of a flow f, denoted by |f |, is given by ),( ),( Vsf vsff Vv = = ∑ ∈ . Implicit summation notation: A set used in an arithmetic formula represents a sum over the elements of the set. ? Example — flow conservation: f (u, V) = 0 for all u ∈ V –{s, t}. Introduction to Algorithms Day 38 L22.11? 2001 by Charles E. Leiserson Simple properties of flow Lemma. ? f (X, X) = 0, ? f (X, Y) = – f (Y, X), ? f (X∪Y, Z) = f (X, Z) + f (Y, Z) if X∩Y = ?. Theorem. | f | = f (V, t). Proof. | f |= f (s, V) = f (V, V) – f (V–s, V) Omit braces. = f (V, V–s) = f (V, t) + f (V, V–s–t) = f (V, t). Introduction to Algorithms Day 38 L22.12? 2001 by Charles E. Leiserson Flow into the sink s s t t 2:3 2:2 2:3 1 : 1 1:3 0:2 2:2 3:3 0:3 0:1 2:2 | f | = f (s, V) = 4 f (V, t) = 4 Introduction to Algorithms Day 38 L22.13? 2001 by Charles E. Leiserson Cuts Definition. A cut (S, T) of a flow network G = (V, E) is a partition of V such that s ∈ S and t ∈ T. If f is a flow on G, then the flow across the cut is f (S, T). s s t t 2:3 2:2 2:3 1 : 1 1:3 0:2 2:2 3:3 0:3 0:1 2:2 ∈ S ∈ T f (S, T) = (2 + 2) + (– 2 + 1 – 1 + 2) = 4 Introduction to Algorithms Day 38 L22.14? 2001 by Charles E. Leiserson Another characterization of flow value Lemma. For any flow f and any cut (S, T), we have | f | = f (S, T). Proof. f (S, T)= f (S, V) – f (S, S) = f (S, V) = f (s, V) + f (S–s, V) = f (s, V) = | f |. Introduction to Algorithms Day 38 L22.15? 2001 by Charles E. Leiserson Capacity of a cut Definition. The capacity of a cut (S, T) is c(S, T). s s t t 2:3 2:2 2:3 1 : 1 1:3 0:2 2:2 3:3 0:3 0:1 2:2 ∈ S ∈ T c(S, T) = (3 + 2) + (1 + 2 + 3) = 11 Introduction to Algorithms Day 38 L22.16? 2001 by Charles E. Leiserson Upper bound on the maximum flow value Theorem. The value of any flow is bounded above by the capacity of any cut. .),( ),( ),( ),( TSc vuc vuf TSff SuTv SuTv = ≤ = = ∑∑ ∑∑ ∈∈ ∈∈ Proof. Introduction to Algorithms Day 38 L22.17? 2001 by Charles E. Leiserson Residual network Definition. Let f be a flow on G = (V, E). The residual network G f (V, E f ) is the graph with strictly positive residual capacities c f (u, v) = c(u, v) – f (u, v) > 0. Edges in E f admit more flow. u u v v 0:1 3:5 G: u u v v 4 2 G f : Example: Lemma. |E f | ≤ 2|E|. Introduction to Algorithms Day 38 L22.18? 2001 by Charles E. Leiserson Augmenting paths Definition. Any path from s to t in G f is an aug- menting path in G with respect to f. The flow value can be increased along an augmenting path p by )},({min)( ),( vucpc f pvu f ∈ = . s s 3:5 G: 2:6 0:2 5:5 2:3 t t 2:5 s s 2 3 G f : 4 2 7 2 1 t t 3 2 c f (p) = 2 Ex.: Introduction to Algorithms Day 38 L22.19? 2001 by Charles E. Leiserson Max-flow, min-cut theorem Theorem. The following are equivalent: 1. f is a maximum flow. 2. f admits no augmenting paths. 3. | f | = c(S, T) for some cut (S, T). Proof (and algorithms). Next time.