4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{cea07472-f93b-4a7b-b362-89fb8c0af4a9-04_931_1312_219_379}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 shows a capacitated, directed network of pipes. The uncircled number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.
- List the saturated arcs.
- State the value of the initial flow.
- Explain why arc FT cannot be full to capacity.
- State the capacity of cut \(C _ { 1 }\) and the capacity of cut \(C _ { 2 }\)
- By inspection find one flow-augmenting route to increase the flow by three units. You must state your route.
- Prove that, once the flow-augmenting route found in part (e) has been applied, the flow is maximal.