1.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{40023f8e-6874-400e-84b5-60d98b648afc-02_1010_1467_353_399}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent a feasible flow from S to T.
- State the value of this flow.
(1) - Explain why arcs CD and CG cannot both be saturated.
(1) - Find the capacity of
- cut \(C _ { 1 }\)
- cut \(C _ { 2 }\)
- Write down a flow augmenting route of weight 6 which saturates BF.
The flow augmenting route in part (d) is applied to give an increased flow.
- Prove that this increased flow is maximal.