| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2021 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Apply Prim's Algorithm |
| Difficulty | Moderate -0.5 This is a standard algorithmic application question from Further Maths Decision module requiring mechanical execution of Prim's algorithm and nearest neighbour algorithm on given tables. While it involves multiple parts and careful bookkeeping with 8-9 vertices, these are well-practiced algorithms with no conceptual difficulty or problem-solving insight required—just methodical application of learned procedures. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| \cline { 2 - 9 } \multicolumn{1}{c|}{} | A | B | C | D | E | F | G | H |
| A | - | 24 | 42 | 48 | 34 | 37 | 32 | 22 |
| B | 24 | - | 40 | 35 | 30 | 41 | 39 | 44 |
| C | 42 | 40 | - | 21 | 26 | 45 | 38 | 36 |
| D | 48 | 35 | 21 | - | 32 | 37 | 29 | 27 |
| E | 34 | 30 | 26 | 32 | - | 34 | 40 | 28 |
| F | 37 | 41 | 45 | 37 | 34 | - | 43 | 41 |
| G | 32 | 39 | 38 | 29 | 40 | 43 | - | 38 |
| H | 22 | 44 | 36 | 27 | 28 | 41 | 38 | - |
| \cline { 2 - 9 } \multicolumn{1}{c|}{} | \(\mathbf { A }\) | \(\mathbf { B }\) | \(\mathbf { C }\) | \(\mathbf { D }\) | \(\mathbf { E }\) | \(\mathbf { F }\) | \(\mathbf { G }\) | \(\mathbf { H }\) |
| \(\mathbf { J }\) | 31 | 27 | 50 | 29 | 43 | 25 | 49 | 35 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Prim's starting at A: AH, AB, DH; CD, CE; DG, EF | M1 | First three arcs correctly chosen in order {AH, AB, DH,...} or first four nodes correctly chosen in order {A, H, B, D,...}. If any rejections seen, M1 (max) only |
| First five arcs correctly chosen in order {AH, AB, DH, CD, CE,...} or all eight nodes {A, H, B, D, C, E, G, F} | A1 | Accept \(\{1, 3, 5, 4, 6, 8, 7, 2\}\) for nodes |
| cso – all arcs correct stated and chosen in correct order | A1 | Candidates must be considering arcs for this final mark |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Weight of MST is 183 (miles) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| NNA: \(J-F-E-C-D-H-A-B-G-J\) | B1 | cao (for route – must return to J) |
| Upper bound is 267 (miles) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(183 + 27 + 25 = \ldots\) | M1 | Their answer to (b) \(+ 27 + 25\) (the two smallest arcs incident to J) |
| \(\ldots = 235\) (miles) | A1 | cao |
# Question 3:
**(a)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| Prim's starting at A: AH, AB, DH; CD, CE; DG, EF | M1 | First three arcs correctly chosen in order {AH, AB, DH,...} or first four nodes correctly chosen in order {A, H, B, D,...}. If any rejections seen, M1 (max) only |
| First five arcs correctly chosen in order {AH, AB, DH, CD, CE,...} or all eight nodes {A, H, B, D, C, E, G, F} | A1 | Accept $\{1, 3, 5, 4, 6, 8, 7, 2\}$ for nodes |
| cso – all arcs correct stated and chosen in correct order | A1 | Candidates must be considering arcs for this final mark |
**(b)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| Weight of MST is 183 (miles) | B1 | cao |
**(c)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| NNA: $J-F-E-C-D-H-A-B-G-J$ | B1 | cao (for route – must return to J) |
| Upper bound is 267 (miles) | B1 | cao |
**(d)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| $183 + 27 + 25 = \ldots$ | M1 | Their answer to (b) $+ 27 + 25$ (the two smallest arcs incident to J) |
| $\ldots = 235$ (miles) | A1 | cao |
---3.
\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
A & - & 24 & 42 & 48 & 34 & 37 & 32 & 22 \\
\hline
B & 24 & - & 40 & 35 & 30 & 41 & 39 & 44 \\
\hline
C & 42 & 40 & - & 21 & 26 & 45 & 38 & 36 \\
\hline
D & 48 & 35 & 21 & - & 32 & 37 & 29 & 27 \\
\hline
E & 34 & 30 & 26 & 32 & - & 34 & 40 & 28 \\
\hline
F & 37 & 41 & 45 & 37 & 34 & - & 43 & 41 \\
\hline
G & 32 & 39 & 38 & 29 & 40 & 43 & - & 38 \\
\hline
H & 22 & 44 & 36 & 27 & 28 & 41 & 38 & - \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}
Table 1 shows the shortest distances, in miles, 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 table of distances. 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|}{} & $\mathbf { A }$ & $\mathbf { B }$ & $\mathbf { C }$ & $\mathbf { D }$ & $\mathbf { E }$ & $\mathbf { F }$ & $\mathbf { G }$ & $\mathbf { H }$ \\
\hline
$\mathbf { J }$ & 31 & 27 & 50 & 29 & 43 & 25 & 49 & 35 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{center}
\end{table}
Table 2 shows the distances, in miles, between town J and towns A , B , $\mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }$ and H .\\
Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels.
\item Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav's route. You must state your route and its length.
\item Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav's route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2021 Q3 [8]}}