Question 5 - A-Level Maths

Edexcel FD1 2023 June — Question 5 13 marks

Exam Board	Edexcel
Module	FD1 (Further Decision 1)
Year	2023
Session	June
Marks	13
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Route Inspection
Type	Combined Dijkstra and route inspection
Difficulty	Challenging +1.2 This is a multi-part Further Maths Decision question combining route inspection (Chinese Postman) with Dijkstra's shortest paths and MST algorithms. While it requires understanding of multiple algorithms and careful bookkeeping across several parts, each individual component is a standard textbook application without requiring novel insight. The shortest distance table is provided rather than needing to be calculated, simplifying part (a). This is moderately above average difficulty due to the Further Maths content and multi-algorithm nature, but remains a straightforward application question.
Spec	7.04e Route inspection: Chinese postman, pairing odd nodes

5. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-08_657_1066_214_502} \captionsetup{labelformat=empty} \caption{Figure 5}

\end{figure} [The total weight of the network is 423]
Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road. The table below shows the shortest distances, in miles, between the nine towns. \begin{table}[h]

	A	B	C	D	E	F	G	H	J
A	-	34	51	31	79	20	8	55	61
B	34	-	17	65	45	54	42	21	27
C	51	17	-	82	28	71	59	22	10
D	31	65	82	-	87	22	23	86	92
E	79	45	28	87	-	65	87	30	18
F	20	54	71	22	65	-	28	75	81
G	8	42	59	23	87	28	-	63	69
H	55	21	22	86	30	75	63	-	12
J	61	27	10	92	18	81	69	12	-

\captionsetup{labelformat=empty} \caption{Table of shortest distances}

\end{table} A route is needed that minimises the total distance required to traverse each road at least once. The route must start at F and finish at J .

1. By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice.
2. State the total length of this route.
Starting at A, use Prim's algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels.
Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete's route. Write down the route that gives this upper bound.
By deleting G and all of its arcs, find a lower bound for the length of Pete's route. Pete decides to take the route he found in (c).
Interpret the route in terms of the actual towns visited.

Show mark scheme Show mark scheme source

Question 5:

Part (a)(i)

Answer	Marks	Guidance
Answer	Mark	Guidance
Route must start at F and finish at J; consider pairings of nodes F, C, D and G	M1	Correct three pairings of the correct four nodes (F, C, D and G)
\(CD + FG = 82 + 28 = 110\)	A1	Two rows correct including pairings and totals
\(CF + DG = 71 + 23 = 94\)	A1	All three rows correct including pairings and totals
\(CG + DF = 59 + 22 = 81\)
Repeated roads: CB, BA, AG, and DF	A1	CAO (CB, BA, AG, DF only, in any order) — must be stated as edges; A0 for CG or CBAG or CG via B and A

Part (a)(ii)

Answer	Marks	Guidance
Answer	Mark	Guidance
Length of route \(= 423 + 81 = 504\) miles	A1ft	\(423 +\) weight of shortest pairing

Part (b)

Answer	Marks	Guidance
Answer	Mark	Guidance
Prim's starting at A: AG, AF, DF, AB, BC, CJ, HJ, EJ	M1	First three arcs correctly chosen in order {AG, AF, DF, …} or first four nodes correctly chosen in order {A, G, F, D, …}. If any explicit rejections seen then M1 (max) only
A1	First five arcs correctly chosen in order {AG, AF, DF, AB, BC, …} or all nine nodes correctly chosen in order {A, G, F, D, B, C, J, H, E}
A1	CSO — all arcs correct stated and chosen in correct order

Part (c)

Answer	Marks	Guidance
Answer	Mark	Guidance
NNA starting at G: \(G - A - F - D - B - C - J - H - E - G\)	M1	Nearest neighbour route starting at G; must have at least \(G - A - F - D - B - C - \ldots\)
\(8 + 20 + 22 + 65 + 17 + 10 + 12 + 30 + 87 = 271\)	A1	CAO on length (271) and route (must return to G)

Part (d)

Answer	Marks	Guidance
Answer	Mark	Guidance
\((141 - 8) + 8 + 23 = 164\) miles	M1	RMST arcs: AF, DF, AB, BC, CJ, HJ, EJ (any order); or RMST weight calc \(20+22+34+17+10+12+18\); or RMST weight 133 or \(141-8\); or lower bound stated 164
A1	CAO (164)

Part (e)

Answer	Marks	Guidance
Answer	Mark	Guidance
GAFD GA BCJH J E JCBA G	B1	CAO (GAFD GA BCJH J E JCBA G or in terms of arcs)

# Question 5:

## Part (a)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Route must start at F and finish at J; consider pairings of nodes F, C, D and G | M1 | Correct three pairings of the correct four nodes (F, C, D and G) |
| $CD + FG = 82 + 28 = 110$ | A1 | Two rows correct including pairings **and** totals |
| $CF + DG = 71 + 23 = 94$ | A1 | All three rows correct including pairings **and** totals |
| $CG + DF = 59 + 22 = 81$ | | |
| Repeated roads: CB, BA, AG, and DF | A1 | CAO (CB, BA, AG, DF only, in any order) — must be stated as edges; A0 for CG or CBAG or CG via B and A |

## Part (a)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Length of route $= 423 + 81 = 504$ miles | A1ft | $423 +$ weight of shortest pairing |

## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Prim's starting at A: AG, AF, DF, AB, BC, CJ, HJ, EJ | M1 | First three arcs correctly chosen in order {AG, AF, DF, …} or first four nodes correctly chosen in order {A, G, F, D, …}. If any explicit rejections seen then M1 (max) only |
| | A1 | First five arcs correctly chosen in order {AG, AF, DF, AB, BC, …} or all nine nodes correctly chosen in order {A, G, F, D, B, C, J, H, E} |
| | A1 | CSO — all arcs correct stated and chosen in correct order |

## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| NNA starting at G: $G - A - F - D - B - C - J - H - E - G$ | M1 | Nearest neighbour route starting at G; must have at least $G - A - F - D - B - C - \ldots$ |
| $8 + 20 + 22 + 65 + 17 + 10 + 12 + 30 + 87 = 271$ | A1 | CAO on length (271) **and** route (must return to G) |

## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| $(141 - 8) + 8 + 23 = 164$ miles | M1 | RMST arcs: AF, DF, AB, BC, CJ, HJ, EJ (any order); or RMST weight calc $20+22+34+17+10+12+18$; or RMST weight 133 or $141-8$; or lower bound stated 164 |
| | A1 | CAO (164) |

## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| GAFD **GA** BCJH **J** E **JCBA** G | B1 | CAO (GAFD **GA** BCJH **J** E **JCBA** G or in terms of arcs) |

Show LaTeX source

5.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-08_657_1066_214_502}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}

[The total weight of the network is 423]\\
Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road.

The table below shows the shortest distances, in miles, between the nine towns.

\begin{table}[h]
\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 & - & 34 & 51 & 31 & 79 & 20 & 8 & 55 & 61 \\
\hline
B & 34 & - & 17 & 65 & 45 & 54 & 42 & 21 & 27 \\
\hline
C & 51 & 17 & - & 82 & 28 & 71 & 59 & 22 & 10 \\
\hline
D & 31 & 65 & 82 & - & 87 & 22 & 23 & 86 & 92 \\
\hline
E & 79 & 45 & 28 & 87 & - & 65 & 87 & 30 & 18 \\
\hline
F & 20 & 54 & 71 & 22 & 65 & - & 28 & 75 & 81 \\
\hline
G & 8 & 42 & 59 & 23 & 87 & 28 & - & 63 & 69 \\
\hline
H & 55 & 21 & 22 & 86 & 30 & 75 & 63 & - & 12 \\
\hline
J & 61 & 27 & 10 & 92 & 18 & 81 & 69 & 12 & - \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table of shortest distances}
\end{center}
\end{table}

A route is needed that minimises the total distance required to traverse each road at least once.

The route must start at F and finish at J .
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice.
\item State the total length of this route.
\end{enumerate}\item Starting at A, use Prim's algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.

Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels.
\item Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete's route. Write down the route that gives this upper bound.
\item By deleting G and all of its arcs, find a lower bound for the length of Pete's route.

Pete decides to take the route he found in (c).
\item Interpret the route in terms of the actual towns visited.
\end{enumerate}

\hfill \mbox{\textit{Edexcel FD1 2023 Q5 [13]}}

This paper (7 questions)

View full paper

Q1 7 Q2 7 Q3 8 Q4 12 Q5 13 Q6 9 Q7 19

	A	B	C	D	E	F	G	H	J
A	-	34	51	31	79	20	8	55	61
B	34	-	17	65	45	54	42	21	27
C	51	17	-	82	28	71	59	22	10
D	31	65	82	-	87	22	23	86	92
E	79	45	28	87	-	65	87	30	18
F	20	54	71	22	65	-	28	75	81
G	8	42	59	23	87	28	-	63	69
H	55	21	22	86	30	75	63	-	12
J	61	27	10	92	18	81	69	12	-

	A	B	C	D	E	F	G	H	J
A	-	34	51	31	79	20	8	55	61
B	34	-	17	65	45	54	42	21	27
C	51	17	-	82	28	71	59	22	10
D	31	65	82	-	87	22	23	86	92
E	79	45	28	87	-	65	87	30	18
F	20	54	71	22	65	-	28	75	81
G	8	42	59	23	87	28	-	63	69
H	55	21	22	86	30	75	63	-	12
J	61	27	10	92	18	81	69	12	-

	A	B	C	D	E	F	G	H	J
A	-	34	51	31	79	20	8	55	61
B	34	-	17	65	45	54	42	21	27
C	51	17	-	82	28	71	59	22	10
D	31	65	82	-	87	22	23	86	92
E	79	45	28	87	-	65	87	30	18
F	20	54	71	22	65	-	28	75	81
G	8	42	59	23	87	28	-	63	69
H	55	21	22	86	30	75	63	-	12
J	61	27	10	92	18	81	69	12	-