Starting from zero, one valid run of the <Ford-Fulkerson algorithm> augments along
$$
\begin{aligned}
S\to a\to d\to T &\quad\text{by }1,\\
S\to b\to d\to T &\quad\text{by }2,\\
S\to b\to e\to T &\quad\text{by }1,\\
S\to c\to e\to T &\quad\text{by }4.
\end{aligned}
$$
The resulting nonzero edge flows are
$$
\begin{array}{c|ccccccccc}
\text{edge}&Sa&Sb&Sc&ad&bd&be&ce&dT&eT\\ \hline
\text{flow}&1&3&4&1&2&1&4&3&5
\end{array}
$$
and they obey every <capacity constraint> and every flow-conservation equation. The flow value is
$$
\boxed{|f|=1+3+4=8}.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / ib / Paper 4 / 20H / b / i / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ib/paper-4/20h/b/i/solution