Question 7 - A-Level Maths

AQA D1 2012 June — Question 7 11 marks

Exam Board	AQA
Module	D1 (Decision Mathematics 1)
Year	2012
Session	June
Marks	11
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Travelling Salesman
Type	Nearest Neighbour Algorithm
Difficulty	Moderate -0.8 This is a straightforward application of the nearest neighbour algorithm, a standard D1 procedure requiring only systematic selection of minimum values from a table with no conceptual difficulty or problem-solving insight. The algorithm is purely mechanical and well-practiced, making it easier than average A-level questions that require mathematical reasoning.
Spec	7.04c Travelling salesman upper bound: nearest neighbour method 7.04d Travelling salesman lower bound: using minimum spanning tree

7 Rupta, a sales representative, has to visit six shops, \(A , B , C , D , E\) and \(F\). Rupta starts at shop \(A\) and travels to each of the other shops once, before returning to shop \(A\). Rupta wishes to keep her travelling time to a minimum. The table shows the travelling times, in minutes, between the shops.

Show mark scheme Show mark scheme source

Question 7:

(a)

Answer	Marks	Guidance
Answer	Marks	Guidance
\(A\)–\(C\): 10, \(C\)–\(F\): 31, \(F\)–\(D\): 32, \(D\)–\(E\): 11, \(E\)–\(B\): 18, \(B\)–\(A\): 16; Total = 118 minutes	B1

(b)

Answer	Marks	Guidance
Answer	Marks	Guidance
From \(A\): nearest is \(C\) (10)	M1	Correct application of nearest neighbour
\(C \to D\) (14), \(D \to E\) (11), \(E \to B\) (18), \(B \to F\) (50), \(F \to A\) (40)	A1 A1
Total = 143 minutes	A1	cao

(c)

Answer	Marks	Guidance
Answer	Marks	Guidance
Delete \(A\) and find minimum spanning tree of remaining vertices \(B,C,D,E,F\)	M1
MST edges: \(D\)–\(E\) (11), \(C\)–\(D\) (14), \(B\)–\(E\) (18), \(C\)–\(F\) (31); MST = 74	A1
Add two smallest edges from \(A\): \(AC=10\), \(AB=16\)	M1
Lower bound = \(74 + 10 + 16 = 100\) minutes	A1	cao

(d)

Answer	Marks	Guidance
Answer	Marks	Guidance
Sketch showing MST plus two edges from \(A\)	B1
The lower bound (100) shows the optimal tour cannot be less than 100 minutes	B1	Comment on significance

## Question 7:

**(a)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A$–$C$: 10, $C$–$F$: 31, $F$–$D$: 32, $D$–$E$: 11, $E$–$B$: 18, $B$–$A$: 16; Total = 118 minutes | B1 | |

**(b)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| From $A$: nearest is $C$ (10) | M1 | Correct application of nearest neighbour |
| $C \to D$ (14), $D \to E$ (11), $E \to B$ (18), $B \to F$ (50), $F \to A$ (40) | A1 A1 | |
| Total = 143 minutes | A1 | cao |

**(c)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Delete $A$ and find minimum spanning tree of remaining vertices $B,C,D,E,F$ | M1 | |
| MST edges: $D$–$E$ (11), $C$–$D$ (14), $B$–$E$ (18), $C$–$F$ (31); MST = 74 | A1 | |
| Add two smallest edges from $A$: $AC=10$, $AB=16$ | M1 | |
| Lower bound = $74 + 10 + 16 = 100$ minutes | A1 | cao |

**(d)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Sketch showing MST plus two edges from $A$ | B1 | |
| The lower bound (100) shows the optimal tour cannot be less than 100 minutes | B1 | Comment on significance |

---

Show LaTeX source

7 Rupta, a sales representative, has to visit six shops, $A , B , C , D , E$ and $F$. Rupta starts at shop $A$ and travels to each of the other shops once, before returning to shop $A$. Rupta wishes to keep her travelling time to a minimum.

The table shows the travelling times, in minutes, between the shops.

\hfill \mbox{\textit{AQA D1 2012 Q7 [11]}}

This paper (9 questions)

View full paper

Q1 5 Q2 5 Q3 9 Q4 8 Q5 8 Q6 7 Q7 11 Q8 8 Q9 14