| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Easy -1.3 This is a standard D1 question testing algorithmic application of Prim's algorithm and route inspection with clear procedures. Part (a) requires mechanical application of Prim's algorithm from a table, part (b) is straightforward graph drawing, and part (c) follows the standard route inspection algorithm (identify odd vertices, find pairings, add to network weight). All parts are routine textbook exercises requiring no problem-solving insight, though the multi-part nature and 15 marks total provide some substance. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04e Route inspection: Chinese postman, pairing odd nodes |
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | \(G\) | |
| \(A\) | \(-\) | 48 | 117 | 92 | \(-\) | \(-\) | \(-\) |
| \(B\) | 48 | \(-\) | \(-\) | \(-\) | \(-\) | 63 | 55 |
| \(C\) | 117 | \(-\) | \(-\) | 28 | \(-\) | \(-\) | 85 |
| \(D\) | 92 | \(-\) | 28 | \(-\) | 58 | 132 | \(-\) |
| \(E\) | \(-\) | \(-\) | \(-\) | 58 | \(-\) | 124 | \(-\) |
| \(F\) | \(-\) | 63 | \(-\) | 132 | 124 | \(-\) | \(-\) |
| \(G\) | \(-\) | 55 | 85 | \(-\) | \(-\) | \(-\) | \(-\) |
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
& $A$ & $B$ & $C$ & $D$ & $E$ & $F$ & $G$ \\
\hline
$A$ & $-$ & 48 & 117 & 92 & $-$ & $-$ & $-$ \\
\hline
$B$ & 48 & $-$ & $-$ & $-$ & $-$ & 63 & 55 \\
\hline
$C$ & 117 & $-$ & $-$ & 28 & $-$ & $-$ & 85 \\
\hline
$D$ & 92 & $-$ & 28 & $-$ & 58 & 132 & $-$ \\
\hline
$E$ & $-$ & $-$ & $-$ & 58 & $-$ & 124 & $-$ \\
\hline
$F$ & $-$ & 63 & $-$ & 132 & 124 & $-$ & $-$ \\
\hline
$G$ & $-$ & 55 & 85 & $-$ & $-$ & $-$ & $-$ \\
\hline
\end{tabular}
The table shows the lengths, in metres, of the paths between seven vertices $A$, $B$, $C$, $D$, $E$, $F$ and $G$ in a network N.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at $A$, to solve the minimum connector problem for this table of distances. You must clearly state the order in which you selected the edges of your tree, and the weight of your final tree. Draw your tree using the vertices given in Diagram 1 in the answer book. [5]
\item Draw N using the vertices given in Diagram 2 in the answer book. [3]
\item Solve the Route Inspection problem for N. You must make your method of working clear. State a shortest route and find its length. (The weight of N is 802.) [7]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2006 Q2 [15]}}