| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Calculate MST length/weight/cost |
| Difficulty | Moderate -0.8 This is a standard textbook application of Prim's algorithm and Chinese postman problem with a clearly labeled network diagram. Part (a) requires mechanical application of a learned algorithm with no problem-solving insight, while part (b) is a routine follow-up requiring identification of odd vertices and pairing. The question is easier than average A-level maths as it tests algorithmic execution rather than mathematical reasoning. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Use of Prim's algorithm; first edges AC=13, AE=14, EI=15, CD=16 | M1 | Use of Prim's (not Kruskal's and not path); 6+ edges (no cycles); edges not lengths or vertices, with first 2 edges correct |
| CH=20, EF=21, FB=19, BG=19 (8 edges) | B1 | 8 edges |
| CH 5th | A1 | |
| EF 6th | A1 | |
| All correct | A1 | Total: 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 137 | B1 | Total: 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct spanning tree drawn with 6+ edges, no cycles | M1 | |
| Correct, including labelling | A1 | Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Odd vertices: \(B, C, D, E\) | E1 | PI CAO |
| \(BC+DE = 22+18\) (or 40); \(BD+CE = 38+27\) (or 65); \(BE+CD = 22+16\) (or 38) | M1 | 3 correct sets of pairs (lettered) |
| Values correct | A2;1 | 3 correct sets of numbers; 2 correct sets of numbers |
| \(\min = 307 + 38\) | A1F | PI 307 plus their shortest |
| \(= 345\) | B1 | SC: 345 with no M mark scored scores 2/last 5. Route without 345 scores 0/last 5. Total: 6 |
# Question 4:
## Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Use of Prim's algorithm; first edges AC=13, AE=14, EI=15, CD=16 | M1 | Use of Prim's (not Kruskal's and not path); 6+ edges (no cycles); edges not lengths or vertices, with first 2 edges correct |
| CH=20, EF=21, FB=19, BG=19 (8 edges) | B1 | 8 edges |
| CH 5th | A1 | |
| EF 6th | A1 | |
| All correct | A1 | Total: 5 |
## Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 137 | B1 | Total: 1 |
## Part (a)(iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct spanning tree drawn with 6+ edges, no cycles | M1 | |
| Correct, including labelling | A1 | Total: 2 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Odd vertices: $B, C, D, E$ | E1 | PI CAO |
| $BC+DE = 22+18$ (or 40); $BD+CE = 38+27$ (or 65); $BE+CD = 22+16$ (or 38) | M1 | 3 correct sets of pairs (lettered) |
| Values correct | A2;1 | 3 correct sets of numbers; 2 correct sets of numbers |
| $\min = 307 + 38$ | A1F | PI 307 plus their shortest |
| $= 345$ | B1 | SC: 345 with no M mark scored scores 2/last 5. Route without 345 scores 0/last 5. Total: 6 |4 In Paris, there is a park where there are statues of famous people; there are many visitors each day to this park. Lighting is to be installed at nine places, $A , B , \ldots , I$, in the park. The places have to be connected either directly or indirectly by cabling, to be laid alongside the paths, as shown in the diagram.
The diagram shows the length of each path, in metres, connecting adjacent places.\\
\includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-4_1109_1120_612_459}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Prim's algorithm, starting from $A$, to find the minimum length of cabling required.
\item State this minimum length.
\item Draw the minimum spanning tree.
\end{enumerate}\item A security guard walks along all the paths before returning to his starting place. Find the length of an optimal Chinese postman route for the guard.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2010 Q4 [14]}}