Moderate -0.5 This is a standard D2 network flows question testing basic definitions and routine application of max-flow min-cut theorem. Parts (a)-(b) are pure recall, part (c) is inspection of a small network, and parts (d)-(e) require minimal problem-solving. Easier than average A-level maths due to algorithmic nature and limited conceptual depth.
minimum cut, as applied to a directed network flow.
\includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_844_1465_338_299}
The figure above shows a capacitated directed network and two cuts \(C _ { 1 }\) and \(C _ { 2 }\). The number on each arc is its capacity.
State the values of the cuts \(C _ { 1 }\) and \(C _ { 2 }\).
Given that one of these two cuts is a minimum cut,
find a maximum flow pattern by inspection, and show it on the diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_597_1470_1656_296}
Find a second minimum cut for this network.
In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).
State, with a reason, which of these arcs should be added, and the value of the increased flow.
7.
\begin{enumerate}[label=(\alph*)]
\item Define the terms
\begin{enumerate}[label=(\roman*)]
\item cut,
\item minimum cut, as applied to a directed network flow.\\
\includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_844_1465_338_299}
The figure above shows a capacitated directed network and two cuts $C _ { 1 }$ and $C _ { 2 }$. The number on each arc is its capacity.
\end{enumerate}\item State the values of the cuts $C _ { 1 }$ and $C _ { 2 }$.
Given that one of these two cuts is a minimum cut,
\item find a maximum flow pattern by inspection, and show it on the diagram below.\\
\includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_597_1470_1656_296}
\item Find a second minimum cut for this network.
In order to increase the flow through the network it is decided to add an arc of capacity 100 joining $D$ either to $E$ or to $G$.
\item State, with a reason, which of these arcs should be added, and the value of the increased flow.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2006 Q7 [11]}}