Question 2 - A-Level Maths

Edexcel D1 2024 January — Question 2 10 marks

Exam Board	Edexcel
Module	D1 (Decision Mathematics 1)
Year	2024
Session	January
Marks	10
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Minimum Spanning Trees
Type	Apply Prim's algorithm from vertex
Difficulty	Moderate -0.8 This is a standard algorithmic application question from Decision Maths requiring mechanical execution of Prim's algorithm on a distance table and nearest neighbour algorithm. While it involves multiple parts and careful bookkeeping with an 8×8 table, it requires no problem-solving insight—just following learned procedures step-by-step, making it easier than average A-level questions.
Spec	7.04b Minimum spanning tree: Prim's and Kruskal's algorithms 7.04c Travelling salesman upper bound: nearest neighbour method

2. \begin{table}[h]

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

\captionsetup{labelformat=empty} \caption{Table 1}

\end{table} Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.

Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.
State the weight of the minimum spanning tree. \begin{table}[h]
\cline { 2 - 9 } \multicolumn{1}{c|}{} A B C D E F G H
J 33 37 41 35 \(x\) 40 28 42
\captionsetup{labelformat=empty} \caption{Table 2}
\end{table} Table 2 shows the travel times, in minutes, between town J and towns A, B, C, D, E, F, G and H .
The journey time between towns E and J is \(x\) minutes where \(x > 28\) A salesperson needs to visit all of the nine towns, starting and finishing at J. The salesperson wishes to minimise the total time spent travelling.
Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson's route. Write down the route that gives this upper bound. Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson's route was found.
State the best upper bound that can be obtained by using this information and your answer to (c). Give the reason for your answer. Starting by deleting J and all of its arcs, a lower bound of 264 minutes for the duration of the salesperson's route was found.
Determine the value of \(x\). You must make your method and working clear.

Show mark scheme Show mark scheme source

Question 2 (Minimum Spanning Tree):

Part (a) - Prim's Algorithm:

Answer	Marks	Guidance
Answer	Mark	Guidance
First three arcs: AE, AC, CD	a1M1	First three arcs correct in order, or first four nodes {A,E,C,D} correct in order
AE, AC, CD; BD, AF; CH, BG (all arcs in correct order)	a1A1	First five arcs correct in order
All arcs correctly stated in correct order (no additional arcs)	a2A1	CSO

Part (b) - Weight of MST:

Answer	Marks	Guidance
Answer	Mark	Guidance
Weight of MST is 205 (minutes)	b1B1	No units required

Part (c) - Nearest Neighbour:

Answer	Marks	Guidance
Answer	Mark	Guidance
\(J-G-B-D-C-A-E-F-H-J\) with first five nodes correct	c1M1	Accept arcs JG, GB, BD, DC
\(28+32+28+27+29+28+36+39+42 = 289\) (minutes)	c1A1	Correct route returning to J

Part (d) - Best Upper Bound:

Answer	Marks	Guidance
Answer	Mark	Guidance
Best upper bound is the one starting at J as 289 < 291	d1B1	Accept any wording indicating 289 is smaller than 291

Part (e) - Finding x:

Answer	Marks	Guidance
Answer	Mark	Guidance
Two smallest arcs incident to J are 28 and \(\min(x, 33)\), but \(28+33+205 \neq 264\)	e1B1	Must justify that two smallest arcs are 28 and 31
\(205 + 28 + x = 264\)	e1M1	Forming equation: weight of MST + 28 + x = 264
\(x = 31\)	e1A1	CAO

# Question 2 (Minimum Spanning Tree):

## Part (a) - Prim's Algorithm:
| Answer | Mark | Guidance |
|--------|------|----------|
| First three arcs: AE, AC, CD | a1M1 | First three arcs correct in order, or first four nodes {A,E,C,D} correct in order |
| AE, AC, CD; BD, AF; CH, BG (all arcs in correct order) | a1A1 | First five arcs correct in order |
| All arcs correctly stated in correct order (no additional arcs) | a2A1 | CSO |

## Part (b) - Weight of MST:
| Answer | Mark | Guidance |
|--------|------|----------|
| Weight of MST is 205 (minutes) | b1B1 | No units required |

## Part (c) - Nearest Neighbour:
| Answer | Mark | Guidance |
|--------|------|----------|
| $J-G-B-D-C-A-E-F-H-J$ with first five nodes correct | c1M1 | Accept arcs JG, GB, BD, DC |
| $28+32+28+27+29+28+36+39+42 = 289$ (minutes) | c1A1 | Correct route returning to J |

## Part (d) - Best Upper Bound:
| Answer | Mark | Guidance |
|--------|------|----------|
| Best upper bound is the one starting at J as 289 < 291 | d1B1 | Accept any wording indicating 289 is smaller than 291 |

## Part (e) - Finding x:
| Answer | Mark | Guidance |
|--------|------|----------|
| Two smallest arcs incident to J are 28 and $\min(x, 33)$, but $28+33+205 \neq 264$ | e1B1 | Must justify that two smallest arcs are 28 and 31 |
| $205 + 28 + x = 264$ | e1M1 | Forming equation: weight of MST + 28 + x = 264 |
| $x = 31$ | e1A1 | CAO |

---

Show LaTeX source

2.

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
 & A & B & C & D & E & F & G & H \\
\hline
A & - & 34 & 29 & 35 & 28 & 30 & 37 & 38 \\
\hline
B & 34 & - & 32 & 28 & 39 & 40 & 32 & 39 \\
\hline
C & 29 & 32 & - & 27 & 33 & 39 & 34 & 31 \\
\hline
D & 35 & 28 & 27 & - & 35 & 38 & 41 & 36 \\
\hline
E & 28 & 39 & 33 & 35 & - & 36 & 33 & 40 \\
\hline
F & 30 & 40 & 39 & 38 & 36 & - & 34 & 39 \\
\hline
G & 37 & 32 & 34 & 41 & 33 & 34 & - & 35 \\
\hline
H & 38 & 39 & 31 & 36 & 40 & 39 & 35 & - \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}

Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.
\item State the weight of the minimum spanning tree.

\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
\cline { 2 - 9 }
\multicolumn{1}{c|}{} & A & B & C & D & E & F & G & H \\
\hline
J & 33 & 37 & 41 & 35 & $x$ & 40 & 28 & 42 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{center}
\end{table}

Table 2 shows the travel times, in minutes, between town J and towns A, B, C, D, E, F, G and H .\\
The journey time between towns E and J is $x$ minutes where $x > 28$\\
A salesperson needs to visit all of the nine towns, starting and finishing at J. The salesperson wishes to minimise the total time spent travelling.
\item Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson's route. Write down the route that gives this upper bound.

Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson's route was found.
\item State the best upper bound that can be obtained by using this information and your answer to (c). Give the reason for your answer.

Starting by deleting J and all of its arcs, a lower bound of 264 minutes for the duration of the salesperson's route was found.
\item Determine the value of $x$. You must make your method and working clear.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2024 Q2 [10]}}

This paper (7 questions)

View full paper

Q1 13 Q2 10 Q3 14 Q4 7 Q5 5 Q6 9 Q7 17

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

\cline { 2 - 9 } \multicolumn{1}{c\|}{}	A	B	C	D	E	F	G	H
J	33	37	41	35	\(x\)	40	28	42

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-