6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]\\
Water has to be transferred from two mountain lakes $P$ and $Q$ to three urban reservoirs $U$, $V$ and $W$. There are pumping stations at $X , Y$ and $Z$.

The possible routes with the capacities along each edge, in millions of litres per hour, are shown in the following diagram.\\
\includegraphics[max width=\textwidth, alt={}, center]{68ff5b50-6aff-4b28-8fad-d16a8bb4779e-06_862_1316_662_338}
\begin{enumerate}[label=(\alph*)]
\item On Figure 4, add a super-source, $S$, and a super-sink, $T$, and appropriate edges so as to produce a directed network with a single source and a single sink. Indicate the capacity of each of the edges you have added.
\item \begin{enumerate}[label=(\roman*)]
\item Find the value of the cut $C$.
\item State what can be deduced about the maximum flow from $S$ to $T$.
\end{enumerate}\item On Figure 5, write down the maximum flows along the routes $S Q Z W T$ and $S P Y X Z V T$.
\item \begin{enumerate}[label=(\roman*)]
\item On Figure 6, add the vertices $S$ and $T$ and the edges connecting $S$ and $T$ to the network. Using the maximum flows along the routes SQZWT and SPYXZVT found in part (c) as the initial flow, indicate the potential increases and decreases of flow on each edge.
\item Use flow augmentation to find the maximum flow from $S$ to $T$. You should indicate any flow augmenting paths on Figure 5 and modify the potential increases and decreases of the flow on Figure 6.
\end{enumerate}\item State the value of the flow from $Y$ to $X$ in millions of litres per hour when the maximum flow is achieved.
\end{enumerate}

\hfill \mbox{\textit{AQA D2 2008 Q6 [13]}}