6. This question should be answered on the sheet provided in the answer booklet.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{c1b75596-bbab-4278-8503-7cfbea0bc5f1-6_732_1308_433_388}
\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.
- 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.
- Indicate a maximum flow on Diagram 3.
- Prove that your flow is maximal.