9.
\includegraphics[max width=\textwidth, alt={}]{83ddfbb1-d035-4fae-b39d-a643c877cfed-6_945_1484_255_285}
The figure above shows a capacitated, directed network. The capacity of each arc is shown on each arc. The numbers in circles represent an initial flow from \(S\) to \(T\).
Two cuts \(C _ { 1 }\) and \(C _ { 2 }\) are shown on the figure.
- Write down the capacity of each of the two cuts and the value of the initial flow.
(3) - Complete the initialisation of the labelling procedure on the diagram below by entering values along arcs \(A C , C D , D E\) and \(D T\).
\includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-7_2372_1131_121_475} - Hence use the labelling procedure to find a maximal flow through the network. You must list each flow-augmenting path you use, together with its flow.
- Show your maximal flow pattern on the diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-8_757_1472_210_294} - Prove that your flow is maximal.
(Total 14 marks)