Easy -1.2 This is a straightforward application of the nearest neighbour algorithm starting from a specified vertex. It requires only systematic execution of a standard algorithm with no problem-solving insight, making it easier than average. The small network size (5 vertices) and clear tabular data make it a routine D1 exercise.
8 Tony delivers paper to five offices, \(A , B , C , D\) and \(E\). Tony starts his deliveries at office \(E\) and travels to each of the other offices once, before returning to office \(E\). Tony wishes to keep his travelling time to a minimum.
The table shows the travelling times, in minutes, between the offices.
The lower bound (52) is not achievable / the optimal solution lies between 52 and 66 / this is not a Hamiltonian cycle so cannot represent an actual tour
B1
Comment on significance
I can see these are answer space pages for Question 9 from what appears to be an AQA Decision Mathematics paper, but there is no mark scheme content visible in these images.
The pages shown (pages 22, 23, and 24) contain only:
- The question text for Question 9
- Blank answer space lines for student responses
To get the mark scheme content for this question, you would need to provide the separate mark scheme document published by AQA for this paper (P65656/Jan13/MD01).
However, based on the question text, here is the worked solution for the 6 inequalities:
# Question 8:
## Part (a):
| $AC + CD + DB + BE + EA = 16 + 10 + 15 + 9 + 8 = 58$ minutes | B1 | Answer only |
## Part (b):
| Any tour starting at $E$ with total time 58, e.g. $EACDBE$ or $EDBDCA$ etc. (reverse of ACDBEA starting at E) | B1 | Must start and end at $E$ |
## Part (c):
| Start at $E$: nearest unvisited is $A$ (8) | M1 | Showing method of nearest neighbour |
| From $A$: nearest unvisited is $B$ (10) | | |
| From $B$: nearest unvisited is $D$ (15) | | |
| From $D$: nearest unvisited is $C$ (10) | A1 | Correct tour identified |
| Return $C$ to $E$: (23) | | |
| Tour $EABDCE$: $8 + 10 + 15 + 10 + 23 = 66$ minutes | A1 | Correct total |
| Upper bound = 66 minutes | A1 | |
## Part (d):
| Delete $E$ and its arcs | M1 | |
| Find minimum spanning tree for $\{A, B, C, D\}$ | M1 | |
| $AB = 10$, $CD = 10$, $BD = 15$: total = 35 | A1 | Correct MST edges and value |
| Add two smallest arcs from $E$: $EA = 8$, $EB = 9$ | A1 | |
| Lower bound $= 35 + 8 + 9 = 52$ minutes | A1 | |
## Part (e):
| Sketch showing edges $AB$, $CD$, $BD$, $EA$, $EB$ | B1 | Correct network drawn |
| The lower bound (52) is not achievable / the optimal solution lies between 52 and 66 / this is not a Hamiltonian cycle so cannot represent an actual tour | B1 | Comment on significance |
I can see these are answer space pages for Question 9 from what appears to be an AQA Decision Mathematics paper, but there is **no mark scheme content visible** in these images.
The pages shown (pages 22, 23, and 24) contain only:
- The **question text** for Question 9
- **Blank answer space** lines for student responses
To get the mark scheme content for this question, you would need to provide the **separate mark scheme document** published by AQA for this paper (P65656/Jan13/MD01).
---
However, based on the question text, here is the **worked solution** for the 6 inequalities:
8 Tony delivers paper to five offices, $A , B , C , D$ and $E$. Tony starts his deliveries at office $E$ and travels to each of the other offices once, before returning to office $E$. Tony wishes to keep his travelling time to a minimum.
The table shows the travelling times, in minutes, between the offices.
\hfill \mbox{\textit{AQA D1 2013 Q8 [12]}}