| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Easy -1.2 This is a straightforward application of Prim's algorithm, a standard D1 procedure requiring only mechanical execution of the algorithm steps and basic arithmetic. The multi-part structure adds length but not conceptual difficulty—parts (i) and (iii) involve simple graph drawing, while part (iv) is a non-mathematical observation. This is easier than average A-level maths as it requires no algebraic manipulation, proof, or problem-solving insight. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks |
|---|---|
| (i) A–B: 17; B–C: 25; C–D: 20; D–E: 16; E–A: 15 or 20 | M1 connectivity, A1 lengths, A1 |
| (ii) Connected tree (order: AE; AD; DB; DC or AD; AE; DB; DC or AD; DB; AE; DC). Length: 65 km | M1 connected tree, A2 (–1 each error) |
| Alternatively: Order: AD; DB; DE; DC. Length: 66 km | A1, B1 |
| (iii) Connected tree with vertex X (order: AX; XB; XD; XE; XC or similar). Length: 53 km. Advice: Close BC, AE and BD | M1 connected tree, A2 (–1 each error), B1, B3 |
| (iv) Facility (e.g. anglers); distances (e.g. B to C) | B1 |
**(i)** A–B: 17; B–C: 25; C–D: 20; D–E: 16; E–A: 15 or 20 | M1 connectivity, A1 lengths, A1 |
**(ii)** Connected tree (order: AE; AD; DB; DC or AD; AE; DB; DC or AD; DB; AE; DC). Length: 65 km | M1 connected tree, A2 (–1 each error) |
Alternatively: Order: AD; DB; DE; DC. Length: 66 km | A1, B1 |
**(iii)** Connected tree with vertex X (order: AX; XB; XD; XE; XC or similar). Length: 53 km. Advice: Close BC, AE and BD | M1 connected tree, A2 (–1 each error), B1, B3 |
**(iv)** Facility (e.g. anglers); distances (e.g. B to C) | B1 |5 The diagram represents canals connecting five cities. Canal lengths (shown on the arcs) are in km.\\
\includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_410_990_306_539}\\
(i) Draw a network in your answer book with nodes representing the five cities and arcs representing direct canal connections, i.e. canal connections which do not involve passing through another city.
The company operating the canal system wishes to close some canals to save money, whilst preserving the connectivity.\\
(ii) Starting at A, use Prim's algorithm on your answer to part (i) to find a minimum connector for the network. Give the order in which you include arcs. Draw your minimum connector and give its total length.
Consider the original network together with an extra vertex, X , at the junction of four arcs.\\
\includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_405_987_1361_539}\\
(iii) Draw the minimum connector which results from applying Prim's algorithm, starting at A , to this network. Give the length of that minimum connector. Hence advise the company on which canals to close.\\
(iv) Give a reason why the company might face objections to such closures.
\hfill \mbox{\textit{OCR MEI D1 2009 Q5 [16]}}