| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Moderate -0.8 This is a straightforward application of Prim's algorithm on a given network, requiring systematic execution of a standard algorithm with no conceptual challenges. Parts (a)-(c) are routine procedural work, while part (d) requires understanding Kruskal's algorithm order but involves simple edge comparison rather than problem-solving insight. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Edges selected in order: \(AB=3\), \(BC=6\), \(BE=13\), \(EF=5\), \(FD\) or \(10\), \(FG=32\), \(GJ=7\), \(GH=8\), \(HK=4\), \(HI=12\) | M1, A1 | SCA; Kruskal's (no method): (a) B1, (b) B1, (c) M1 A2 |
| 10 edges listed | B1 | |
| All correct | A1 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(\Sigma = 100\) | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Minimum spanning tree drawn correctly | M1, A2 | 3 \((-1\) EE\()\); 10 edges |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Seventh edge: \(DF\) | B1 | |
| Eighth edge: \(HI\) | B1 | 2 |
| Total: 10 |
## Question 5(a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Edges selected in order: $AB=3$, $BC=6$, $BE=13$, $EF=5$, $FD$ or $10$, $FG=32$, $GJ=7$, $GH=8$, $HK=4$, $HI=12$ | M1, A1 | SCA; Kruskal's (no method): (a) B1, (b) B1, (c) M1 A2 |
| 10 edges listed | B1 | |
| All correct | A1 | **4** |
## Question 5(b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $\Sigma = 100$ | B1 | **1** |
## Question 5(c):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimum spanning tree drawn correctly | M1, A2 | **3** $(-1$ EE$)$; 10 edges |
## Question 5(d):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Seventh edge: $DF$ | B1 | |
| Eighth edge: $HI$ | B1 | **2** |
| **Total: 10** | | |
---5 The network shows the lengths, in miles, of roads connecting eleven villages.\\
\includegraphics[max width=\textwidth, alt={}, center]{76bccb26-f2ec-4798-bb6b-89c922f9651a-04_1100_1575_406_251}
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting from $A$, to find the minimum spanning tree for the network.
\item State the length of your minimum spanning tree.
\item Draw your minimum spanning tree.
\item A student used Kruskal's algorithm to find the same minimum spanning tree. Find the seventh and eighth edges that the student added to his spanning tree.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2005 Q5 [10]}}