Flows and Cuts Flow value lemma.Let f be any flow,and let (A, B)be any s-t cut.Then,the net flow sent across the cut is equal to the amount leaving s. ∑f(e)-∑f(e)=v(f) e out of 4 e in to a 6 2 9 5 10 0 6 10 44 15 150 10 3 8 8 5 3 8 6 10 1 10 4 0 6 150 15 10 11 11 Value 24 4 30 1
11 Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s. Flows and Cuts 10 6 6 11 1 10 3 8 8 0 0 0 11 s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 15 10 4 4 0 Value = 24 f(e) e out of A f(e) e in to A v( f ) 4 A
Flows and Cuts Flow value lemma.Let f be any flow,and let (A, B)be any s-t cut.Then,the net flow sent across the cut is equal to the amount leaving s. ∑f(e)-∑f(e)=v(f) e out of 4 e in to a 6 2 9 5 10 0 6 10 44 15 150 10 3 8 8 5 8 6 10 A 10 150 15 10 11 11 Value=6+0+8-1+11 4 30 =24 12
12 Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s. Flows and Cuts f(e) e out of A f(e) e in to A v( f ) 10 6 6 1 10 3 8 8 0 0 0 11 s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 15 10 4 4 0 Value = 6 + 0 + 8 - 1 + 11 = 24 4 11 A