6. This question should be answered on the sheet provided in the answer booklet.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-003_469_844_422_1731}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{figure}
Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
- State the maximum flow along
- SAET,
- SBDT,
- SCFT.
(3 marks)
- Show these maximum flows on Diagram 1 on the answer sheet.
(1 mark) - Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow.
(6 marks) - Indicate a maximum flow on Diagram 3.
(2 marks) - Prove that your flow is maximal.
(2 marks)