| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply both algorithms and compare |
| Difficulty | Easy -1.3 This is a standard textbook exercise testing rote application of two MST algorithms (Kruskal's and Prim's) with no problem-solving or insight required. Students simply follow memorized procedures step-by-step on a straightforward network, making it significantly easier than average A-level questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| DE GF DC \(\left\{\begin{array}{c}\text{not CF}\\ \text{BD}\end{array}\right\}\) EG (not EF not CF) AC (not AB) GH | M1 A1 A1 | M1: Kruskal's algorithm – first 4 arcs selected chosen correctly.<br>1A1: All seven non-rejected arcs chosen correctly.<br>2A1: All rejections correct and in correct order and at correct time. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Table with entries: A-B: 31, A-C: 30, B-D: 24, B-H: 38, C-D: 22, C-E: 24, C-F: 29, D-E: 18, E-F: 28, E-G: 26, F-G: 21, G-H: 33, H-D: 34 | B2, 1, 0 | 1B1: condone two (double) errors<br>2B1: cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| AC CD DE BD GE GF GH | M1 A1 A1 | M1: Prim's algorithm – first four arcs chosen correctly, in order, or first five nodes chosen correctly, in order. {A,C,D,E,B,...}<br>1A1: First six arcs chosen correctly or all 8 nodes chosen correctly, in order. {A,C,D,E,B,G,F,H}<br>2A1: All correct and arcs chosen in correct order. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Weight: 174 | B1 | 1B1: cao |
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| DE GF DC $\left\{\begin{array}{c}\text{not CF}\\ \text{BD}\end{array}\right\}$ EG (not EF not CF) AC (not AB) GH | M1 A1 A1 | M1: Kruskal's algorithm – first 4 arcs selected chosen correctly.<br>1A1: All seven non-rejected arcs chosen correctly.<br>2A1: All rejections correct and in correct order and at correct time. |
**Total: 3 marks**
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Table with entries: A-B: 31, A-C: 30, B-D: 24, B-H: 38, C-D: 22, C-E: 24, C-F: 29, D-E: 18, E-F: 28, E-G: 26, F-G: 21, G-H: 33, H-D: 34 | B2, 1, 0 | 1B1: condone two (double) errors<br>2B1: cao |
**Total: 2 marks**
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| AC CD DE BD GE GF GH | M1 A1 A1 | M1: Prim's algorithm – first four arcs chosen correctly, in order, or first five nodes chosen correctly, in order. {A,C,D,E,B,...}<br>1A1: First six arcs chosen correctly or all 8 nodes chosen correctly, in order. {A,C,D,E,B,G,F,H}<br>2A1: All correct and arcs chosen in correct order. |
**Total: 3 marks**
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Weight: 174 | B1 | 1B1: cao |
**Total: 1 mark**
**Grand Total for Q2: 9 marks**
---\includegraphics{figure_1}
Figure 1 represents the distances, in metres, between eight vertices, A, B, C, D, E, F, G and H, in a network.
\begin{enumerate}[label=(\alph*)]
\item Use Kruskal's algorithm to find a minimum spanning tree for the network.
You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
[3]
\item Complete Matrix 1 in your answer book, to represent the network.
[2]
\item Starting at A, use Prim's algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs.
[3]
\item State the weight of the minimum spanning tree.
[1]
\end{enumerate}
(Total 9 marks)
\hfill \mbox{\textit{Edexcel D1 2010 Q2 [9]}}