Lecture 15: Max-Flow Min-Cut Theorem

Om kurset

We explain the problem of maximum flow. First, we show that the maximum flow is always less than the minimum cut. We next write down the linear program for maximum flow and take the dual. It turns out that this gives the minimum cut.