Simple properties of flow Lemma °f(x2X)=0, f(x,1)=-f(X,X)2 °f(XUY,Z=f(x,2+f(, Z if Xor=.口 Theorem. f=f(v, t) Proof. f|=f(3s, f(r,v-f(v-s,v Omit braces =f(v,v-s) f(r,t+f(,v-s-t f(V1.□ c 2001 by Charles E Leiserson Introduction to Agorithms Dav38L22.11© 2001 by Charles E. Leiserson Introduction to Algorithms Day 38 L22.11 Simple properties of flow Lemma. • f (X, X) = 0, • f (X, Y) = – f (Y, X), • f (X∪Y, Z) = f (X, Z) + f (Y, Z) if X∩Y = ∅. Theorem. | f | = f(V, t). Proof. | f | = f (s, V) = f (V, V) – f (V–s, V) Omit braces. = f (V, V–s) = f (V, t) + f (V, V–s–t) = f (V, t)