Week 6 - Homework 4 (assessed)

Week 7 - Max-Flow Min-Cut

This lecture we want to show correctness of Ford-Fulkerson Algorithm.

To do this we will prove the following Theorem. Statement To do this lets first look at cuts of this graph in particular st-cuts. st-cut There is a related problem to Max flow problem called the Min st-cut problem. Statement

Proof of the Max-flow min-cut Theorem

Max-flow min-cut Theorem Note this gives us that $size(f^{\ast})$ for a flow from the Ford-Fulkerson Algorithm is maximal. Therefore Ford-Fulkerson Algorithm is correct and we have proven the following lemma. Flows are maximal if there is no augmenting path