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