AQA D2 2006 January — Question 4

Exam BoardAQA
ModuleD2 (Decision Mathematics 2)
Year2006
SessionJanuary
TopicNetwork Flows

4 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes, with the lower and upper capacities for each pipe in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{30a88efe-fe9e-4384-a3e3-da2a05326797-04_547_1214_555_404}
  1. Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 10 litres per second from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(M N , P Q , N P\) and \(N T\).
    1. Taking your answer from part (a) as an initial flow, use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\).
    2. State the value of the maximum flow and illustrate this flow on Figure 5.
  2. Find a cut with capacity equal to that of the maximum flow.