9.
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-6_540_1291_203_411}
This diagram shows a capacitated directed network. The number on each arc is its capacity.
- State the maximum flow along
- SADT,
- SCET,
- \(S B F T\).
- Show these maximum flows on Diagram 1 below.
\section*{Diagram 1}
\includegraphics[max width=\textwidth, alt={}]{be329a47-a709-4719-abe6-41d388a6c631-6_561_1187_1283_721}
Take 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 below. List each flow-augmenting route you use, together with its flow.
\section*{Diagram 2}
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_718_1525_205_269}
- Draw your final flow pattern on Diagram 3 below.
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_611_1196_1082_717} - Prove that your flow is maximal.
- Give an example of a practical situation that could have been modelled by the original network.