Question 2 - A-Level Maths

Edexcel FD1 2024 June — Question 2 13 marks

Exam Board	Edexcel
Module	FD1 (Further Decision 1)
Year	2024
Session	June
Marks	13
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Travelling Salesman
Type	Apply Prim's Algorithm
Difficulty	Moderate -0.5 This is a standard algorithmic question from Further Maths Decision module requiring systematic application of Prim's algorithm and nearest neighbour algorithm to a 9-vertex network. While it involves multiple parts and careful bookkeeping, these are well-practiced procedures with no conceptual difficulty or novel problem-solving required—students follow learned algorithms step-by-step. It's slightly easier than average A-level because it's purely procedural with no proof, interpretation, or mathematical insight needed.
Spec	7.04b Minimum spanning tree: Prim's and Kruskal's algorithms 7.04c Travelling salesman upper bound: nearest neighbour method

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

	A	B	C	D	E	F	G	H	J
A	-	50	59	26	50	40	87	63	59
B	50	-	28	61	79	63	45	64	48
C	59	28	-	33	57	35	70	36	45
D	26	61	33	-	24	64	71	37	33
E	50	79	57	24	-	40	64	30	31
F	40	63	35	64	40	-	47	70	71
G	87	45	70	71	64	47	-	34	67
H	63	64	36	37	30	70	34	-	33
J	59	48	45	33	31	71	67	33	-

Use Prim's algorithm, starting at D , to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
State the weight of the minimum spanning tree found in part (a).
Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.
Use your answer to part (b) to calculate an initial upper bound for the length of the historian's route.
1. Use the nearest neighbour algorithm, starting at D , to find an upper bound for the length of the historian's route.
2. Write down the route which gives this upper bound. Using the nearest neighbour algorithm, starting at F , an upper bound of length 352 miles was found.
State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer.
By deleting A and all of its arcs, find a lower bound for the length of the historian's route.
(2) By deleting J and all of its arcs, a lower bound of length 274 miles was found.
State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer.

Show mark scheme Show mark scheme source

Question 2:

Part (a)

Answer	Marks	Guidance
Prim's starting at D: DE, AD, EH; EJ, CD, BC; GH, CF	M1	First three arcs correctly chosen in order
A1	First six arcs correctly chosen in order
A1	CSO — all arcs correctly stated in correct order

(3)

Part (b)

Answer	Marks	Guidance
Weight of MST is 241 (miles)	B1	CAO; no units required

(1)

Part (c)

Answer	Marks	Guidance
Correct MST diagram	B1	If multiple attempts, check all and award if any one correct

(1)

Part (d)

Answer	Marks	Guidance
482 (miles)	B1ft	Follow through double their answer to (b)

(1)

Part (e)

Answer	Marks	Guidance
NNA starting at D: \(D - E - H - J - C - B - G - F - A - D\)	M1	Must have at least \(D-E-H-J-C-B-\ldots\)
CAO route (must return to D)	A1
\(24+30+33+45+28+45+47+40+26 = 318\) (miles)	A1	CAO length

(3)

Part (f)

Answer	Marks	Guidance
Best upper bound is 318 from (e) as 318 is less than both 352 and 482	dB1ft	Follow through from (e); must include reason; must score at least M1 in (e)

(1)

Part (g)

Answer	Marks	Guidance
\((241 - 26) + 26 + 40 = 281\) (miles)	M1	Weight of MST \(-26 + 26(\text{AD}) + 40(\text{AF})\)
281	A1

(2)

Part (h)

Answer	Marks	Guidance
Best lower bound is 281 from (g) as 281 is greater than 274	dB1ft	Must be smaller than answer to (f); must score at least M1 in (g)

(1)

# Question 2:

## Part (a)
| Prim's starting at D: DE, AD, EH; EJ, CD, BC; GH, CF | M1 | First three arcs correctly chosen in order |
| | A1 | First six arcs correctly chosen in order |
| | A1 | CSO — all arcs correctly stated in correct order |
**(3)**

## Part (b)
| Weight of MST is 241 (miles) | B1 | CAO; no units required |
**(1)**

## Part (c)
| Correct MST diagram | B1 | If multiple attempts, check all and award if any one correct |
**(1)**

## Part (d)
| 482 (miles) | B1ft | Follow through double their answer to (b) |
**(1)**

## Part (e)
| NNA starting at D: $D - E - H - J - C - B - G - F - A - D$ | M1 | Must have at least $D-E-H-J-C-B-\ldots$ |
| CAO route (must return to D) | A1 | |
| $24+30+33+45+28+45+47+40+26 = 318$ (miles) | A1 | CAO length |
**(3)**

## Part (f)
| Best upper bound is 318 from (e) as 318 is less than both 352 and 482 | dB1ft | Follow through from (e); must include reason; must score at least M1 in (e) |
**(1)**

## Part (g)
| $(241 - 26) + 26 + 40 = 281$ (miles) | M1 | Weight of MST $-26 + 26(\text{AD}) + 40(\text{AF})$ |
| 281 | A1 | |
**(2)**

## Part (h)
| Best lower bound is 281 from (g) as 281 is greater than 274 | dB1ft | Must be smaller than answer to (f); must score at least M1 in (g) |
**(1)**

---

Show LaTeX source

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
 & A & B & C & D & E & F & G & H & J \\
\hline
A & - & 50 & 59 & 26 & 50 & 40 & 87 & 63 & 59 \\
\hline
B & 50 & - & 28 & 61 & 79 & 63 & 45 & 64 & 48 \\
\hline
C & 59 & 28 & - & 33 & 57 & 35 & 70 & 36 & 45 \\
\hline
D & 26 & 61 & 33 & - & 24 & 64 & 71 & 37 & 33 \\
\hline
E & 50 & 79 & 57 & 24 & - & 40 & 64 & 30 & 31 \\
\hline
F & 40 & 63 & 35 & 64 & 40 & - & 47 & 70 & 71 \\
\hline
G & 87 & 45 & 70 & 71 & 64 & 47 & - & 34 & 67 \\
\hline
H & 63 & 64 & 36 & 37 & 30 & 70 & 34 & - & 33 \\
\hline
J & 59 & 48 & 45 & 33 & 31 & 71 & 67 & 33 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at D , to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
\item State the weight of the minimum spanning tree found in part (a).
\item Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.

A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.
\item Use your answer to part (b) to calculate an initial upper bound for the length of the historian's route.
\item \begin{enumerate}[label=(\roman*)]
\item Use the nearest neighbour algorithm, starting at D , to find an upper bound for the length of the historian's route.
\item Write down the route which gives this upper bound.

Using the nearest neighbour algorithm, starting at F , an upper bound of length 352 miles was found.
\end{enumerate}\item State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer.
\item By deleting A and all of its arcs, find a lower bound for the length of the historian's route.\\
(2)

By deleting J and all of its arcs, a lower bound of length 274 miles was found.
\item State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer.
\end{enumerate}

\hfill \mbox{\textit{Edexcel FD1 2024 Q2 [13]}}

This paper (7 questions)

View full paper

Q1 7 Q2 13 Q3 13 Q4 8 Q5 9 Q6 11 Q7 14

	A	B	C	D	E	F	G	H	J
A	-	50	59	26	50	40	87	63	59
B	50	-	28	61	79	63	45	64	48
C	59	28	-	33	57	35	70	36	45
D	26	61	33	-	24	64	71	37	33
E	50	79	57	24	-	40	64	30	31
F	40	63	35	64	40	-	47	70	71
G	87	45	70	71	64	47	-	34	67
H	63	64	36	37	30	70	34	-	33
J	59	48	45	33	31	71	67	33	-

	A	B	C	D	E	F	G	H	J
A	-	50	59	26	50	40	87	63	59
B	50	-	28	61	79	63	45	64	48
C	59	28	-	33	57	35	70	36	45
D	26	61	33	-	24	64	71	37	33
E	50	79	57	24	-	40	64	30	31
F	40	63	35	64	40	-	47	70	71
G	87	45	70	71	64	47	-	34	67
H	63	64	36	37	30	70	34	-	33
J	59	48	45	33	31	71	67	33	-

	A	B	C	D	E	F	G	H	J
A	-	50	59	26	50	40	87	63	59
B	50	-	28	61	79	63	45	64	48
C	59	28	-	33	57	35	70	36	45
D	26	61	33	-	24	64	71	37	33
E	50	79	57	24	-	40	64	30	31
F	40	63	35	64	40	-	47	70	71
G	87	45	70	71	64	47	-	34	67
H	63	64	36	37	30	70	34	-	33
J	59	48	45	33	31	71	67	33	-