| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Session | Specimen |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Explain algorithm properties or choices |
| Difficulty | Moderate -0.8 This is a conceptual question about MST algorithms requiring explanation and a counterexample diagram rather than computation. Part (i) requires understanding why Kruskal's algorithm must include the two smallest edges (they cannot form a cycle), which is straightforward reasoning. Part (ii) asks for a simple counterexample diagram showing the third smallest edge might create a cycle. Both parts test basic understanding of the algorithm rather than problem-solving skills, making this easier than average A-level questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | The arc with smallest weight cannot create a cycle (only one arc added so far), so it is always included. The arc with second smallest weight: if it created a cycle it would need to connect the same two nodes as the first arc, but as all weights are different and direct paths are shorter than indirect paths, this cannot happen. So it is always included. | M1, A1, A1 |
| (ii) | Diagram showing 4 nodes where the third smallest arc completes a cycle with the two already selected arcs, e.g. a triangle on three of the four nodes with appropriate weights | M1, A1, A1, A1 |
# Question 2:
**(i)** | The arc with smallest weight cannot create a cycle (only one arc added so far), so it is always included. The arc with second smallest weight: if it created a cycle it would need to connect the same two nodes as the first arc, but as all weights are different and direct paths are shorter than indirect paths, this cannot happen. So it is always included. | M1, A1, A1 | Credit clear logical argument referencing cycle condition
**(ii)** | Diagram showing 4 nodes where the third smallest arc completes a cycle with the two already selected arcs, e.g. a triangle on three of the four nodes with appropriate weights | M1, A1, A1, A1 | Must have at least 3 arcs shown with valid weights satisfying the given conditions
---2 This question is about a simply connected network with at least three arcs joining 4 nodes. The weights on the arcs are all different and any direct paths always have a smaller weight than the total weight of any indirect paths between two vertices.\\
(i) Kruskal's algorithm is used to construct a minimum connector. Explain why the arcs with the smallest and second smallest weights will always be included in this minimum connector.\\
(ii) Draw a diagram to show that the arc with the third smallest weight need not always be included in a minimum connector.
\hfill \mbox{\textit{OCR D1 Q2 [7]}}