- A sheet is provided for use in answering this question.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{df7b056f-1446-43f1-a2fd-c0d56533550e-3_588_1285_287_296}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{figure}
Figure 1 shows a capacitated, directed network. The numbers on each arc indicate the minimum and maximum capacity of that arc.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{df7b056f-1446-43f1-a2fd-c0d56533550e-3_648_1288_1155_296}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{figure}
Figure 2 shows a feasible flow through the same network.
- Using this as your initial flow pattern, use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow and draw the maximal flow pattern.
(6 marks) - Find a cut of the same value as your maximum flow and explain why this proves it gives the maximim possible flow.