| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Apply Prim's Algorithm |
| Difficulty | Moderate -0.5 This is a standard D1 question testing routine application of Prim's algorithm, deletion method for lower bound, and nearest neighbour algorithm. All three parts follow textbook procedures with no novel problem-solving required. The table is straightforward with 6 vertices, making it easier than average A-level maths questions but typical for D1 algorithmic work. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| A | B | C | D | E | F | |
| A | - | 6 | 3 | - | - | - |
| B | 6 | - | 5 | 6 | - | 14 |
| C | 3 | 5 | - | 8 | 4 | 10 |
| D | - | 6 | 8 | - | 3 | 8 |
| E | - | - | 4 | 3 | - | - |
| F | - | 14 | 10 | 8 | - | - |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | M1 | |
| Order: \(A \; C \; E \; D \; B \; F\) | B1 | For correct order, listed or marked on arrows or table, or arcs listed \(AC \; CE \; ED \; CB \; DF\) |
| Minimum spanning tree: | B1 | For tree (correct or follow through from table, provided solution forms a spanning tree) |
| (Shows A connected to C, C connected to E and D, E connected to F, B connected elsewhere) | ||
| Total weight: 23 miles | B1 | For 23 (or follow through from table or diagram, provided solution forms a spanning tree) |
| (ii) | MST for reduced network = 18 Two shortest arcs from \(B = 5 + 6 = 11\) Lower bound = 29 miles | M1, M1, A1, 3 |
| (iii) | \(F - D - E - C - A - B - F\) | M1, A1 |
| \(8 + 3 + 4 + 3 + 6 + 14 = 38\) miles | M1, A1, 13 | For a substantially correct attempt at sum For 38 (cao) |
(i) | | M1 | For choosing row C in column $A$
| Order: $A \; C \; E \; D \; B \; F$ | B1 | For correct order, listed or marked on arrows or table, or arcs listed $AC \; CE \; ED \; CB \; DF$
| Minimum spanning tree: | B1 | For tree (correct or follow through from table, provided solution forms a spanning tree)
| | | (Shows A connected to C, C connected to E and D, E connected to F, B connected elsewhere)
| Total weight: 23 miles | B1 | For 23 (or follow through from table or diagram, provided solution forms a spanning tree)
(ii) | MST for reduced network = 18 Two shortest arcs from $B = 5 + 6 = 11$ Lower bound = 29 miles | M1, M1, A1, 3 | For their 18 seen or implied For 11 seen or implied For 29 (cao)
(iii) | $F - D - E - C - A - B - F$ | M1, A1 | For $F - D - E - C - A - B$ For correct tour
| $8 + 3 + 4 + 3 + 6 + 14 = 38$ miles | M1, A1, 13 | For a substantially correct attempt at sum For 38 (cao)6 Answer this question on the insert provided.
The table shows the distances, in miles, along the direct roads between six villages, $A$ to $F$. A dash ( - ) indicates that there is no direct road linking the villages.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
& A & B & C & D & E & F \\
\hline
A & - & 6 & 3 & - & - & - \\
\hline
B & 6 & - & 5 & 6 & - & 14 \\
\hline
C & 3 & 5 & - & 8 & 4 & 10 \\
\hline
D & - & 6 & 8 & - & 3 & 8 \\
\hline
E & - & - & 4 & 3 & - & - \\
\hline
F & - & 14 & 10 & 8 & - & - \\
\hline
\end{tabular}
\end{center}
(i) On the table in the insert, use Prim's algorithm to find a minimum spanning tree. Start by crossing out row A. Show which entries in the table are chosen and indicate the order in which the rows are deleted. Draw your minimum spanning tree and state its total weight.\\
(ii) By deleting vertex B and the arcs joined to vertex B, calculate a lower bound for the length of the shortest cycle through all the vertices.\\
(iii) A pply the nearest neighbour method to the table above, starting from $F$, to find a cycle that passes through every vertex and use this to write down an upper bound for the length of the shortest cycle through all the vertices.\\
{}\\
\hfill \mbox{\textit{OCR D1 2007 Q6 [13]}}