| Exam Board | AQA |
|---|---|
| Module | Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) |
| Session | Specimen |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.8 This is a standard application of the nearest neighbour algorithm and minimum spanning tree deletion method for TSP bounds, both routine procedures in Further Maths Decision. Parts (a)-(b) require mechanical application of algorithms, while (c)-(d) involve simple comparison of bounds, and (e) asks for contextual interpretation. No novel problem-solving or insight required beyond following learned procedures. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Hamiltonian cycle \(A \to C \to D \to E \to B \to A\), \((10 + 8 + 9 + 11 + 15)\) | M1 | Correct cycle starting at \(A\) using nearest neighbour algorithm |
| Upper bound \(= 53\) | A1 | Correctly determines and states the upper bound |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Minimum spanning tree connecting \(A\), \(D\), \(E\) and \(C\) (or 27 seen), with edges of weight 10, 9, 8 | B1 | Correctly determines minimum spanning tree |
| Two shortest arcs connected to \(B\): weights 11 and 12 | M1 | Correctly identifies the two shortest arcs connected to \(B\) |
| \(27 + 11 + 12 = 50\) | A1 | Calculates sum of minimum spanning tree and two shortest arcs |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Optimal time lies between 50 and 53 minutes; lower bound is not a Hamiltonian cycle so cannot confirm a cycle of less than 53 minutes exists | R1 | Infers correctly that optimal Hamiltonian cycle has weight between 50 and 53 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Model applies to typical tourist; Charlotte walks more slowly than the typical tourist | E1 | Evaluates answers in parts (a) and (b) with reference to a plausible reason |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| E.g. less traffic at night so travel time between monuments likely less than morning times; OR increased pedestrians at night making it slower | E1 | Plausible reason why times between monuments would differ in the evening |
# Question 5:
## Part 5(a):
| Answer | Mark | Guidance |
|--------|------|----------|
| Hamiltonian cycle $A \to C \to D \to E \to B \to A$, $(10 + 8 + 9 + 11 + 15)$ | M1 | Correct cycle starting at $A$ using nearest neighbour algorithm |
| Upper bound $= 53$ | A1 | Correctly determines and states the upper bound |
## Part 5(b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Minimum spanning tree connecting $A$, $D$, $E$ and $C$ (or 27 seen), with edges of weight 10, 9, 8 | B1 | Correctly determines minimum spanning tree |
| Two shortest arcs connected to $B$: weights 11 and 12 | M1 | Correctly identifies the two shortest arcs connected to $B$ |
| $27 + 11 + 12 = 50$ | A1 | Calculates sum of minimum spanning tree and two shortest arcs |
## Part 5(c):
| Answer | Mark | Guidance |
|--------|------|----------|
| Optimal time lies between 50 and 53 minutes; lower bound is not a Hamiltonian cycle so cannot confirm a cycle of less than 53 minutes exists | R1 | Infers correctly that optimal Hamiltonian cycle has weight between 50 and 53 |
## Part 5(d):
| Answer | Mark | Guidance |
|--------|------|----------|
| Model applies to typical tourist; Charlotte walks more slowly than the typical tourist | E1 | Evaluates answers in parts (a) and (b) with reference to a plausible reason |
## Part 5(e):
| Answer | Mark | Guidance |
|--------|------|----------|
| E.g. less traffic at night so travel time between monuments likely less than morning times; OR increased pedestrians at night making it slower | E1 | Plausible reason why times between monuments would differ in the evening |
---5 Charlotte is visiting a city and plans to visit its five monuments: $A , B , C , D$ and $E$.\\
The network shows the time, in minutes, that a typical tourist would take to walk between the monuments on a busy weekday morning.\\
\includegraphics[max width=\textwidth, alt={}, center]{ba9e9840-ce27-4ca7-ab05-50461d135445-06_902_1134_529_543}
Charlotte intends to walk from one monument to another until she has visited them all, before returning to her starting place.
5
\begin{enumerate}[label=(\alph*)]
\item Use the nearest neighbour algorithm, starting from $A$, to find an upper bound for the minimum time for Charlotte's tour.\\
5
\item By deleting vertex $B$, find a lower bound for the minimum time for Charlotte's tour.\\[0pt]
[3 marks]\\
5
\item Charlotte wants to complete the tour in 52 minutes. Use your answers to parts (a) and (b) to comment on whether this could be possible.\\
5
\item Charlotte takes 58 minutes to complete the tour. Evaluate your answers to part (a) and part (b) given this information.\\
5
\item Explain how this model for a typical tourist's tour may not be applicable if the tourist walked between the monuments during the evening.
\end{enumerate}
\hfill \mbox{\textit{AQA Further AS Paper 2 Discrete Q5 [8]}}