| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | State maximum flow along specific routes |
| Difficulty | Standard +0.3 This is a standard D1 network flows question requiring straightforward application of the labelling procedure algorithm. Part (a) involves simple path inspection, parts (b)-(d) are routine algorithmic execution, and part (e) requires stating a standard max-flow min-cut result—all textbook exercises with no novel problem-solving required. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(x + y = 8\) correctly drawn | B1 | Must pass within one small square of \((0,8)\), \((4,4)\) and \((8,0)\) |
| \(3y = 9 + 2x\) correctly drawn | B1 | Must pass within one small square of \((0,3)\), \((6,7)\); sufficiently long to define feasible region |
| \(4y = x\) correctly drawn | B1 | Must pass within one small square of origin and \((8,2)\) |
| \(x = 8\) correctly drawn | B1 | Must be distinct from the other three lines; shown as dashed or distinctive |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct R labelled | B1 | All lines must have been drawn correctly; condone \(x=8\) not distinct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Objective line drawn | B1 | Line must be correct to within one small square if extended from axis to axis |
| \(V\left(\dfrac{32}{5}, \dfrac{8}{5}\right)\) (oe) | M1 dA1 | Must have scored B1; correct exact coordinates; if reciprocal objective line drawn, must solve \(x+y=8\) and \(3y=9+2x\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(C = \dfrac{88}{5}\) (oe) | B1 | CAO or \(17.6\) or \(17\dfrac{3}{5}\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \((7,7)\) | B1 | CAO vertex; accept \(x=7\), \(y=7\) |
| \(35\) | B1 | CAO value |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(y \leq \dfrac{5}{3}x\) \(\therefore k = \dfrac{5}{3}\) (oe) | M1 A1 | M1: \(k = \dfrac{5}{3}\) or \(\dfrac{3}{5}\) or \(1.6\) or \(0.6\) or \(1\dfrac{2}{3}\); A1: CAO \(k=\dfrac{5}{3}\) |
## Question 6:
### Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| $x + y = 8$ correctly drawn | B1 | Must pass within one small square of $(0,8)$, $(4,4)$ and $(8,0)$ |
| $3y = 9 + 2x$ correctly drawn | B1 | Must pass within one small square of $(0,3)$, $(6,7)$; sufficiently long to define feasible region |
| $4y = x$ correctly drawn | B1 | Must pass within one small square of origin and $(8,2)$ |
| $x = 8$ correctly drawn | B1 | Must be distinct from the other three lines; shown as dashed or distinctive |
### Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct R labelled | B1 | All lines must have been drawn correctly; condone $x=8$ not distinct |
### Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| Objective line drawn | B1 | Line must be correct to within one small square if extended from axis to axis |
| $V\left(\dfrac{32}{5}, \dfrac{8}{5}\right)$ (oe) | M1 dA1 | Must have scored B1; correct exact coordinates; if reciprocal objective line drawn, must solve $x+y=8$ and $3y=9+2x$ |
### Part (d):
| Answer | Mark | Guidance |
|--------|------|----------|
| $C = \dfrac{88}{5}$ (oe) | B1 | CAO or $17.6$ or $17\dfrac{3}{5}$ |
### Part (e):
| Answer | Mark | Guidance |
|--------|------|----------|
| $(7,7)$ | B1 | CAO vertex; accept $x=7$, $y=7$ |
| $35$ | B1 | CAO value |
### Part (f):
| Answer | Mark | Guidance |
|--------|------|----------|
| $y \leq \dfrac{5}{3}x$ $\therefore k = \dfrac{5}{3}$ (oe) | M1 A1 | M1: $k = \dfrac{5}{3}$ or $\dfrac{3}{5}$ or $1.6$ or $0.6$ or $1\dfrac{2}{3}$; A1: CAO $k=\dfrac{5}{3}$ |
---6. This question should be answered on the sheet provided in the answer booklet.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-007_732_1308_433_388}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{center}
\end{figure}
Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.
\begin{enumerate}[label=(\alph*)]
\item State the maximum flow along
\begin{enumerate}[label=(\roman*)]
\item SAET,
\item SBDT,
\item SCFT.\\
(3 marks)
\end{enumerate}\item Show these maximum flows on Diagram 1 on the answer sheet.
\item Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from $S$ to $T$. Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow.
\item Indicate a maximum flow on Diagram 3.
\item Prove that your flow is maximal.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q6}}