6 [Figures 4, 5, 6 and 7, printed on the insert, are provided for use in this question.]
- The network shows a flow from \(S\) to \(T\) along a system of pipes, with the capacity, in litres per minute, indicated on each edge.
\includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_350_878_532_591}
- Show that the value of the cut shown on the diagram is 97 .
- The cut shown on the diagram can be represented as \(\{ S , C \} , \{ A , B , T \}\).
Complete the table on Figure 4, giving the value of each of the 8 possible cuts.
- State the value of the maximum flow through the network, giving a reason for your answer.
- Indicate on Figure 5 a possible flow along each edge corresponding to this maximum flow.
- Extra pipes, \(B D , C D\) and \(D T\), are added to form a new system, with the capacity, in litres per minute, indicated on each edge of the network below.
\includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_483_977_1724_520}
- Taking your values from Figure 5 as the initial flow, use the labelling procedure on Figure 6 to find the new maximum flow through the network. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
- State the value of the new maximum flow, and, on Figure 7, indicate a possible flow along each edge corresponding to this maximum flow.