6.\\
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-3_696_1319_1292_374}

This figure shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as the initial flow.
\begin{enumerate}[label=(\alph*)]
\item On Diagram 1 and Diagram 2 in the answer book, add a supersource $S$ and a supersink $T$. On Diagram 1 show the minimum capacities of the arcs you have added.

Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.
\item Complete the initial labelling procedure in Diagram 2.
\item Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow, and state the maximal flow.
\item Show a maximal flow pattern on Diagram 3.
\item Prove that your flow is maximal.
\item Describe briefly a situation for which this network could be a suitable model.\\
(Total 16 marks)\\
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-4_1486_1963_568_50}
\end{enumerate}

\hfill \mbox{\textit{Edexcel D2 2005 Q6 [16]}}