| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Apply Kruskal's Algorithm |
| Difficulty | Moderate -0.8 This is a standard application of Kruskal's algorithm with routine follow-up questions. While multi-part, each step involves direct application of well-practiced algorithms (Kruskal's, nearest neighbour) with no novel problem-solving required. The adaptations asked for are straightforward given the MST structure. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(CD=5, DE=7, AB=8, \cancel{CE=8}, FG=9, BC=10, \cancel{AC=11}, EF=12, \cancel{BF=14}, \cancel{EG=15}, \cancel{AD=16}, \cancel{DG=18}, \cancel{BE=20}, \cancel{AF=23}, \cancel{BG=24}, \cancel{CF=24}\) | B1 | Correct tree drawn (if return via \(GFBA\) is also shown then B0) |
| B1 | Evidence in list of \(CE\) and \(AC\) not being chosen, and everything else above \(AC\) being chosen | |
| Weight \(= 51\) | B1 | 51 (cao), must be seen, not implied from part of a calculation |
| \(A-B-C-D-E-F-G-F-B-A\) | B1 | This closed route, or in reverse, starting at any vertex (must be written). No credit for any other route |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Replace \(CD\) and \(DE\) with \(CE \Rightarrow 51 - 5 - 7 + 8 = 47\) | B1 | 47 or 'their \(51' - 4\) (do not need to see working) |
| \(A-B-C-E-F-G-D-A\) | B1 | This cycle, or in reverse, starting at any vertex (not as two parts) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A-B-C-D-E-F-G\) then stalls and cannot return to \(A\) | M1 | \(A-B-C-D-E-F-G\) (may go beyond \(G\)) must be written |
| A1 | 'stalls', 'stuck', 'fails', 'cannot return to \(A\)', 'node(s) visited twice', or similar. Do not allow 'it forms a mini-cycle/loop' | |
| \(B-A-C-D-E-F-G-B\) | M1 | \(B-A-C-D-E-F\) (must be written) |
| A1 | Complete cycle correct and in this order | |
| Swap \(F\) and \(G\) to get \(B-A-C-D-E-G-F-B = 69\) km | M1 | This cycle, or in reverse, starting at any vertex (must be written) |
| A1 | 69 (condone no units) |
# Question 4:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $CD=5, DE=7, AB=8, \cancel{CE=8}, FG=9, BC=10, \cancel{AC=11}, EF=12, \cancel{BF=14}, \cancel{EG=15}, \cancel{AD=16}, \cancel{DG=18}, \cancel{BE=20}, \cancel{AF=23}, \cancel{BG=24}, \cancel{CF=24}$ | B1 | Correct tree drawn (if return via $GFBA$ is also shown then B0) |
| | B1 | Evidence in list of $CE$ and $AC$ not being chosen, and everything else above $AC$ being chosen |
| Weight $= 51$ | B1 | 51 (cao), must be seen, not implied from part of a calculation |
| $A-B-C-D-E-F-G-F-B-A$ | B1 | This closed route, or in reverse, starting at any vertex (must be written). No credit for any other route |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Replace $CD$ and $DE$ with $CE \Rightarrow 51 - 5 - 7 + 8 = 47$ | B1 | 47 or 'their $51' - 4$ (do not need to see working) |
| $A-B-C-E-F-G-D-A$ | B1 | This cycle, or in reverse, starting at any vertex (not as two parts) |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A-B-C-D-E-F-G$ then stalls and cannot return to $A$ | M1 | $A-B-C-D-E-F-G$ (may go beyond $G$) must be written |
| | A1 | 'stalls', 'stuck', 'fails', 'cannot return to $A$', 'node(s) visited twice', or similar. Do not allow 'it forms a mini-cycle/loop' |
| $B-A-C-D-E-F-G-B$ | M1 | $B-A-C-D-E-F$ (must be written) |
| | A1 | Complete cycle correct and in this order |
| Swap $F$ and $G$ to get $B-A-C-D-E-G-F-B = 69$ km | M1 | This cycle, or in reverse, starting at any vertex (must be written) |
| | A1 | 69 (condone no units) |4 A simplified map of an area of moorland is shown below. The vertices represent farmhouses and the arcs represent the paths between the farmhouses. The weights on the arcs show distances in km.\\
\includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-4_618_1420_356_319}
Ted wants to visit each farmhouse and then return to his starting point.\\
(i) In your answer book the arcs have been sorted into increasing order of weight. Use Kruskal's algorithm to find a minimum spanning tree for the network, and give its total weight. Hence find a route visiting each farmhouse, and returning to the starting point, which has length 82 km .\\
(ii) Give the weight of the minimum spanning tree for the six vertices $A , B , C , E , F , G$. Hence find a route visiting each of the seven farmhouses once, and returning to the starting point, which has length 81 km .\\
(iii) Show that the nearest neighbour method fails to produce a cycle through every vertex when started from $A$ but that it succeeds when started from $B$. Adapt this cycle to find a complete cycle of total weight less than 70 , and find the total length of the shorter cycle.
\hfill \mbox{\textit{OCR D1 2013 Q4 [12]}}