| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Find missing flow values |
| Difficulty | Moderate -0.8 This is a standard network flows question requiring application of well-defined algorithms (conservation of flow, identifying saturated arcs, cut capacities, and max-flow min-cut theorem). Parts (a)-(d) are routine bookwork, (e) requires inspection but follows standard patterns, and (f) applies a standard theorem. No novel problem-solving or proof construction required beyond textbook methods. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
1.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-1_746_1413_262_267}
\end{center}
The diagram above shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow.
\begin{enumerate}[label=(\alph*)]
\item State the values of $x$ and $y$.
\item List the saturated arcs.
\item State the value of the feasible flow.
\item State the capacities of the cuts $\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }$, and $\mathrm { C } _ { 3 }$.
\item By inspection, find a flow-augmenting route to increase the flow by one unit. You must state your route.
\item Prove that the new flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2008 Q1 [11]}}