2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{d7e250dc-9e38-4f65-a51a-c6a08082f310-03_1120_1757_212_153}
\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.
- List the eight saturated arcs.
- Explain why arc EH can never be full to capacity.
- Find the capacity of
- cut \(C _ { 1 }\)
- cut \(C _ { 2 }\)
- Write down a flow-augmenting route that increases the flow by three units.
Given that the flow through the network is increased by three units,
- prove that this new flow is maximal.