| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Easy -1.2 This is a straightforward application of Kruskal's algorithm with the edges already sorted by weight, requiring only mechanical execution of the algorithm (add edges in order, avoiding cycles) and basic arithmetic to sum the weights. No problem-solving or novel insight needed, just procedural recall. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| \(BC = 3\) | M1 | For selecting all arcs up to \(AB\) and deleting \(AB\) in list |
| \(FG = 4\) | A1 | For deleting \(AC\), \(DE\) in list and selecting arcs for tree correctly, indicated in any way |
| \(JL = 5\) | ||
| \(EG = 6\) | M1 | For a spanning tree drawn |
| \(AE = 7\) | A1 | For correct (minimum) spanning tree drawn |
| \(BG = 7\) | ||
| \(AB = 8\) | ||
| \(CH = 8\) | ||
| \(DF = 8\) | ||
| \(GJ = 8\) | ||
| \(HK = 8\) | ||
| \(AC = 9\) | ||
| \(DE = 9\) | ||
| \(FI = 9\) | ||
| \(GH = 9\) | ||
| \(IJ = 9\) | ||
| \(JK = 9\) | ||
| \(AD = 10\) | ||
| \(DG = 10\) | ||
| \(GK = 10\) | ||
| \(IL = 10\) | ||
| \(KL = 10\) | ||
| \(GI = 11\) | ||
| \(CG = 12\) | ||
| \(DI = 12\) | ||
| Total weight = 73 | B1 | For total = 73 |
| \(\mathbf{5}\) |
| $BC = 3$ | M1 | For selecting all arcs up to $AB$ and deleting $AB$ in list |
| $FG = 4$ | A1 | For deleting $AC$, $DE$ in list and selecting arcs for tree correctly, indicated in any way |
| $JL = 5$ | | |
| $EG = 6$ | M1 | For a spanning tree drawn |
| $AE = 7$ | A1 | For correct (minimum) spanning tree drawn |
| $BG = 7$ | | |
| $AB = 8$ | | |
| $CH = 8$ | | |
| $DF = 8$ | | |
| $GJ = 8$ | | |
| $HK = 8$ | | |
| $AC = 9$ | | |
| $DE = 9$ | | |
| $FI = 9$ | | |
| $GH = 9$ | | |
| $IJ = 9$ | | |
| $JK = 9$ | | |
| $AD = 10$ | | |
| $DG = 10$ | | |
| $GK = 10$ | | |
| $IL = 10$ | | |
| $KL = 10$ | | |
| $GI = 11$ | | |
| $CG = 12$ | | |
| $DI = 12$ | | |
| Total weight = 73 | B1 | For total = 73 |
| | $\mathbf{5}$ | |1 Answer this question on the insert provided.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{8f17020a-14bf-4459-9241-1807b954a629-2_956_1203_349_493}
\end{center}
This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.
\hfill \mbox{\textit{OCR D1 2006 Q1 [5]}}