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)