Question 3 - A-Level Maths

Edexcel FD1 Specimen — Question 3 11 marks

Exam Board	Edexcel
Module	FD1 (Further Decision 1)
Session	Specimen
Marks	11
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Travelling Salesman
Type	Lower Bound by Vertex Deletion
Difficulty	Standard +0.3 This is a standard Further Maths D1 question testing routine application of the vertex deletion algorithm for TSP lower bounds, plus basic nearest neighbour algorithm. Part (a) is definitional recall, (b) follows a prescribed method with straightforward MST calculation, (c) requires working backwards from given information but is mechanical, and (d) is direct application of bounds. While it's a multi-part question worth several marks, each component uses standard algorithms without requiring problem-solving insight or novel approaches—slightly easier than average A-level difficulty.
Spec	7.04c Travelling salesman upper bound: nearest neighbour method 7.04d Travelling salesman lower bound: using minimum spanning tree

3. (a) Explain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.

	A	B	C	D	E	F	G
A	-	17	24	16	21	18	41
B	17	-	35	25	30	31	\(x\)
C	24	35	-	28	20	35	32
D	16	25	28	-	29	19	45
E	21	30	20	29	-	22	35
F	18	31	35	19	22	-	37
G	41	\(x\)	32	45	35	37	-

The table shows the least distances, in km, by road between seven towns, A, B, C, D, E, F and G . The least distance between B and G is \(x \mathrm {~km}\), where \(x > 25\) Preety needs to visit each town at least once, starting and finishing at A. She wishes to minimise the total distance she travels.
(b) Starting by deleting B and all of its arcs, find a lower bound for Preety's route. Preety found the nearest neighbour routes from each of A and C . Given that the sum of the lengths of these routes is 331 km ,
(c) find \(x\), making your method clear.
(d) Write down the smallest interval that you can be confident contains the optimal length of Preety's route. Give your answer as an inequality.

Show mark scheme Show mark scheme source

Question 3:

Part (a)

Answer	Marks	Guidance
Answer	Mark	Guidance
In the practical problem each vertex must be visited at least once; in the classical problem each vertex must be visited just once	B2,1,0	Understands the difference is connected to number of times each vertex may be visited. Must attempt a difference referring to both problems explicitly. Technical language must be correct. Need not imply each/every/all vertices for first mark
Second B1: must imply each/every/all vertices are visited; e.g. 'the practical visits a vertex at least once while the classical visits a vertex only once' (B1B0 note that B0B1 is not possible)

Part (b)

Answer	Marks	Guidance
Answer	Mark	Guidance
Prim's algorithm on reduced network starting at A: AD, AF, AE, CE, CG	M1	Correctly applying Prim's algorithm from node A for the first four arcs (or five nodes)
Lower bound \(= 107 + 17 + 25 = 149\) (km)	M1	Candidates weight of their RMST \(+ 17 + 25\) (the two smallest arcs incident to B)
A1	cao (condone lack of units)

Part (c)

Answer	Marks	Guidance
Answer	Mark	Guidance
NNA from A: \(A-D-F-E-C-G-B-A = 126+x\)	M1	Either one route, must return to A
NNA from C: \(C-E-A-D-F-B-G-C = 139+x\)	A1	One correct route with corresponding length correct (do not include if correct lengths seen but are then doubled)
A1	Both routes correct and their corresponding lengths correct
\((126+x)+(139+x) = 331 \Rightarrow x = 33\)	A1	cao for \(x\)

Part (d)

Answer	Marks	Guidance
Answer	Mark	Guidance
\(149 < \text{optimal} \leqslant 159\)	M1	Their numbers correctly used; accept any inequalities or any indication of interval from their 149 to their 159 (so \(149-159\) can score this mark). Dependent on two routes seen in (c); neither total needs to be correct. Note \(UB > LB\) for this mark
A1	cao (no follow through on their values) including correct inequalities or equivalent set notation (but condone \(149 \leqslant \text{optimal} \leqslant 159\))

# Question 3:

## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| In the practical problem each vertex must be visited at least once; in the classical problem each vertex must be visited just once | B2,1,0 | Understands the difference is connected to number of times each vertex may be visited. Must attempt a difference referring to both problems explicitly. Technical language must be correct. Need not imply each/every/all vertices for first mark |
| | | Second B1: must imply each/every/all vertices are visited; e.g. 'the practical visits a vertex at least once while the classical visits a vertex only once' (B1B0 note that B0B1 is not possible) |

## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Prim's algorithm on reduced network starting at A: AD, AF, AE, CE, CG | M1 | Correctly applying Prim's algorithm from node A for the first four arcs (or five nodes) |
| Lower bound $= 107 + 17 + 25 = 149$ (km) | M1 | Candidates weight of their RMST $+ 17 + 25$ (the two smallest arcs incident to B) |
| | A1 | cao (condone lack of units) |

## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| NNA from A: $A-D-F-E-C-G-B-A = 126+x$ | M1 | Either one route, must return to A |
| NNA from C: $C-E-A-D-F-B-G-C = 139+x$ | A1 | One correct route with corresponding length correct (do not include if correct lengths seen but are then doubled) |
| | A1 | Both routes correct and their corresponding lengths correct |
| $(126+x)+(139+x) = 331 \Rightarrow x = 33$ | A1 | cao for $x$ |

## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| $149 < \text{optimal} \leqslant 159$ | M1 | Their numbers correctly used; accept any inequalities or any indication of interval from their 149 to their 159 (so $149-159$ can score this mark). Dependent on two routes seen in (c); neither total needs to be correct. Note $UB > LB$ for this mark |
| | A1 | cao (no follow through on their values) including correct inequalities or equivalent set notation (but condone $149 \leqslant \text{optimal} \leqslant 159$) |

---

Show LaTeX source

3. (a) Explain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
 & A & B & C & D & E & F & G \\
\hline
A & - & 17 & 24 & 16 & 21 & 18 & 41 \\
\hline
B & 17 & - & 35 & 25 & 30 & 31 & $x$ \\
\hline
C & 24 & 35 & - & 28 & 20 & 35 & 32 \\
\hline
D & 16 & 25 & 28 & - & 29 & 19 & 45 \\
\hline
E & 21 & 30 & 20 & 29 & - & 22 & 35 \\
\hline
F & 18 & 31 & 35 & 19 & 22 & - & 37 \\
\hline
G & 41 & $x$ & 32 & 45 & 35 & 37 & - \\
\hline
\end{tabular}
\end{center}

The table shows the least distances, in km, by road between seven towns, A, B, C, D, E, F and G . The least distance between B and G is $x \mathrm {~km}$, where $x > 25$

Preety needs to visit each town at least once, starting and finishing at A. She wishes to minimise the total distance she travels.\\
(b) Starting by deleting B and all of its arcs, find a lower bound for Preety's route.

Preety found the nearest neighbour routes from each of A and C . Given that the sum of the lengths of these routes is 331 km ,\\
(c) find $x$, making your method clear.\\
(d) Write down the smallest interval that you can be confident contains the optimal length of Preety's route. Give your answer as an inequality.\\

\hfill \mbox{\textit{Edexcel FD1  Q3 [11]}}

This paper (7 questions)

View full paper

Q1 4 Q2 7 Q3 11 Q4 14 Q5 15 Q6 12 Q7 12