| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Calculate Specific Tour Length |
| Difficulty | Moderate -0.8 This is a straightforward application of standard TSP algorithms from D1. Part (a) requires simple arithmetic from a table, part (b) is a routine minimum spanning tree calculation for a lower bound, and part (c) asks students to combine given bounds into an interval. All techniques are standard textbook exercises with no novel problem-solving required. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) | \(\boldsymbol { F }\) | |
| \(\boldsymbol { A }\) | - | 8 | 6 | 9 | 12 | 7 |
| \(\boldsymbol { B }\) | 8 | - | 10 | 14 | 13 | 8 |
| \(\boldsymbol { C }\) | 6 | 10 | - | 7 | 16 | 10 |
| \(\boldsymbol { D }\) | 9 | 14 | 7 | - | 15 | 5 |
| \(\boldsymbol { E }\) | 12 | 13 | 16 | 15 | - | 11 |
| \(\boldsymbol { F }\) | 7 | 8 | 10 | 5 | 11 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(A\ B\ C\ D\ E\ F\ A\) | M1 | 6 values |
| \(8\ 10\ 7\ 15\ 11\ 7 = 58\) | A1 | Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(A \to C \to D \to F \to B \to E \to A\) | M1 | Tour starting and finishing at \(A\) |
| \(6\quad 7\quad 5\quad 8\quad 13\quad 12\) | M1 | Visits all vertices |
| A1 | Correct order | |
| \(= 51\) | B1 | Total: 4 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Delete \(A\) | M1 | SCA (MST plus 2 edges) |
| Graph with edges \(B\)-\(F\): 8, \(F\)-\(E\): 11, \(F\)-\(D\): 5, \(C\)-\(D\): 7 | M1 | 4 edges (not including \(A\)) |
| Correct MST diagram | A1 | |
| Their MST \(+ 6\ (AC) + 7\ (AF)\) | M1 | |
| Total \(= 44\) | A1 | Total: 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(45 \leq T \leq 51\) | M1 | Use of inequalities |
| A1F | 45 | |
| \(\max(45/\text{their(b)}) \leq T \leq \min(\text{their (a)})\) | A1F | 51 — Total: 3 |
## Question 7(a)(i):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $A\ B\ C\ D\ E\ F\ A$ | M1 | 6 values |
| $8\ 10\ 7\ 15\ 11\ 7 = 58$ | A1 | Total: 2 |
## Question 7(a)(ii):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $A \to C \to D \to F \to B \to E \to A$ | M1 | Tour starting and finishing at $A$ |
| $6\quad 7\quad 5\quad 8\quad 13\quad 12$ | M1 | Visits all vertices |
| | A1 | Correct order |
| $= 51$ | B1 | Total: 4 |
## Question 7(b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Delete $A$ | M1 | SCA (MST plus 2 edges) |
| Graph with edges $B$-$F$: 8, $F$-$E$: 11, $F$-$D$: 5, $C$-$D$: 7 | M1 | 4 edges (not including $A$) |
| Correct MST diagram | A1 | |
| Their MST $+ 6\ (AC) + 7\ (AF)$ | M1 | |
| Total $= 44$ | A1 | Total: 5 |
## Question 7(c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $45 \leq T \leq 51$ | M1 | Use of inequalities |
| | A1F | 45 |
| $\max(45/\text{their(b)}) \leq T \leq \min(\text{their (a)})$ | A1F | 51 — Total: 3 |
---7 Rob delivers bread to six shops $A , B , C , D , E$ and $F$. Each day, Rob starts at shop $A$, travels to each of the other shops before returning to shop $A$. The table shows the distances, in miles, between the shops.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ & $\boldsymbol { E }$ & $\boldsymbol { F }$ \\
\hline
$\boldsymbol { A }$ & - & 8 & 6 & 9 & 12 & 7 \\
\hline
$\boldsymbol { B }$ & 8 & - & 10 & 14 & 13 & 8 \\
\hline
$\boldsymbol { C }$ & 6 & 10 & - & 7 & 16 & 10 \\
\hline
$\boldsymbol { D }$ & 9 & 14 & 7 & - & 15 & 5 \\
\hline
$\boldsymbol { E }$ & 12 & 13 & 16 & 15 & - & 11 \\
\hline
$\boldsymbol { F }$ & 7 & 8 & 10 & 5 & 11 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Find the length of the tour $A B C D E F A$.
\item Find the length of the tour obtained by using the nearest neighbour algorithm starting from $A$.
\end{enumerate}\item By deleting $A$, find a lower bound for the length of a minimum tour.
\item By deleting $F$, another lower bound of 45 miles is obtained for the length of a minimum tour.
The length of a minimum tour is $T$ miles. Write down the smallest interval for $T$ which can be obtained from your answers to parts (a) and (b), and the information given in this part.\\
(3 marks)
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2005 Q7 [16]}}