Question 1 - A-Level Maths

Edexcel D2 2007 June — Question 1 11 marks

Exam Board	Edexcel
Module	D2 (Decision Mathematics 2)
Year	2007
Session	June
Marks	11
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Travelling Salesman
Type	Complete Table by Inspection
Difficulty	Moderate -0.8 This is a routine D2 question requiring straightforward application of Floyd's algorithm (or inspection of a network diagram) to complete a distance table, followed by standard nearest neighbour and lower bound algorithms. The techniques are algorithmic and well-practiced, requiring minimal problem-solving insight—easier than average A-level maths questions.
Spec	7.04c Travelling salesman upper bound: nearest neighbour method

The network above shows the distances, in miles, between seven gift shops, \(A , B\), \(C , D , E , F\) and \(G\).

The area manager needs to visit each shop. She will start and finish at shop A and wishes to minimise the total distance travelled.

By inspection, complete the two copies of the table of least distances below. \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-1_666_1136_141_863}
A \(B\) C \(D\) \(E\) \(F\) \(G\)
A - 15 36 53 23
B - 17 38 49 80 49
C 15 17 - 21 62 32
D 36 38 21 - 11 42
E 49 11 - 31 61
\(F\) 53 80 62 42 31 - 30
\(G\) 23 49 32 61 30 -
(4)
\(A\) \(B\) \(C\) \(D\) \(E\) \(F\) \(G\)
\(A\) - 15 36 53 23
\(B\) - 17 38 49 80 49
\(C\) 15 17 - 21 62 32
\(D\) 36 38 21 - 11 42
\(E\) 49 11 - 31 61
\(F\) 53 80 62 42 31 - 30
\(G\) 23 49 32 61 30 -
Starting at A, and making your method clear, find an upper bound for the route length, using the nearest neighbour algorithm.
(3)
By deleting A, and all of its arcs, find a lower bound for the route length.
(4) (Total 11 marks)

Show LaTeX source

\begin{enumerate}
  \item The network above shows the distances, in miles, between seven gift shops, $A , B$, $C , D , E , F$ and $G$.
\end{enumerate}

The area manager needs to visit each shop. She will start and finish at shop A and wishes to minimise the total distance travelled.\\
(a) By inspection, complete the two copies of the table of least distances below.\\
\includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-1_666_1136_141_863}

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
 & A & $B$ & C & $D$ & $E$ & $F$ & $G$ \\
\hline
A & - &  & 15 & 36 &  & 53 & 23 \\
\hline
B &  & - & 17 & 38 & 49 & 80 & 49 \\
\hline
C & 15 & 17 & - & 21 &  & 62 & 32 \\
\hline
D & 36 & 38 & 21 & - & 11 & 42 &  \\
\hline
E &  & 49 &  & 11 & - & 31 & 61 \\
\hline
$F$ & 53 & 80 & 62 & 42 & 31 & - & 30 \\
\hline
$G$ & 23 & 49 & 32 &  & 61 & 30 & - \\
\hline
\end{tabular}
\end{center}

(4)

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | }
\hline
 & $A$ & $B$ & $C$ & $D$ & $E$ & $F$ & $G$ \\
\hline
$A$ & - &  & 15 & 36 &  & 53 & 23 \\
\hline
$B$ &  & - & 17 & 38 & 49 & 80 & 49 \\
\hline
$C$ & 15 & 17 & - & 21 &  & 62 & 32 \\
\hline
$D$ & 36 & 38 & 21 & - & 11 & 42 &  \\
\hline
$E$ &  & 49 &  & 11 & - & 31 & 61 \\
\hline
$F$ & 53 & 80 & 62 & 42 & 31 & - & 30 \\
\hline
$G$ & 23 & 49 & 32 &  & 61 & 30 & - \\
\hline
\end{tabular}
\end{center}

(b) Starting at A, and making your method clear, find an upper bound for the route length, using the nearest neighbour algorithm.\\
(3)\\
(c) By deleting A, and all of its arcs, find a lower bound for the route length.\\
(4) (Total 11 marks)\\

\hfill \mbox{\textit{Edexcel D2 2007 Q1 [11]}}

This paper (9 questions)

View full paper

Q1 11 Q2 13 Q3 13 Q4 16 Q5 14 Q6 8 Q7 14 Q8 18 Q9 10

	A	\(B\)	C	\(D\)	\(E\)	\(F\)	\(G\)
A	-		15	36		53	23
B		-	17	38	49	80	49
C	15	17	-	21		62	32
D	36	38	21	-	11	42
E		49		11	-	31	61
\(F\)	53	80	62	42	31	-	30
\(G\)	23	49	32		61	30	-

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
\(A\)	-		15	36		53	23
\(B\)		-	17	38	49	80	49
\(C\)	15	17	-	21		62	32
\(D\)	36	38	21	-	11	42
\(E\)		49		11	-	31	61
\(F\)	53	80	62	42	31	-	30
\(G\)	23	49	32		61	30	-