COMP 360 Lecture Notes - Lecture 4: Flow Network, If And Only If, Contraposition

• School: McGill University
• Department: Computer Science (Sci)
• Course: COMP 360
• Professor: Adrian R Vetta

Document Summary

It depends on the original network and the current flow in the network. Flow value lemma: let f be any flow and let (a,b) be any cut. Then, the net flow across (a,b) = val(f) By definition we must remember that the value of the flow = the total flow leaving the source. We are claiming through the lemma above that if we take an arbitrary cut in the same graph across that cut = value of the flow. ) *+, *- 2 urce. aph then the net flow. The sink is not in the partition a and hence source "s" is the only node 0. We want to simplify these edges (referring to the diagram above) : - The edge is: (s, v1) - this would cancel each other out. The edges are: (s, v2) and (v1, v4) Let f be any flow and (a,b) be any cut.