6. This question should be answered on the sheet provided in the answer booklet.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-007_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.