Class exercise solution recap

In class today, the exercise was to prove that the flow out of s equals to the flow into t in any valid flow network. Someone cleverly proposed the following solution.

First, let A be the set of all nodes except s and t. Then by the flow conversation constraint, we have

But notice that for every edge e which does not have s or t as an endpoint, appears on both sides (since it goes into one node and comes out of one node). Canceling off all these terms, on the left hand side we are left with the flow into t, and on the right hand side, the flow out of s, proving that the two are equal.

In the next class (on Friday), we’ll see a generalization of this lemma, which will be the basis of our algorithms for computing minimum s-t cuts.

Advertisement