| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Easy -1.3 This is a straightforward application of Prim's algorithm in matrix form, which is a standard algorithmic procedure taught in D1. Part (i) requires only basic observation (triangle inequality), and part (ii) is pure mechanical execution of a learned algorithm with no problem-solving or insight required—significantly easier than average A-level maths questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | |
| A | 6 | 7 | 12 | 3 | ||
| B | 6 | 10 | 8 | |||
| C | 7 | 10 | 2 | |||
| D | 12 | 2 | 9 | 8 | ||
| E | 8 | 9 | ||||
| F | 3 | 8 |
| Answer | Marks | Guidance |
|---|---|---|
| (i) \(ACD\) is \(7+2 = 9\) \((<12)\) or \(AFD\) is \(3+8 = 11\) \((<12)\); \(AD\) could by via some point of interest, or over difficult terrain, or ... The triangle inequality applies to triangles! | B1, B1 | needs numerical justification |
| (ii) | M1, M1, M1, A1 | starting at and crossing row A (i.e. no selection in row); selecting FA and BA (or first two arcs following wrong start); numbering columns A, F and B (similarly); all correct (dependent on 3 Ms) (can cross all rows) |
| (iii) | ||
| cao (weights not needed) | B1 | |
| cao | B1 | 26 (miles) |
**(i)** $ACD$ is $7+2 = 9$ $(<12)$ or $AFD$ is $3+8 = 11$ $(<12)$; $AD$ could by via some point of interest, or over difficult terrain, or ... The triangle inequality applies to triangles! | B1, B1 | needs numerical justification
**(ii)** | M1, M1, M1, A1 | starting at and crossing row A (i.e. no selection in row); selecting FA and BA (or first two arcs following wrong start); numbering columns A, F and B (similarly); all correct (dependent on 3 Ms) (can cross all rows)
**(iii)** | | |
cao (weights not needed) | B1 |
cao | B1 | 26 (miles)3 Six remote villages are linked by a set of roads. Two villages are connected directly if there is a road between them which does not pass through another village. The table gives the lengths in miles of all direct connections.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & & 6 & 7 & 12 & & 3 \\
\hline
B & 6 & & 10 & & 8 & \\
\hline
C & 7 & 10 & & 2 & & \\
\hline
D & 12 & & 2 & & 9 & 8 \\
\hline
E & & 8 & & 9 & & \\
\hline
F & 3 & & & 8 & & \\
\hline
\end{tabular}
\end{center}
(i) Why might it be thought surprising that the direct distance between A and D is as long as 12 miles? Give a possible reason why the distance is longer than might have been expected.\\
(ii) Use the tabular form of Prim's algorithm, starting at A , to find a minimum connector for these villages. Draw your connector and give its total length.
\hfill \mbox{\textit{OCR MEI D1 2014 Q3 [8]}}