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)