| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Moderate -0.5 This is a standard D1 question testing routine application of Kruskal's algorithm and nearest neighbour method, plus some spatial reasoning about a cube. Part (i) is textbook MST application, part (ii) is standard algorithm execution, and part (iii) requires only basic logical deduction about cube geometry. The multi-part structure adds length but not conceptual difficulty—all techniques are direct applications of taught algorithms with no novel problem-solving required. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct spanning tree diagram (A,B,C,D,E,F,G,H) | M1 | For a correct tree (labels not required) |
| Kruskal: \(DF, CD, BD\) and \(EF, FH, AC, EG\) | A1 | For a valid order (using Prim or Kruskal) |
| Length \(= 40\) | B1 | For length \(= 40\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(A\ C\ D\ F\ E\ G\ H\ B\ A\) | M1 | At getting at least as far as \(A\ C\ D\ F\ E\) (or shown on diagram) |
| Correct cycle ending back at \(A\) | A1 | If shown on diagram, needs direction shown |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| (A) \(ACEG\) and \(ABGH\) | B1 | For both, vertices in any order |
| (B) 5 | B1 | For 5 |
| (C) \(ABCD\) | B1 | For \(ABCD\), vertices in any order |
# Question 3:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct spanning tree diagram (A,B,C,D,E,F,G,H) | M1 | For a correct tree (labels not required) |
| Kruskal: $DF, CD, BD$ and $EF, FH, AC, EG$ | A1 | For a valid order (using Prim or Kruskal) |
| Length $= 40$ | B1 | For length $= 40$ |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $A\ C\ D\ F\ E\ G\ H\ B\ A$ | M1 | At getting at least as far as $A\ C\ D\ F\ E$ (or shown on diagram) |
| Correct cycle ending back at $A$ | A1 | If shown on diagram, needs direction shown |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| (A) $ACEG$ and $ABGH$ | B1 | For both, vertices in any order |
| (B) 5 | B1 | For 5 |
| (C) $ABCD$ | B1 | For $ABCD$, vertices in any order |
---3 This diagram shows a network.\\
\includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-2_693_744_1307_694}
\begin{enumerate}[label=(\roman*)]
\item Obtain a minimum connector for this network. Draw your minimum connector, state the order in which the arcs were chosen and give their total weight.
\item Use the nearest neighbour method, starting from vertex $A$, to find a cycle that passes through every vertex.
The network represents a cubical die, with vertices labelled $A$ to $H$, and faces numbered from 1 to 6 in such a way that the numbers on each pair of opposite faces add up to 7 . When two faces meet in an edge, the sum of the numbers on the two faces is recorded as the weight on that edge.
\item (a) List the vertices of each of the two faces that meet in the edge $A G$.\\
(b) What number is on the face $A C E G$ ?\\
(c) Which face is numbered 3?
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2005 Q3 [8]}}