| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Compare Prim's and Kruskal's algorithms |
| Difficulty | Moderate -0.8 This is a straightforward Decision 1 question testing standard algorithm recall and application. Part (a) requires memorized differences between two algorithms (3 marks for listing facts), part (b) is routine application of Prim's algorithm, and parts (c)-(d) are standard route inspection problems following textbook methods. No novel problem-solving or insight required—purely procedural execution of learned algorithms. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Any three correct differences from: Kruskal starts with shortest arc, Prim starts with any node; Kruskal requires cycle checking, Prim does not; Prim's growing tree is always connected; Kruskal considers arcs in ascending order of weight; Prim can use matrix form; Prim adds nodes, Kruskal adds arcs | B1, B1, B1 | All technical language must be correct (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| DE, EB, BL, LF, BH; HG, GA, ES; SP, MP, AR | M1 | First five arcs correctly chosen in order (no weights), or first six nodes correctly chosen in order \(\{D,E,B,L,F,H\}\). If any rejections seen at any point then M1 max only |
| — | A1 | First eight arcs correctly chosen in order or all nodes correctly chosen in order \(\{D,E,B,L,F,H,G,A,S,P,M,R\}\) |
| — | A1 | CSO — all arcs correctly stated (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(ES + LG = 24 + 15 = 39\) smallest | M1 | Three pairings of the correct four odd nodes |
| \(EL + S(FL)G = 17 + 55 = 72\) | A1 | Two rows correct including pairing and total |
| \(E(L)G + L(F)S = 32 + 40 = 72\) | A1 | Three rows correct including pairing and total |
| Repeat ES and LG | A1 | (4) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Caretaker should repeat EL (17) as it is the minimum pair not including G (ES: 24, EL: 17, LS: 40) | M1 | Identified need to repeat one path of ES, EL, LS not including G |
| EL is the least of those paths not including G | A1 | Identifies EL as least; must explicitly state EL is least of paths not including G |
| Finish at S; length of route \(= 341 + 17 = 358\) (metres) | A1 | CAO — finish at S and length 358 (3) |
# Question 4:
## Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Any three correct differences from: Kruskal starts with shortest arc, Prim starts with any node; Kruskal requires cycle checking, Prim does not; Prim's growing tree is always connected; Kruskal considers arcs in ascending order of weight; Prim can use matrix form; Prim adds nodes, Kruskal adds arcs | B1, B1, B1 | All technical language must be correct **(3)** |
## Part (b)
| Answer/Working | Mark | Guidance |
|---|---|---|
| DE, EB, BL, LF, BH; HG, GA, ES; SP, MP, AR | M1 | First five arcs correctly chosen in order (no weights), or first six nodes correctly chosen in order $\{D,E,B,L,F,H\}$. If any rejections seen at any point then M1 max only |
| — | A1 | First eight arcs correctly chosen in order or all nodes correctly chosen in order $\{D,E,B,L,F,H,G,A,S,P,M,R\}$ |
| — | A1 | CSO — all arcs correctly stated **(3)** |
## Part (c)
| Answer/Working | Mark | Guidance |
|---|---|---|
| $ES + LG = 24 + 15 = 39$ smallest | M1 | Three pairings of the correct four odd nodes |
| $EL + S(FL)G = 17 + 55 = 72$ | A1 | Two rows correct including pairing **and** total |
| $E(L)G + L(F)S = 32 + 40 = 72$ | A1 | Three rows correct including pairing **and** total |
| Repeat ES and LG | A1 | **(4)** |
## Part (d)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Caretaker should repeat EL (17) as it is the minimum pair not including G (ES: 24, EL: 17, LS: 40) | M1 | Identified need to repeat one path of ES, EL, LS not including G |
| EL is the least of those paths not including G | A1 | Identifies EL as least; must explicitly state EL is least of paths not including G |
| Finish at S; length of route $= 341 + 17 = 358$ (metres) | A1 | CAO — finish at S **and** length 358 **(3)** |
---4. (a) State three differences between Prim's algorithm and Kruskal's algorithm for finding a minimum spanning tree.\\
(3)
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-5_864_1073_386_497}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
[The total weight of the network is 341]\\
(b) Use Prim's algorithm, starting at D , to find a minimum spanning tree for the network shown in Figure 4. You must list the arcs in the order in which you select them.\\
(3)
Figure 4 models a network of school corridors. The number on each arc represents the length, in metres, of that corridor. The school caretaker needs to inspect each corridor in the school to check that the fire alarms are working correctly. He wants to find a route of minimum length that traverses each corridor at least once and starts and finishes at his office, D.\\
(c) Use the route inspection algorithm to find the corridors that will need to be traversed twice. You must make your method and working clear.
The caretaker now decides to start his inspection at G. His route must still traverse each corridor at least once but he does not need to finish at G.\\
(d) Determine the finishing point so that the length of his route is minimised. You must give reasons for your answer and state the length of his route.\\
(3)\\
\hfill \mbox{\textit{Edexcel D1 2014 Q4 [13]}}