| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 23 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Apply Kruskal's Algorithm |
| Difficulty | Moderate -0.3 This is a multi-part question testing standard D1 algorithms (Kruskal's, nearest neighbour, Dijkstra's, route inspection) with step-by-step guidance. While lengthy, each part applies textbook procedures with minimal problem-solving required. The algorithms are mechanical and well-practiced at this level, making it slightly easier than average despite the multiple parts. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.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 tree7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Delete \(EG\) from spanning tree; \(100 - 23 = 77\); Two shortest arcs from \(E\) are \(EG\) and \(EF\); \(77 + 23 + 26 = 126\); Lower bound \(= 126\) | B1, M1, A1 | Follow through from part (i); Weight of MST on reduced network; Adding two shortest arcs to MST; 126 cao |
| Answer | Marks | Guidance |
|---|---|---|
| \(A-B-D-F-G-E-\) stall | M1 | \(A-B-D-F-G-E\) |
| Misses out vertex \(C\) | A1 | Cannot continue because \(B\), \(D\) and \(F\) have already been visited |
| Answer | Marks | Guidance |
|---|---|---|
| \(B-A-C-D-F-G-E-B\) | M1, A1 | Tour starts \(B-A-C-D-F-\) ; Correct tour, starting and ending at \(B\) |
| Upper bound \(= 148\) | B1 | 148 cao |
| Answer | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm applied with correct temporary labels; Weight \(= 56\); Route \(= A-B-D-G\) | M1, A1, B1, B1, B1, B1 | At least three sets of temporary labels correct; Temporary labels all correct; Permanent labels correct; Order of labelling correct; 56 cao; \(A-B-D-G\) cao |
| Answer | Marks | Guidance |
|---|---|---|
| \(A, B, C\) and \(G\) are odd | B1 | Identifying or using \(A, B, C, G\) |
| \(AB=9\), \(AC=27\), \(AG=56\); \(CG=42\), \(BG=47\), \(BC=34\); totals \(51\), \(74\), \(90\); Repeat \(AB\) and \(CG\) \((C-F-G)=51\); Weight \(= 300 + 51 = 351\) | M1, A1, B1 | At least one correct pairing or total; All three totals correct or explanation; 351 cao |
# Question 3 (continued):
## Part (ii)
| Delete $EG$ from spanning tree; $100 - 23 = 77$; Two shortest arcs from $E$ are $EG$ and $EF$; $77 + 23 + 26 = 126$; Lower bound $= 126$ | B1, M1, A1 | Follow through from part (i); Weight of MST on reduced network; Adding two shortest arcs to MST; 126 cao | [3] |
## Part (iii)
| $A-B-D-F-G-E-$ stall | M1 | $A-B-D-F-G-E$ |
| Misses out vertex $C$ | A1 | Cannot continue because $B$, $D$ and $F$ have already been visited | [2] |
## Part (iv)
| $B-A-C-D-F-G-E-B$ | M1, A1 | Tour starts $B-A-C-D-F-$ ; Correct tour, starting and ending at $B$ |
| Upper bound $= 148$ | B1 | 148 cao | [3] |
## Part (v)
| Dijkstra's algorithm applied with correct temporary labels; Weight $= 56$; Route $= A-B-D-G$ | M1, A1, B1, B1, B1, B1 | At least three sets of temporary labels correct; Temporary labels all correct; Permanent labels correct; Order of labelling correct; 56 cao; $A-B-D-G$ cao | [6] |
## Part (vi)
| $A, B, C$ and $G$ are odd | B1 | Identifying or using $A, B, C, G$ |
| $AB=9$, $AC=27$, $AG=56$; $CG=42$, $BG=47$, $BC=34$; totals $51$, $74$, $90$; Repeat $AB$ and $CG$ $(C-F-G)=51$; Weight $= 300 + 51 = 351$ | M1, A1, B1 | At least one correct pairing or total; All three totals correct or explanation; 351 cao | [4] |
---3 Answer this question on the insert provided.
\includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-3_492_1006_356_568}\\
(i) This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.\\
(ii) Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex $E$, and all the arcs joined to $E$, removed. Hence find a lower bound for the travelling salesperson problem on the original network.\\
(iii) Show that the nearest neighbour method, starting from vertex $A$, fails on the original network.\\
(iv) Apply the nearest neighbour method, starting from vertex $B$, to find an upper bound for the travelling salesperson problem on the original network.\\
(v) Apply Dijkstra's algorithm to the copy of the network in the insert to find the least weight path from $A$ to $G$. State the weight of the path and give its route.\\
(vi) The sum of the weights of all the arcs is 300 .
Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. The weights of least weight paths from vertex $A$ should be found using your answer to part (v); the weights of other such paths should be determined by inspection.
\hfill \mbox{\textit{OCR D1 2009 Q3 [23]}}