Question 1 - A-Level Maths

Edexcel D2 — Question 1 8 marks

Exam Board	Edexcel
Module	D2 (Decision Mathematics 2)
Marks	8
Paper	Download PDF ↗
Topic	Travelling Salesman
Type	Complete Table by Inspection
Difficulty	Moderate -0.8 This is a routine D2 question testing standard nearest-neighbour algorithm application. Part (a) requires simple inspection of a small network, parts (b) and (d) are mechanical algorithm execution, and part (c) is straightforward interpretation. No novel problem-solving or complex reasoning required—just following a prescribed procedure on a small network.
Spec	7.04c Travelling salesman upper bound: nearest neighbour method 7.04d Travelling salesman lower bound: using minimum spanning tree

\includegraphics{figure_1} Figure 1 shows a network of roads connecting six villages \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\). The lengths of the roads are given in km.

Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. [2] The table can now be taken to represent a complete network.
Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once. [3]
Interpret your answer in part (b) in terms of the original network of roads connecting the six villages. [1]
By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length. [2]

Show LaTeX source

\includegraphics{figure_1}

Figure 1 shows a network of roads connecting six villages $A$, $B$, $C$, $D$, $E$ and $F$. The lengths of the roads are given in km.

\begin{enumerate}[label=(\alph*)]
\item Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. [2]

The table can now be taken to represent a complete network.

\item Use the nearest-neighbour algorithm, starting at $A$, on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at $A$ and visits every village exactly once. [3]

\item Interpret your answer in part (b) in terms of the original network of roads connecting the six villages. [1]

\item By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length. [2]
\end{enumerate}

\hfill \mbox{\textit{Edexcel D2  Q1 [8]}}

This paper (12 questions)

View full paper

Q1 8 Q2 8 Q3 10 Q4 8 Q5 11 Q6 14 Q7 14 Q8 14 Q9 17 Q10 6 Q11 11 Q12 11