5 [Answer this question on the insert provided.]
Fig. 1 shows a directed flow network. The weight on each arc shows the capacity in litres per second.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-05_620_1082_424_502}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{figure}
- Find the capacity of the cut \(\mathscr { C }\) shown.
- Deduce that there is no possible flow from \(S\) to \(T\) in which both arcs leading into \(T\) are saturated. Explain your reasoning clearly.
Fig. 2 shows a possible flow of 160 litres per second through the network.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-05_499_1084_1471_500}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{figure} - On the diagram in the insert, show the excess capacities and potential backflows for this flow.
- Use the labelling procedure to augment the flow as much as possible. Show your working clearly, but do not obscure your answer to part (iii).
- Show the final flow that results from part (iv). Explain clearly how you know that this flow is maximal.