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