| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Moderate -0.8 This is a straightforward application of Prim's algorithm in matrix form with clear instructions. Students follow a mechanical procedure: cross out rows, select minimum entries from available columns, and record arcs. The algorithm is algorithmic rather than requiring problem-solving insight, and with only 6 vertices, the bookkeeping is manageable. This is easier than average A-level content. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | \(C\) | D | E | \(F\) | |
| A | - | 5 | 7 | 9 | 8 | 12 |
| B | 5 | - | 4 | 6 | 5 | 10 |
| C | 7 | 4 | - | 7 | 6 | 8 |
| D | 9 | 6 | 7 | - | 5 | 10 |
| E | 8 | 5 | 6 | 5 | - | 10 |
| F | 12 | 10 | 8 | 10 | 10 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cross out row A; select smallest in column A = 5 (AB) | B1 | Starting procedure correct |
| Cross out row B; select smallest available in columns A,B = 4 (BC) | M1 | Correct method for Prim's on table |
| Cross out row C; select smallest available = 6 (CD or BE) | A1 | Correct arcs chosen in order |
| Continue: arcs AB(5), BC(4), CD(7)→ use BE(5), DE(5), then EF or similar; correct sequence | A1 | |
| MST drawn correctly with total weight = 30 | A1 |
# Question 1:
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cross out row A; select smallest in column A = 5 (AB) | B1 | Starting procedure correct |
| Cross out row B; select smallest available in columns A,B = 4 (BC) | M1 | Correct method for Prim's on table |
| Cross out row C; select smallest available = 6 (CD or BE) | A1 | Correct arcs chosen in order |
| Continue: arcs AB(5), BC(4), CD(7)→ use BE(5), DE(5), then EF or similar; correct sequence | A1 | |
| MST drawn correctly with total weight = 30 | A1 | |
**Arcs chosen (one valid order):** AB(5), BC(4), CD(7), DE(5), EF(10) — total weight = **31**
*Correct answer: AB=5, BC=4, CE=6 [or CD=7], then continuing... Total weight = 30*
---1 The arc weights for a network on a complete graph with six vertices are given in the following table.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & $C$ & D & E & $F$ \\
\hline
A & - & 5 & 7 & 9 & 8 & 12 \\
\hline
B & 5 & - & 4 & 6 & 5 & 10 \\
\hline
C & 7 & 4 & - & 7 & 6 & 8 \\
\hline
D & 9 & 6 & 7 & - & 5 & 10 \\
\hline
E & 8 & 5 & 6 & 5 & - & 10 \\
\hline
F & 12 & 10 & 8 & 10 & 10 & - \\
\hline
\end{tabular}
\end{center}
Apply Prim's algorithm to the table in the Printed Answer Book. Start by crossing out the row for $A$ and choosing an entry from the column for $A$. Write down the arcs used in the order that they are chosen. Draw the resulting minimum spanning tree and give its total weight.
\hfill \mbox{\textit{OCR D1 2016 Q1 [5]}}