| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Standard +0.3 This is a standard D1 question testing routine application of Kruskal's algorithm and TSP bounds. Part (i) requires understanding MST properties (straightforward conceptual recall), parts (ii) and (iv) are mechanical algorithm applications following prescribed steps, and part (iii) uses a standard deletion method for lower bounds. No novel problem-solving or insight required—just careful execution of learned procedures. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| A | \(B\) | C | D | E | \(F\) | G | \(H\) | |
| A | - | 10 | - | 9 | 10 | - | - | - |
| B | 10 | - | 8 | 5 | - | - | - | - |
| C | - | 8 | - | 9 | - | 10 | - | - |
| D | 9 | 5 | 9 | - | 6 | 7 | 8 | - |
| E | 10 | - | - | 6 | - | 一 | 9 | 7 |
| F | - | - | 10 | 7 | - | - | 5 | - |
| G | - | - | - | 8 | 9 | 5 | - | 8 |
| H | - | - | - | - | 7 | - | 8 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| When the deleted vertex is a leaf (degree 1) in the minimum spanning tree | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Select arcs: BD=5, FG=5, DE=6, DF=7, EH=7, BC=8, GH=8 (reject DG=8 as cycle), AD=9 | M1 | Applying Kruskal's correctly |
| Correct MST drawn with total weight = \(5+5+6+7+7+8+8+9 = 55\) | A1A1A1 | A1 correct arcs, A1 no cycles, A1 correct weight |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| MST of reduced network (without A): weight = \(5+5+6+7+7+8+8 = 46\) | M1 | Finding MST without A |
| Lower bound = \(46 + 9 + 10 = 65\) | A1 | Adding two smallest arcs from A: AD=9, AE=10 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route: \(A \to D(9) \to B(5) \to C(8) \to F(10) \to G(5) \to H(8) \to E(7) \to A(10)\) | M1 | Applying nearest neighbour correctly |
| Upper bound = \(9+5+8+10+5+8+7+10 = 62\) | A1A1 | A1 valid Hamiltonian cycle, A1 correct total |
# Question 2:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| When the deleted vertex is a leaf (degree 1) in the minimum spanning tree | B1 | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Select arcs: BD=5, FG=5, DE=6, DF=7, EH=7, BC=8, GH=8 (reject DG=8 as cycle), AD=9 | M1 | Applying Kruskal's correctly |
| Correct MST drawn with total weight = $5+5+6+7+7+8+8+9 = 55$ | A1A1A1 | A1 correct arcs, A1 no cycles, A1 correct weight |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| MST of reduced network (without A): weight = $5+5+6+7+7+8+8 = 46$ | M1 | Finding MST without A |
| Lower bound = $46 + 9 + 10 = 65$ | A1 | Adding two smallest arcs from A: AD=9, AE=10 |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: $A \to D(9) \to B(5) \to C(8) \to F(10) \to G(5) \to H(8) \to E(7) \to A(10)$ | M1 | Applying nearest neighbour correctly |
| Upper bound = $9+5+8+10+5+8+7+10 = 62$ | A1A1 | A1 valid Hamiltonian cycle, A1 correct total |
---2 (i) A minimum spanning tree is constructed for a network. A vertex and all arcs joined to it are then deleted from the network. Under what circumstances will the remaining arcs of the minimum spanning tree form a minimum spanning tree for the reduced network?
Joseph wants to use Kruskal's algorithm to find the minimum spanning tree for a network. He has sorted the arcs in the network by increasing order of weight.
$$\begin{array} { l l l l l l l }
B D = 5 & F G = 5 & D E = 6 & D F = 7 & E H = 7 & B C = 8 & D G = 8 \\
G H = 8 & A D = 9 & C D = 9 & E G = 9 & A B = 10 & A E = 10 & C F = 10
\end{array}$$
(ii) Use Kruskal's algorithm on the list in your answer book, crossing out arcs that are not used. Draw your minimum spanning tree and give its total weight.\\
(iii) By considering the minimum spanning tree for the reduced network formed when vertex $A$ and all arcs joined to $A$ are deleted, find a lower bound for the shortest closed cycle through every vertex on the original network.
The table shows the arc weights for the same network.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& A & $B$ & C & D & E & $F$ & G & $H$ \\
\hline
A & - & 10 & - & 9 & 10 & - & - & - \\
\hline
B & 10 & - & 8 & 5 & - & - & - & - \\
\hline
C & - & 8 & - & 9 & - & 10 & - & - \\
\hline
D & 9 & 5 & 9 & - & 6 & 7 & 8 & - \\
\hline
E & 10 & - & - & 6 & - & 一 & 9 & 7 \\
\hline
F & - & - & 10 & 7 & - & - & 5 & - \\
\hline
G & - & - & - & 8 & 9 & 5 & - & 8 \\
\hline
H & - & - & - & - & 7 & - & 8 & - \\
\hline
\end{tabular}
\end{center}
(iv) Apply the nearest neighbour method, starting at $A$, to find a cycle through every vertex. Hence write down an upper bound for the shortest closed cycle through every vertex on the network.
\hfill \mbox{\textit{OCR D1 2015 Q2 [10]}}