| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Easy -1.3 This is a straightforward application of Prim's algorithm, a standard D1 procedure requiring systematic edge selection and recording. The algorithm is mechanical with no problem-solving insight needed—students follow the taught method step-by-step. Part (b) requires minimal additional thought about algorithm order but no conceptual depth. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Starting at \(A\): select \(AD = 4\) | B1 | First edge correct |
| Select \(AB = 6\), then \(BD = 7\) rejected, \(DC = 18\) | M1 | Correct application of Prim's |
| Correct sequence of edges selected: \(AD\), \(AB\), \(DE\), \(EH\), \(EG\), \(GI\), \(GF\), \(HC\) or similar | A1 | Accept equivalent valid orderings |
| All 8 edges correct for spanning tree | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Total length \(= 4+6+19+14+10+12+20+13 = 98\) miles | B1 | Follow through from their tree |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct tree drawn with all 9 vertices and 8 edges | B1 | |
| All edge weights correctly labelled | B1 | Follow through from (a)(i) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Final edge: \(AB = 6\) (or \(EH = 14\) depending on order reached) | B1 | Accept any valid final edge for Prim's from \(D\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Final edge: \(GI = 12\) (or equivalent last edge when starting from \(H\)) | B1 | Accept any valid final edge for Prim's from \(H\) |
# Question 3:
## Part (a)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting at $A$: select $AD = 4$ | B1 | First edge correct |
| Select $AB = 6$, then $BD = 7$ rejected, $DC = 18$ | M1 | Correct application of Prim's |
| Correct sequence of edges selected: $AD$, $AB$, $DE$, $EH$, $EG$, $GI$, $GF$, $HC$ or similar | A1 | Accept equivalent valid orderings |
| All 8 edges correct for spanning tree | A1 | |
## Part (a)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Total length $= 4+6+19+14+10+12+20+13 = 98$ miles | B1 | Follow through from their tree |
## Part (a)(iii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct tree drawn with all 9 vertices and 8 edges | B1 | |
| All edge weights correctly labelled | B1 | Follow through from (a)(i) |
## Part (b)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Final edge: $AB = 6$ (or $EH = 14$ depending on order reached) | B1 | Accept any valid final edge for Prim's from $D$ |
## Part (b)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Final edge: $GI = 12$ (or equivalent last edge when starting from $H$) | B1 | Accept any valid final edge for Prim's from $H$ |
I can see these are exam paper pages showing questions and answer spaces, but I don't see any mark scheme content in these images. These appear to be the **question paper pages** (pages 7-11), not the mark scheme.
The pages show:
- Answer space for Question 3 (page 7)
- Question 4 with a network diagram (page 8)
- Answer space for Question 4 (page 9)
- Question 5 with a network diagram (page 10)
- Answer space for Question 5 (page 11)
To extract mark scheme content, I would need the **mark scheme document** for this paper (P50406/Jun12/MD01), which would be a separate document showing:
- Model answers
- Mark allocations (M1, A1, B1, etc.)
- Examiner guidance notes
Could you share the mark scheme pages instead? They would typically show the worked solutions alongside the mark allocations.3 The following network shows the lengths, in miles, of roads connecting nine villages, $A , B , \ldots , I$.\\
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_810_501_445_388}\\
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_812_499_443_1135}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Prim's algorithm starting from $A$, showing the order in which you select the edges, to find a minimum spanning tree for the network.
\item State the length of your minimum spanning tree.
\item Draw your minimum spanning tree.
\end{enumerate}\item Prim's algorithm from different starting points produces the same minimum spanning tree for this network. State the final edge that would complete the minimum spanning tree using Prim's algorithm:
\begin{enumerate}[label=(\roman*)]
\item starting from $D$;
\item starting from $H$.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q3 [9]}}