| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2017 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | MST Method for Upper Bound |
| Difficulty | Moderate -0.8 This is a standard algorithmic question requiring mechanical application of two well-known methods (MST upper bound and nearest neighbour) with no problem-solving insight needed. The procedures are routine for D2 students, involving straightforward Prim's/Kruskal's algorithm followed by a shortcut, then greedy nearest neighbour selection. Part (b) is trivial comparison of bounds. While it has multiple parts worth 7 marks total, each step follows a memorized algorithm with no conceptual challenge beyond careful arithmetic. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| A | B | C | D | E | F | |
| A | - | 83 | 75 | 82 | 69 | 97 |
| B | 83 | - | 94 | 103 | 77 | 109 |
| C | 75 | 94 | - | 97 | 120 | 115 |
| D | 82 | 103 | 97 | - | 105 | 125 |
| E | 69 | 77 | 120 | 105 | - | 88 |
| F | 97 | 109 | 115 | 125 | 88 | - |
| Answer | Marks |
|---|---|
| Prim's starting from A: AE, AC, BE, AD; EF | M1 A1 |
| \(2 \times 391 = 782\) | B1 |
| Answer | Marks |
|---|---|
| Nearest neighbour: A – E – B – C – D – F – A | M1 |
| 69 77 94 97 125 97 = 559 | A1 (5) |
| Answer | Marks |
|---|---|
| \(500 \leq \text{length} \leq 559\) (accept \(500 < \text{length} \leq 559\)) | B2, 1, 0 (2) |
**Part (a)(i):**
Prim's starting from A: AE, AC, BE, AD; EF | M1 A1
$2 \times 391 = 782$ | B1
**Part (a)(ii):**
Nearest neighbour: A – E – B – C – D – F – A | M1
69 77 94 97 125 97 = 559 | A1 (5)
**Part (b):**
$500 \leq \text{length} \leq 559$ (accept $500 < \text{length} \leq 559$) | B2, 1, 0 (2)
**Notes for Question 1:**
- **a1M1:** First four arcs (or first five nodes: A, E, C, B, D or equivalent numbers across the top of the table {1, 4, 3, 5, 2, -}) selected correctly. Award M1 only for a correct tree with no working or for a correct tree starting at a different node
- **a1A1:** CAO (order of arcs correct or all six nodes correct: A, E, C, B, D, F – but not just the numbers across the top of the table)
- **a1B1:** CAO (782) – must follow from the correct MST (so dependent on at least the M mark in (a)(i)) – do not isw if attempt at short cuts reduces this value
- **a2M1:** Nearest neighbour A – E – B – C – D – F – (condone lack of return to start) or correct route length of 559. Accept AE, EB, BC, CD, DF but do not accept weights only
- **a2A1:** CAO both route (either in terms of vertices or arcs but not weights) and length correct
- **b1B1:** Any indication of an interval from 500 to their 559 (their 559 > 500 and is the smallest value from either the MST method or NN method – must have stated two values in (a) but ignore how these values were derived)
- **b2B1:** $500 \leq \text{length} \leq 559$ or $500 < \text{length} \leq 559$ (no ft on this mark) – accept set notation e.g. [500,559] or (500, 559]
---1.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
& A & B & C & D & E & F \\
\hline
A & - & 83 & 75 & 82 & 69 & 97 \\
\hline
B & 83 & - & 94 & 103 & 77 & 109 \\
\hline
C & 75 & 94 & - & 97 & 120 & 115 \\
\hline
D & 82 & 103 & 97 & - & 105 & 125 \\
\hline
E & 69 & 77 & 120 & 105 & - & 88 \\
\hline
F & 97 & 109 & 115 & 125 & 88 & - \\
\hline
\end{tabular}
\end{center}
The table above shows the least distances, in km , between six towns, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F .
\begin{enumerate}[label=(\alph*)]
\item Starting at A, and making your working clear, find an initial upper bound for the travelling salesperson problem for this network, using
\begin{enumerate}[label=(\roman*)]
\item the minimum spanning tree method,
\item the nearest neighbour algorithm.\\
(5)
By deleting A, and all of its arcs, a lower bound for the travelling salesperson problem for this network is found to be 500 km .
By deleting B, and all of its arcs, the corresponding lower bound is found to be 474 km .
\end{enumerate}\item Using the results from (a) and the given lower bounds, write down the smallest interval that you can be confident contains the solution to the travelling salesperson problem for this network.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2017 Q1 [7]}}