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
For a flow network max flow is the same as the min st-cut .
Link to original cuts of this graph in particular st-cuts .
st-cut
Given a flow network st-cut is a cut capacity of this cut is
Link to original Max flow problem called the Min st-cut problem .
Statement
Given a flow network st-cut
Link to original
Max-flow min-cut Theorem Statement
For a flow network max flow is the same as the min st-cut .
Proof
First we show max flow min st-cut .
In fact we will show something even stronger. For any flow st-cut Claim 1 as we have
max flow min st-cut .
From Claim 2 let Ford-Fulkerson Algorithm . Then we have a st-cut
Claim 1
Let flow and st-cut . Then define
Proof of Claim 1
This follows from playing around with formulas
Misplaced & f^{out}(L) - f^{in}(L) = & \sum_{\substack{(l,r) \in E\\ l \in L, r \in R}} f(l,r) - \sum_{\substack{(r,l) \in E\\ l \in L, r \in R}} f(r,l)\\ = & \left ( \sum_{\substack{(l,r) \in E\\ l \in L, r \in R}} f(l,r) + \sum_{\substack{(l,l^{\ast}) \in E\\ l, l^{\ast} \in L}} f(l,l^{\ast}) \right ) - \left ( \sum_{\substack{(r,l) \in E\\ l \in L, r \in R}} f(r,l) + \sum_{\substack{(l^{\ast},l) \in E\\ l, l^{\ast} \in L}} f(l^{\ast},l)\right )\\ = & \sum_{l \in L} f^{out}(l) + \sum_{l \in L} f^{in}(l)\\ = & f^{out}(s) + \sum_{l \in L \backslash \{s\}} \left(f^{out}(l) - f^{in}(v)\right)\\ = & f^{out}(s)\\ = & size(f) \end{align*}$$ With the 4th line following from the fact that we can assume $s$ has no in flow. The 5th line follows from the preservation of flow. # Claim 2 >[!important] Claim 2 > >Let $f^{\ast}$ be a [[Flow|flow]] from the [[Ford-Fulkerson Algorithm]] then there exists a [[st-cut]] $(L^{\ast},R^{\ast})$ such that >$$size(f^{\ast}) = capacity(L^{\ast},R^{\ast}).$$ ## Proof of Claim 2 As $f^{\ast}$ is given by the [[Ford-Fulkerson Algorithm]] there is no [[Path (graph)|path]] from $s$ to $t$ in the [[Residual Network (flow)|residual network]] $G^{f^{\ast}}$. Let $$L^{\ast} = \{v \in V \vert s-v \mbox{ are path connected in } G^{f^{\ast}}\} \mbox{ and } R^{\ast} = V \backslash L^{\ast}.$$ We know $t \not \in L^{\ast}$ as there is no [[Path (graph)|path]] from $s$ to $t$. So this is an [[st-cut]]. Now consider edge $(l,r) \in E$ with $l \in L^{\ast}$ and $r \in R^{\ast}$ as there is no edge $(l,r) \in E^{f^{\ast}}$ we have $f^{\ast}(l,r) = c(l,r)$. Similarly for edges $(r,l) \in E$ with $l \in L^{\ast}$ and $r \in R^{\ast}$ as there is no edge $(l,r) \in E^{f^{\ast}}$ we have $f^{\ast}(r,l) = 0$. From [[Max-flow min-cut Theorem#claim-1|Claim 1]] we have $$\begin{align*}size(f^{\ast}) & = (f^{\ast})^{out}(L) + (f^{\ast})^{in}(L)\\ & = \sum_{\substack{(l,r) \in E\\ l \in L, r \in R}} f^{\ast}(l,r) + \sum_{\substack{(r,l) \in E\\ l \in L, r \in R}} f^{\ast}(r,l)\\ & = \sum_{\substack{(l,r) \in E\\ l \in L, r \in R}} c(l,r)\\ & = capacity(L^{\ast}, R^{\ast}).\end{align*}$$ Link to original 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 Statement
Given a flow network flow path from residual network
Proof
This follows from the proof of the Max-flow min-cut Theorem .
In particularly Claim 2 in the proof of the main result gives us that value of st-cut . With the corollary of Claim 1 being that for these to be equal they must be maximal/minimal in their own respects.
Link to original