6. This question should be answered on the sheet provided.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_723_1292_276_349}
\captionsetup{labelformat=empty}
\caption{Fig. 4}
\end{figure}
Figure 4 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
- Calculate the values of cut \(C _ { 1 }\) and \(C _ { 2 }\).
- Find the minimum cut and state its value.
(2 marks)
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_647_1303_1430_347}
\captionsetup{labelformat=empty}
\caption{Fig. 5}
\end{figure}
Figure 5 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.
(8 marks)