| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Moderate -0.8 This is a routine algorithmic application question requiring mechanical execution of Prim's algorithm in tabular form (a standard D1 procedure) followed by Dijkstra's algorithm. Both are well-practiced techniques with clear step-by-step methods. Part (iii) requires re-checking the algorithms with one changed value, which is straightforward. The question tests procedural fluency rather than problem-solving or insight, making it easier than average A-level maths questions. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | |
| A | - | 10 | - | - | - | 12 | 15 |
| B | 10 | - | 15 | 20 | - | - | 8 |
| C | - | 15 | - | 7 | - | - | 11 |
| D | - | 20 | 7 | - | 20 | - | 13 |
| E | - | - | - | 20 | - | 17 | 9 |
| F | 12 | - | - | - | 17 | - | 13 |
| G | 15 | 8 | 11 | 13 | 9 | 13 | - |
| Answer | Marks |
|---|---|
| (i) Matrix of distances between towns A–G; Network diagram showing connections with total length = 57 miles used to determine where to lay pipes or cables to connect towns | M1 selections; A1 order of selecting; A1 deletions; B1 |
| (ii) Dijkstra's algorithm applied: See Dijkstra labels; order of labelling; working values; Shortest route: AGE with length 24 | M1 sca Dijkstra; A1 labels; A1 order of labelling; A1 working values |
| (iii) Shortens MST to 53 miles (\(\surd\) by 4); New shortest route ABGE = 23 miles (\(\surd\) by 1) | B1; B1; B1; B1 B1 |
**(i)** Matrix of distances between towns A–G; Network diagram showing connections with total length = 57 miles used to determine where to lay pipes or cables to connect towns | M1 selections; A1 order of selecting; A1 deletions; B1 |
**(ii)** Dijkstra's algorithm applied: See Dijkstra labels; order of labelling; working values; Shortest route: AGE with length 24 | M1 sca Dijkstra; A1 labels; A1 order of labelling; A1 working values |
**(iii)** Shortens MST to 53 miles ($\surd$ by 4); New shortest route ABGE = 23 miles ($\surd$ by 1) | B1; B1; B1; B1 B1 |
---5 Answer this question on the insert provided.
Table 5 specifies a road network connecting 7 towns, A, B, $\ldots$, G. The entries in Table 5 give the distances in miles between towns which are connected directly by roads.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G \\
\hline
A & - & 10 & - & - & - & 12 & 15 \\
\hline
B & 10 & - & 15 & 20 & - & - & 8 \\
\hline
C & - & 15 & - & 7 & - & - & 11 \\
\hline
D & - & 20 & 7 & - & 20 & - & 13 \\
\hline
E & - & - & - & 20 & - & 17 & 9 \\
\hline
F & 12 & - & - & - & 17 & - & 13 \\
\hline
G & 15 & 8 & 11 & 13 & 9 & 13 & - \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 5}
\end{center}
\end{table}
(i) Using the copy of Table 5 in the insert, apply the tabular form of Prim's algorithm to the network, starting at vertex A. Show the order in which you connect the vertices.
Draw the resulting tree, give its total length and describe a practical application.\\
(ii) The network in the insert shows the information in Table 5. Apply Dijkstra's algorithm to find the shortest route from A to E.
Give your route and its length.\\
(iii) A tunnel is built through a hill between A and B , shortening the distance between A and B to 6 miles. How does this affect your answers to parts (i) and (ii)?
\hfill \mbox{\textit{OCR MEI D1 2006 Q5 [16]}}