6. This question should be answered on the sheet provided.

A town has adopted a one-way system to cope with recent problems associated with congestion in one area.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-06_670_1301_459_331}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{center}
\end{figure}

Figure 3 models the one-way system as a capacitated directed network. The numbers on the arcs are proportional to the number of vehicles that can pass along each road in a given period of time.
\begin{enumerate}[label=(\alph*)]
\item Find the capacity of the cut which passes through the $\operatorname { arcs } A E , B F , B G$ and $C D$.\\
(2 marks)

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-07_659_1278_196_335}
\captionsetup{labelformat=empty}
\caption{Fig. 4}
\end{center}
\end{figure}

Figure 4 shows a feasible flow of 17 through the same network. For convenience, a supersource, $S$, and a supersink, $T$, have been used.
\item \begin{enumerate}[label=(\roman*)]
\item Use the labelling procedure to find the maximum flow through this network. You must list each flow-augmenting route you use together with its flow.
\item Show your maximum flow pattern and state its value.
\end{enumerate}\item Prove that your flow is the maximum possible through the network.
\item It is suggested that the maximum flow through the network could be increased by making road $E F$ undirected, so that it has a capacity of 8 in either direction.

Using the maximum flow-minimum cut theorem, find the increase in maximum flow this change would allow.\\
(2 marks)
\item An alternative suggestion is to widen a single road in order to increase its capacity. Which road, on its own, could lead to the biggest improvement, and what would be the largest maximum flow this could achieve.\\
(2 marks)
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1  Q6 [15]}}