| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Calculate cut capacity |
| Difficulty | Moderate -0.8 This is a straightforward D1 network flows question testing standard definitions, routine cut calculations, and basic max-flow min-cut theorem application. Part (a) is pure recall, parts (b)-(d) involve simple arithmetic on given cuts, and part (e) requires minimal reasoning about which arc increases capacity. No complex problem-solving or novel insight needed—easier than average A-level maths. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (i) A cut is a division of the vertices of a flow network into 2 sets, one containing the source(s) and the other containing the sink(s). | B1 | |
| (ii) A cut whose capacity is least | B1 (c2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(C_1 = 1038\), \(C_2 = 673\) | B1 (c2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Example: \(A \xrightarrow{(318)} S \xrightarrow{(164)} D \xrightarrow{(208)} T\), \(A \xrightarrow{(2146)} C \xrightarrow{(214)} G \xrightarrow{(427)} T\), \(S \xrightarrow{(325)} B \xrightarrow{251} E \xrightarrow{(251)} F \xrightarrow{(236)} T\) | M1 A1 A1 | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| AC, CD, EF, FT | B1 (1) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| DE would not allow any further flow up EF. DE would carry but minimum cut - D can take extra flow. G then except it. Flow increased by 86 to 159 (except able number) | B2, I, O (2) [11] |
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| (i) A cut is a division of the vertices of a flow network into 2 sets, one containing the source(s) and the other containing the sink(s). | B1 | |
| (ii) A cut whose capacity is least | B1 (c2) | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $C_1 = 1038$, $C_2 = 673$ | B1 (c2) | |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Example: $A \xrightarrow{(318)} S \xrightarrow{(164)} D \xrightarrow{(208)} T$, $A \xrightarrow{(2146)} C \xrightarrow{(214)} G \xrightarrow{(427)} T$, $S \xrightarrow{(325)} B \xrightarrow{251} E \xrightarrow{(251)} F \xrightarrow{(236)} T$ | M1 A1 A1 | (3) |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| AC, CD, EF, FT | B1 (1) | |
## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| DE would not allow any further flow up EF. DE would carry but minimum cut - D can take extra flow. G then except it. Flow increased by 86 to 159 (except able number) | B2, I, O (2) [11] | |\begin{enumerate}[label=(\alph*)]
\item Define the terms
\begin{enumerate}[label=(\roman*)]
\item cut,
\item minimum cut,
\end{enumerate}
as applied to a directed network flow. [2]
\end{enumerate}
\includegraphics{figure_4}
Figure 4 shows a capacitated directed network and two cuts $C_1$ and $C_2$. The number on each arc is its capacity.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item State the values of the cuts $C_1$ and $C_2$. [3]
\end{enumerate}
Given that one of these two cuts is a minimum cut,
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Find a maximum flow pattern by inspection, and show it on the diagram in the answer book. [3]
\item Find a second minimum cut for this network. [1]
\end{enumerate}
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$.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{4}
\item State, with a reason, which of these arcs should be added, and the value of the increased flow. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2006 Q4 [11]}}