| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply both algorithms and compare |
| Difficulty | Moderate -0.8 This is a routine algorithmic question requiring mechanical application of two standard MST algorithms (Kruskal's and Prim's) to a small network, then drawing the result. It tests procedural recall rather than problem-solving or insight, making it easier than average A-level maths questions which typically require more conceptual understanding or multi-step reasoning. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| DC, EG, CF, reject DF; AD, BC, reject AB, BE, reject EF and FG, DH | M1; A1, A1 (3 marks) | a1M1: First three arcs correctly chosen and DF rejected. Accept weights for all 3 marks. Special case: If all 7 arcs in correct order but no rejections seen, award M1 only. a1A1: All arcs/weights in tree selected correctly at correct time. a2A1: All rejections correct and at the right time. |
| Answer | Marks | Guidance |
|---|---|---|
| AD, DC, CF, CB; BE; EG, DH | M1; A1; A1 (3 marks) | b1M1: First four arcs/weights correctly chosen, or first five nodes ADCFB chosen in order. Special case: If Prim but not starting at A please send to review. b1A1: First five arcs/weights correctly chosen, or all nodes in order A, D, C, F, B, E, G, H. b2A1: CSO (must be arcs/weights). E.g no 'reject' arcs. |
| Answer | Marks | Guidance |
|---|---|---|
| Diagram showing minimum spanning tree with correct arcs and weights | B1 (1 mark) | c1B1: CAO mark what you see at (c). |
| Answer | Marks | Guidance |
|---|---|---|
| Weight of tree \(= 148\) (km) | B1 (1 mark) | d1B1: CAO mark what you see at (d). |
# Question 1:
## Part (a):
DC, EG, CF, reject DF; AD, BC, reject AB, BE, reject EF and FG, DH | M1; A1, A1 **(3 marks)** | a1M1: First three arcs correctly chosen and DF rejected. Accept weights for all 3 marks. Special case: If all 7 arcs in correct order but no rejections seen, award M1 only. a1A1: All arcs/weights in tree selected correctly at correct time. a2A1: All rejections correct and at the right time.
## Part (b):
AD, DC, CF, CB; BE; EG, DH | M1; A1; A1 **(3 marks)** | b1M1: First four arcs/weights correctly chosen, or first five nodes ADCFB chosen in order. Special case: If Prim but not starting at A please send to review. b1A1: First five arcs/weights correctly chosen, or all nodes in order A, D, C, F, B, E, G, H. b2A1: CSO (must be arcs/weights). E.g no 'reject' arcs.
## Part (c):
Diagram showing minimum spanning tree with correct arcs and weights | B1 **(1 mark)** | c1B1: CAO mark what you see at (c).
## Part (d):
Weight of tree $= 148$ (km) | B1 **(1 mark)** | d1B1: CAO mark what you see at (d).
**Total: 8 marks**1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e02c4a9a-d2ab-489f-b838-9b4d902c4457-2_782_974_379_539}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents the distances, in km, between eight vertices, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }$ and H in a network.
\begin{enumerate}[label=(\alph*)]
\item Use Kruskal's algorithm to find the 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 Starting at A, use Prim's algorithm to find the minimum spanning tree. You must clearly state the order in which you selected the arcs of your tree.\\
(3)
\item Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
\item State the weight of the tree.\\
(1)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2012 Q1 [8]}}