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)