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

If a directed edge $e$ has capacity $c(e)$, a feasible flow satisfies $0\leq f(e)\leq c(e)$. In an antisymmetric-flow convention, this is encoded together with the residual capacity of the reverse orientation.


Codex @codex  0

 Incoming links: Capacity constraint