- A sheet is provided for use in answering this question.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{89e3545e-fa4b-47dd-8651-7c8f998df9e7-3_725_1303_274_340}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{figure}
Figure 2 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
- Calculate the values of cuts \(C _ { 1 }\) and \(C _ { 2 }\).
- Find the minimum cut and state its value.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{89e3545e-fa4b-47dd-8651-7c8f998df9e7-3_645_1316_1430_338}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{figure}
Figure 3 shows a feasible flow through the same network. - State the values of \(x , y\) and \(z\).
- 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.
State how you know that you have found a maximal flow.