| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Multiple Nearest Neighbour Routes |
| Difficulty | Standard +0.3 This is a standard D1 travelling salesman problem requiring routine application of nearest neighbour algorithm (twice), Prim's algorithm for lower bound, and Chinese Postman analysis. All are textbook procedures with no novel insight required, though the multi-part nature and need for careful bookkeeping make it slightly above trivial difficulty. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks |
|---|---|
| M1 | For \(A\text{-}B\text{-}D\text{-}E\text{-}G\text{-}F\text{-}C\text{-}A\), with or without closing tour |
| A1 | For 42 |
| Answer | Marks |
|---|---|
| B1 | For \(A\text{-}B\text{-}D\text{-}C\text{-}F\text{-}G\text{-}E\), with or without closing tour |
| B1 | For 46 |
| Answer | Marks |
|---|---|
| B1ft(5) | For the smaller of their two times |
| Answer | Marks |
|---|---|
| M1 | For a diagram or listing showing a tree connecting the vertices \(A, B, C, D, E\) and \(F\), but not \(G\) |
| A1 | For a diagram showing this tree (vertices need to be labelled, but arc weights are not needed) |
| Answer | Marks |
|---|---|
| B1 | For a valid vertex or arc order |
| A1 ft | For the total weight of their tree stated |
Total weight of tree = 31 minutes
| Answer | Marks |
|---|---|
| M1 | For the total weight of their tree stated |
| A1 (6) | For stating or using \(GE, GF\) or \(5 + 5\) or 10 for 41 or 10 + their 31 calculated |
| Answer | Marks |
|---|---|
| B1 | For identifying or using \(BDEF\) |
| Answer | Marks |
|---|---|
| M1 | For calculating \(5 + 10\) or \(6 + 14\) or \(16 + 7\) (may be implied plus correct pairs chosen) |
| \(\frac{120}{23}\) minutes | |
| A1 | For 120 (unsupported 120 scores 0 of marks) |
| B1 (5) | For correct arcs listed and no others |
| B1 | For 3 |
| \(\mathbf{16}\) |
**(i)** $A\text{-}B\text{-}D\text{-}E\text{-}G\text{-}F\text{-}C\text{-}A$
42 minutes
| M1 | For $A\text{-}B\text{-}D\text{-}E\text{-}G\text{-}F\text{-}C\text{-}A$, with or without closing tour |
| A1 | For 42 |
$A\text{-}B\text{-}D\text{-}C\text{-}F\text{-}G\text{-}E\text{-}A$
46 minutes
| B1 | For $A\text{-}B\text{-}D\text{-}C\text{-}F\text{-}G\text{-}E$, with or without closing tour |
| B1 | For 46 |
Upper bound = 42 minutes
| B1ft(5) | For the smaller of their two times |
**(ii)** [Diagram showing a tree connecting vertices $A, B, C, D, E$ and $F$, but not $G$]
| M1 | For a diagram or listing showing a tree connecting the vertices $A, B, C, D, E$ and $F$, but not $G$ |
| A1 | For a diagram showing this tree (vertices need to be labelled, but arc weights are not needed) |
$ABDC\text{-}E\text{-}F$ or $ABDC EF$
| B1 | For a valid vertex or arc order |
| A1 ft | For the total weight of their tree stated |
Total weight of tree = 31 minutes
Two least weight arcs from $G$ have weight $5 + 5 = 10$ minutes
| M1 | For the total weight of their tree stated |
| A1 (6) | For stating or using $GE, GF$ or $5 + 5$ or 10 for 41 or 10 + their 31 calculated |
Lower bound = 31 + 10 = 41 minutes
**(iii)** Odd nodes: $B, D, E, F$
| B1 | For identifying or using $BDEF$ |
$BD = 5$, $BE = 6$, $BF = 16$
$EF = 10$, $DF = 14$, $DE = 7$
| M1 | For calculating $5 + 10$ or $6 + 14$ or $16 + 7$ (may be implied plus correct pairs chosen) |
| | $\frac{120}{23}$ minutes |
| A1 | For 120 (unsupported 120 scores 0 of marks) |
| B1 (5) | For correct arcs listed and no others |
| B1 | For 3 |
| | $\mathbf{16}$ |
Travel $BD, EG$ and $FG$ twice (accept $BD, EGF$)
3 times6 The network represents a railway system. The vertices represent the stations and the arcs represent the tracks. The weights on the arcs represent journey times between stations, in minutes. The sum of all the weights is 105 minutes.\\
\includegraphics[max width=\textwidth, alt={}, center]{8f17020a-14bf-4459-9241-1807b954a629-5_981_1215_468_477}
Norah wants to travel around the system visiting every station. She wants to start and end at $A$ and she wants to complete her journey in the shortest possible time.\\
(i) Apply the nearest neighbour method starting at $A$ to find two suitable tours and calculate the journey time for each of these tours. Which of these answers gives the better upper bound for Norah's journey time?\\
(ii) Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex $G$ and all the arcs that are directly joined to $G$. Draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Norah's journey time.
Norah now decides that she wants to use every section of track in her journey. She still wants to start and end at $A$ and to complete her journey in the shortest possible time.\\
(iii) Calculate the journey time for Norah's new problem. Show your working; quickest times between stations may be found by inspection. State which arcs Norah will have to travel twice and how many times she will pass through station $D$.
\hfill \mbox{\textit{OCR D1 2006 Q6 [16]}}