Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 22 Prof charles e. leiserson
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 22 Prof. 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 Ehas a nonnegative capacity c(u, v). If(u,v)EE then c(u, v)=0 Example: c 2001 by Charles E Leiserson Introduction to Agorithms Day38L22.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.2 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: ss tt 3 2 3 3 2 2 3 1 3 2 1
Flow networks Definition, a positive flow on G is a function p:V×V→ R satisfying the following Capacity constraint: For allu, ve v 0≤p(l,y)≤c(2v) Flow conservation: For all u v-s, t) ∑p(1)-∑ p(v,u)=0 v∈ v∈ The value of a flow is the net flow out of the source ∑p(s,)-∑p(,s) v∈ v∈ c 2001 by Charles E Leiserson Introduction to Agorithms Day 38 L22.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.3 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 v∈V v∈V p u v p v u . The value of a flow is the net flow out of the source: ∑ ∑ ∈ ∈ − v V v V p(s,v) p(v,s)
a flow on a network positive capacity flow 2:2 2:3 1:3 2:3 2 2:2 1:2 2:3 Flow conservation (like Kirchoff's current law) ● Flow into u is2+1=3 flow out of u is0+1+2=3 The value of this fow is 1-0+2=3 c 2001 by Charles E Leiserson Introduction to Agorithms Day 38 L22. 4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.4 A flow on a network ss tt 1:3 2:2 2:3 1:12:3 1:2 1:2 2:3 0:1 1:3 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
The maximum-flow problem Maximum-flow problem: Given a flow network G. find a flow of maximum value on g 2:2 2:3 2:3 0:3 2:3|1:2 2:2 2:2 3:3 The value of the maximum flow is 4 c 2001 by Charles E Leiserson Introduction to Agorithms Day38L22.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.5 The maximum-flow problem ss tt 2:3 2:2 2:3 1:12:3 1:2 2:2 3:3 0:1 0:3 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
Flow cancellation Without loss of generality, positive flow goes either from u to v. or from y to u. but not both Net flow from 2:3 1:2 0:2 u to y 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 c 2001 by Charles E Leiserson Introduction to Agorithms Day38L22.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.6 Flow cancellation Without loss of generality, positive flow goes either from u to v, or from v to u, but not both. vv uu 2:3 1:2 vv uu 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
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×→ R satisfying the following Capacity constraint: For all u,vE V, ° Flow conservation: For all 1∈-{S,t}, 2f(u,v)=0.One summation v∈ instead of two Skew symmetry: For all u,vE V, c 2001 by Charles E Leiserson Introduction to Agorithms Day38L22.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.7 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 v∈V f u v . • Skew symmetry: For all u, v ∈ V, f(u, v) = –f(v, u)
Equivalence of definitions Theorem. The two definitions are equivalent Proof()Let f(u,v)=plu, v)-p(v, u) Capacity constraint: Since pl(u, v)<cu, v)and p(v,)≥0, we have f(l,y)≤c(2v) Flow conservation ∑f(1)=2()-p() v∈ v∈ =∑p()∑ v∈ v∈ Skew symmetry. f(u, v=p(u, v)-p(v, u) -(p(v,l)-p(,y) c 2001 by Charles E Leiserson Introduction to Algorithms Day 38 L22.8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.8 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: ( ) ∑ ∑ ∑ ∑ ∈ ∈ ∈ ∈ = − = − v V v V v V v V p u v p v u f u v p u v p v u ( , ) ( , ) ( , ) ( , ) ( , ) • Skew symmetry: f(u, v) = p(u, v) – p(v, u) = – (p(v, u) – p(u, v)) = – f(v, u)
Proof (continued) (ELet p(,1)=0)fn,y)>0 ifu,y)≤0 Capacity constraint: By definition, plu, v20. Since f (l,y)≤c(l,y), it follows that p(l2y)≤c(l2) Flow conservation: Iff(u,v)>0, then plu, v)-p(v, u) f(u, v). Iff(u,v)<0, then plu, v)-p(v, u)=-f(v, u) f(u, v by skew symmetry. Therefore ∑m(n0)-∑pn,m)=∑f(u v∈ v∈ c 2001 by Charles E Leiserson Introduction to Agorithms Day 38 L22.9
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.9 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, ∑ ∑ ∑ ∈ ∈ ∈ − = v V v V v V p(u,v) p(v,u) f (u,v)
Notation Definition. The value of a flow f denoted by f Is given f=∑f(.y) v∈ f(s,v) 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 ue v-is, t) c 2001 by Charles E Leiserson Introduction to Agorithms Dav38L22.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.10 Notation Definition. The value of a flow f, denoted by |f |, is given by ( , ) ( , ) f s V f f s v v V = = ∑ ∈ . 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}