| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with vertex removed |
| Difficulty | Moderate -0.5 This is a standard D1 question testing Kruskal's algorithm application with straightforward modifications. Part (a) is routine algorithm execution, parts (b-c) require minimal adaptation (removing a vertex), and parts (d-f) test basic understanding of directed graphs and algorithm selection. The question is slightly easier than average A-level because it's mostly procedural application of a learned algorithm with no complex problem-solving or proof required. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| order: E–Gr, Gr–F, ↔ I–Ge, Gr–C, Gr–I, Gr–R, C–U; cost £263 | M2 A1 | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| I–Ge, I–F, C–U, C–E, F–R (or Gr–R), Ge–E; cost £396 | M1 A1 | |
| (ii) previous tree still minimum, cost = £263 | A1 | |
| (c) e.g. translations between other languages cheaper via Greek even though Greek translation not required | B1 | |
| (d) an asymmetric array could show both costs | B1 | |
| (e) Prim's | B1 | |
| (f) e.g. that a translation via another language will be of as good quality as one done directly – unlikely to be the case | B2 | (12) |
**(a)** arcs in ascending order by inspection:
20, 25, 25, 35, 38, 42, 50, 52, 55, 68, 75, 85, 85, 93, 100, 105, 108, 175
[Minimum spanning tree diagram with vertices: English, French, Russian, German, Italian, Greek, Chinese, Urdu]
order: E–Gr, Gr–F, ↔ I–Ge, Gr–C, Gr–I, Gr–R, C–U; cost £263 | M2 A1 | A1 |
**(b)** (i) 25, 50, 55, 68, 75, 85, 85, 93, 100, 105, 108, 175
[Second minimum spanning tree diagram showing alternative route]
I–Ge, I–F, C–U, C–E, F–R (or Gr–R), Ge–E; cost £396 | M1 A1 |
(ii) previous tree still minimum, cost = £263 | A1 |
**(c)** e.g. translations between other languages cheaper via Greek even though Greek translation not required | B1 |
**(d)** an asymmetric array could show both costs | B1 |
**(e)** Prim's | B1 |
**(f)** e.g. that a translation via another language will be of as good quality as one done directly – unlikely to be the case | B2 | (12) |
---\textit{This question should be answered on the sheet provided.}
\includegraphics{figure_2}
In Figure 2 the weight on each arc represents the cost in pounds of translating a certain document between the two languages at the nodes that it joins. You may assume that the cost is the same for translating in either direction.
\begin{enumerate}[label=(\alph*)]
\item Use Kruskal's algorithm to find the minimum cost of obtaining a translation of the document from English into each of the other languages on the network. You must show the order in which the arcs were selected. [4 marks]
\item It is decided that a Greek translation is not needed. Find the minimum cost if:
\begin{enumerate}[label=(\roman*)]
\item translations to and from Greek are not available,
\item translations to and from Greek are still available. [3 marks]
\end{enumerate}
\item Comment on your findings. [1 mark]
\end{enumerate}
Another document is to be translated into 60 languages. It is now also necessary to take into account the fact that the cost of a translation between two languages depends on which language you start from.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{3}
\item How would you overcome the problem of having different costs for reverse translations? [1 mark]
\item What algorithm would be suitable to find a computerised solution. [1 mark]
\item State another assumption you have made in answering this question and comment on its validity. [2 marks]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q5 [12]}}