= Solution
Start with zero <flow> and apply the <Ford-Fulkerson algorithm>. The following <augmenting paths> and bottlenecks use the capacities in the original PDF diagram:
$$
\begin{array}{c|l|c|c}
\text{step}&\text{path}&\text{increment}&\text{total flow}\\\hline
1&1\to2\to4\to6\to8&2&2\\
2&1\to2\to5\to6\to8&2&4\\
3&1\to3\to5\to7\to8&1&5\\
4&1\to3\to5\to4\to6\to7\to8&1&6
\end{array}.
$$
For example, the second path is limited by the remaining capacity two on $6\to8$ and by capacity two on $5\to6$. After the third augmentation, $7\to8$ has residual capacity one; the fourth path supplies it through $5\to4\to6\to7$. Every displayed increment is the smallest residual capacity of its path.
The resulting arc flows are
$$
\begin{array}{c|rrrrrrrrrrrrr}
\text{arc}&12&13&23&24&25&35&54&46&56&57&67&68&78\\\hline
f&4&2&0&2&2&2&1&3&2&1&1&4&2
\end{array}.
$$
Here $uv$ denotes $u\to v$. These satisfy every capacity bound and <flow conservation>. The final <residual network> has source-reachable set $S=\{1,2,3,5\}$. Its outgoing arcs are $2\to4$, $5\to4$, $5\to6$ and $5\to7$, with capacities $2,1,2,1$, all saturated. Consequently
$$
\boxed{|f|_{\max}=6,\qquad (S,S^c)=(\{1,2,3,5\},\{4,6,7,8\}),\qquad c(S,S^c)=6.}
$$
This is a <minimum cut>, and the equal flow and cut values certify optimality by the <max-flow min-cut theorem>. The cut immediately before node eight also has capacity six, so the minimum cut is not unique.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2010/iii/paper-35-maximum-flow.png]
{title=Maximum flow six and a minimum cut, with arc labels showing flow/capacity}
Back to article page
