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.

DFS in-class exercise

Here are today’s slides.  They contain one possible solution to the network reliability problem.

Prelim. slides & reading assignment

I’ve just posted some preliminary slides.   This gives you some idea of what we’ll be covering, but the slides may change/shift significantly as we progress through the course.

The first reading assignment is Chapters 1 and 2 of the KT book.  Try to read over these before Monday.