| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Critical Path Analysis |
| Type | Draw activity network from table |
| Difficulty | Easy -1.2 This is a standard textbook application of Kruskal's algorithm with straightforward definitions. Part (a) requires basic recall of graph theory terminology, part (b) is a simple formula (n-1), and parts (c-e) involve mechanical application of a well-practiced algorithm with no novel problem-solving required. The table reading and arc selection are routine for D1 students. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | |
| A | - | 17 | - | 19 | 30 | - | - |
| B | 17 | - | 21 | 23 | - | - | - |
| C | - | 21 | - | 27 | 29 | 31 | 22 |
| D | 19 | 23 | 27 | - | - | 40 | - |
| E | 30 | - | 29 | - | - | 33 | 25 |
| F | - | - | 31 | 40 | 33 | - | 39 |
| G | - | - | 22 | - | 25 | 39 | - |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | (i) Every pair of vertices connected by a path | B1 |
| (b) | \(n - 1\) | B1 |
| (c) | Diagram shown with edges AB, AD, BC, CG weighted as 17, 19, 21, 22 respectively | M1 A1 |
| (d) | Kruskal's: AB, AD, BC, CG, reject BD, EG, reject CD, reject CE, reject AE, CF | M1 A1 A1 |
| (e) | \(135\) (km) | B1 |
| Answer | Marks |
|---|---|
| a1B1 | Must see 'all pairs' and 'path' but not describing complete graph |
| a2B1 | Cao |
| a3B1 | Cao (accept definition of minimum spanning tree) |
| b1B1 | Cao |
| c1M1 | Either all arcs correct (ignore weights) or all but two arcs correct (including correct weight) |
| c1A1 | Cao |
| d1M1 | Kruskal's – first three arcs correctly chosen and at least one rejection seen at some point |
| d1A1 | All six arcs selected correctly AB, AD, BC, CG, EG, CF |
| d2A1 | Cao – all selections and rejections correct (in correct order and at the correct time) |
| e1B1 | Cao (ignore lack of units) |
(a) | (i) Every pair of vertices connected by a path | B1 | (ii) Connected graph with no cycles | B1 | (iii) All nodes connected | B1 | (3) |
(b) | $n - 1$ | B1 | (1) |
(c) | Diagram shown with edges AB, AD, BC, CG weighted as 17, 19, 21, 22 respectively | M1 A1 | (2) |
(d) | Kruskal's: AB, AD, BC, CG, reject BD, EG, reject CD, reject CE, reject AE, CF | M1 A1 A1 | (3) |
(e) | $135$ (km) | B1 | (1) |
**Notes:**
| a1B1 | Must see 'all pairs' and 'path' but not describing complete graph |
| a2B1 | Cao |
| a3B1 | Cao (accept definition of minimum spanning tree) |
| b1B1 | Cao |
| c1M1 | Either all arcs correct (ignore weights) or all but two arcs correct (including correct weight) |
| c1A1 | Cao |
| d1M1 | Kruskal's – first three arcs correctly chosen and at least one rejection seen at some point |
| d1A1 | All six arcs selected correctly AB, AD, BC, CG, EG, CF |
| d2A1 | Cao – all selections and rejections correct (in correct order and at the correct time) |
| e1B1 | Cao (ignore lack of units) |
**Total: 10 marks**
---2. Kruskal's algorithm finds a minimum spanning tree for a connected graph with $n$ vertices.
\begin{enumerate}[label=(\alph*)]
\item Explain the terms
\begin{enumerate}[label=(\roman*)]
\item connected graph,
\item tree,
\item spanning tree.
\end{enumerate}\item Write down, in terms of $n$, the number of arcs in the minimum spanning tree.
The table below shows the lengths, in km, of a network of roads between seven villages, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ and G .
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G \\
\hline
A & - & 17 & - & 19 & 30 & - & - \\
\hline
B & 17 & - & 21 & 23 & - & - & - \\
\hline
C & - & 21 & - & 27 & 29 & 31 & 22 \\
\hline
D & 19 & 23 & 27 & - & - & 40 & - \\
\hline
E & 30 & - & 29 & - & - & 33 & 25 \\
\hline
F & - & - & 31 & 40 & 33 & - & 39 \\
\hline
G & - & - & 22 & - & 25 & 39 & - \\
\hline
\end{tabular}
\end{center}
\item Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights.
\item Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
\item State the weight of the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q2 [10]}}