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)