| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Asymmetric Distance Matrix |
| Difficulty | Moderate -0.3 This is a standard D1 travelling salesman problem with routine algorithmic application. Part (a) requires simple recall of definition, part (b)(i) is mechanical nearest neighbour algorithm execution, part (b)(ii) tests basic understanding of upper bounds, and part (c) involves straightforward enumeration with constraints. While the asymmetric matrix adds minor complexity, the question follows a predictable textbook format with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \backslashbox{From}{To} | A | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | E | \(F\) |
| A | - | 25 | 20 | 20 | 27 | 25 |
| \(\boldsymbol { B }\) | 15 | - | 10 | 11 | 15 | 30 |
| \(\boldsymbol { C }\) | 5 | 30 | - | 15 | 20 | 19 |
| \(\boldsymbol { D }\) | 20 | 25 | 15 | - | 25 | 10 |
| \(\boldsymbol { E }\) | 10 | 20 | 7 | 15 | - | 15 |
| F | 25 | 35 | 29 | 20 | 30 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A valid Hamiltonian cycle stated e.g. \(A \to B \to C \to D \to E \to F \to A\) | B1 | Must visit all 6 nodes exactly once |
| Returns to start correctly | B1 | 2 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(F \to D\) (20) | M1 | Correct first step |
| Correct sequence: \(F \to D \to C \to E \to B \to A \to F\) or equivalent with correct choices shown | A1 | |
| Total = 95 minutes confirmed | A1 | 3 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The nearest neighbour algorithm produces a Hamiltonian cycle | B1 | |
| Any Hamiltonian cycle gives a valid route, so the minimum cannot exceed this value | B1 | 2 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(F \to E\) (30), then \(E \to \ldots \to B\) before \(D\), route constructed with constraints applied | M1 | Correct start \(F \to E\) and \(B\) before \(D\) |
| Valid complete Hamiltonian cycle found satisfying constraints | A1 | |
| Total time calculated and stated as improved upper bound (less than 95) | A1 | 3 marks total |
# Question 5:
## Part (a) – Hamiltonian Cycle Example
| Answer | Marks | Guidance |
|--------|-------|----------|
| A valid Hamiltonian cycle stated e.g. $A \to B \to C \to D \to E \to F \to A$ | B1 | Must visit all 6 nodes exactly once |
| Returns to start correctly | B1 | 2 marks total |
## Part (b)(i) – Nearest Neighbour from F
| Answer | Marks | Guidance |
|--------|-------|----------|
| $F \to D$ (20) | M1 | Correct first step |
| Correct sequence: $F \to D \to C \to E \to B \to A \to F$ or equivalent with correct choices shown | A1 | |
| Total = 95 minutes confirmed | A1 | 3 marks total |
## Part (b)(ii) – Why this is an Upper Bound
| Answer | Marks | Guidance |
|--------|-------|----------|
| The nearest neighbour algorithm produces a Hamiltonian cycle | B1 | |
| Any Hamiltonian cycle gives a valid route, so the minimum cannot exceed this value | B1 | 2 marks total |
## Part (c) – Improved Upper Bound
| Answer | Marks | Guidance |
|--------|-------|----------|
| $F \to E$ (30), then $E \to \ldots \to B$ before $D$, route constructed with constraints applied | M1 | Correct start $F \to E$ and $B$ before $D$ |
| Valid complete Hamiltonian cycle found satisfying constraints | A1 | |
| Total time calculated and stated as improved upper bound (less than 95) | A1 | 3 marks total |5 Angelo is visiting six famous places in Palermo: $A , B , C , D , E$ and $F$. He intends to travel from one place to the next until he has visited all of the places before returning to his starting place. Due to the traffic system, the time taken to travel between two places may be different dependent on the direction travelled.
The table shows the times, in minutes, taken to travel between the six places.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
\backslashbox{From}{To} & A & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ & E & $F$ \\
\hline
A & - & 25 & 20 & 20 & 27 & 25 \\
\hline
$\boldsymbol { B }$ & 15 & - & 10 & 11 & 15 & 30 \\
\hline
$\boldsymbol { C }$ & 5 & 30 & - & 15 & 20 & 19 \\
\hline
$\boldsymbol { D }$ & 20 & 25 & 15 & - & 25 & 10 \\
\hline
$\boldsymbol { E }$ & 10 & 20 & 7 & 15 & - & 15 \\
\hline
F & 25 & 35 & 29 & 20 & 30 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Give an example of a Hamiltonian cycle in this context.
\item \begin{enumerate}[label=(\roman*)]
\item Show that, if the nearest neighbour algorithm starting from $F$ is used, the total travelling time for Angelo would be 95 minutes.
\item Explain why your answer to part (b)(i) is an upper bound for the minimum travelling time for Angelo.
\end{enumerate}\item Angelo starts from $F$ and visits $E$ next. He also visits $B$ before he visits $D$. Find an improved upper bound for Angelo's total travelling time.\\
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-11_2484_1709_223_153}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q5 [10]}}