AQA D2 2012 January — Question 6

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

6 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]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-14_807_1472_429_276}
  1. Find the value of the cut \(Q\).
  2. Figure 2 shows most of the values of a feasible flow of 34 litres per second from \(S\) to \(T\).
    1. Insert the missing values of the flows along \(D E\) and \(F G\) on Figure 2.
    2. Using this feasible flow as the initial flow, indicate potential increases and decreases of the flow along each edge on Figure 3.
    3. Use flow augmentation on Figure 3 to find the maximum flow from \(S\) to \(T\). You should indicate any flow-augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
    1. State the value of the maximum flow.
    2. Illustrate your maximum flow on Figure 4.
  3. Find a cut with capacity equal to that of the maximum flow. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_1646_1463_280_381}
    \end{figure} Figure 3 \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_668_1230_1998_404}
    \end{figure}