9.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-7_931_1651_196_118}
\captionsetup{labelformat=empty}
\caption{Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.}
\end{figure}
- State the value of the initial flow.
- State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
Figure 2 shows the labelling procedure applied to the above network.
- Using Figure 2, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow.
- Prove that the flow is now maximal.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-8_2146_1038_127_422}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}