| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 8 |
| 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 straightforward application of Prim's algorithm in matrix form with a small 5-vertex network, followed by standard lower/upper bound calculations for TSP. The algorithm is mechanical with clear steps, and the TSP bounds use routine methods taught directly in D1. Easier than average A-level maths due to algorithmic rather than mathematical reasoning. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| \multirow{2}{*}{} | Room | |||||
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | ||
| \multirow{5}{*}{Room} | \(A\) | - | 12 | 30 | 15 | 22 |
| B | 12 | - | 24 | 16 | 30 | |
| C | 30 | 24 | - | 20 | 25 | |
| D | 15 | 16 | 20 | - | 10 | |
| E | 22 | 30 | 25 | 10 | - | |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Starting at \(A\): select \(AB=12\) | M1 | Correct application of Prim's |
| \(AB=12, AD=15, DE=10, DB=16\) — select in order \(AB, AD, DE, DC\) | A1 | Correct order of arc selection |
| Arcs: \(AB(12), AD(15), DE(10), DC(20)\) | A1 | |
| Tree drawn correctly | A1 | Total length \(= 57\) m [4] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Lower bound: MST weight \(+ \) two shortest arcs from deleted vertex | M1 | |
| Correct lower bound calculated | A1 | |
| Nearest neighbour from \(A\): correct sequence shown | M1 | |
| Upper bound stated | A1 | [4] |
# Question 2:
## Part (i) - Prim's Algorithm
| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting at $A$: select $AB=12$ | M1 | Correct application of Prim's |
| $AB=12, AD=15, DE=10, DB=16$ — select in order $AB, AD, DE, DC$ | A1 | Correct order of arc selection |
| Arcs: $AB(12), AD(15), DE(10), DC(20)$ | A1 | |
| Tree drawn correctly | A1 | Total length $= 57$ m **[4]** |
## Part (ii) - Lower and Upper Bounds
| Answer | Marks | Guidance |
|--------|-------|----------|
| Lower bound: MST weight $+ $ two shortest arcs from deleted vertex | M1 | |
| Correct lower bound calculated | A1 | |
| Nearest neighbour from $A$: correct sequence shown | M1 | |
| Upper bound stated | A1 | **[4]** |
---2 Five rooms, $A , B , C , D , E$, in a building need to be connected to a computer network using expensive cabling. Rob wants to find the cheapest way to connect the rooms by finding a minimum spanning tree for the cable lengths. The length of cable, in metres, needed to connect each pair of rooms is given in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
\multicolumn{2}{|c|}{\multirow{2}{*}{}} & \multicolumn{5}{|c|}{Room} \\
\hline
& & $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
\multirow{5}{*}{Room} & $A$ & - & 12 & 30 & 15 & 22 \\
\hline
& B & 12 & - & 24 & 16 & 30 \\
\hline
& C & 30 & 24 & - & 20 & 25 \\
\hline
& D & 15 & 16 & 20 & - & 10 \\
\hline
& E & 22 & 30 & 25 & 10 & - \\
\hline
\end{tabular}
\end{center}
(i) Apply Prim's algorithm in matrix (table) form, starting at vertex $A$ and showing all your working. Write down the order in which arcs were added to the tree. Draw the resulting tree and state the length of cable needed.
A sixth room, $F$, is added to the computer network. The distances from $F$ to each of the other rooms are $A F = 32 , B F = 29 , C F = 31 , D F = 35 , E F = 30$.\\
(ii) Use your answer to part (i) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex $A$, to find an upper bound for the length of this tour.
\hfill \mbox{\textit{OCR D1 2011 Q2 [8]}}