| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Moderate -0.3 This is a standard application of Prim's algorithm in tabular form with 11 vertices, which is routine for D1 students who have practiced the method. While the matrix is moderately large, the algorithm is mechanical and follows a fixed procedure. Parts (ii)-(iv) involve straightforward interpretation and reading from the MST, making this slightly easier than average overall. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| P | S | F | Ln | Br | Nr | Bm | Ld | Nc | Lv | M | |
| P | - | 150 | - | 240 | 125 | - | - | - | - | - | - |
| S | 150 | - | 150 | 80 | 105 | - | 135 | - | - | - | - |
| F | - | 150 | - | 80 | - | - | - | - | - | - | - |
| Ln | 240 | 80 | 80 | - | 120 | 115 | 120 | - | - | - | - |
| Br | 125 | 105 | - | 120 | - | 230 | 90 | - | - | - | - |
| Nr | - | - | - | 115 | 230 | - | 160 | 175 | 255 | - | - |
| Bm | - | 135 | - | 120 | 90 | 160 | - | 120 | - | - | 90 |
| Ld | - | - | - | - | - | 175 | 120 | - | 210 | 100 | 90 |
| Nc | - | - | - | - | - | 255 | - | 210 | - | 175 | - |
| Lv | - | - | - | - | - | - | - | 100 | 175 | - | 35 |
| M | - | - | - | - | - | - | 90 | 90 | - | 35 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Part | Answer/Working | Marks |
| (i) | Table with 125 in P column and 90 in Br column ringed, with both rows crossed. All circles in correct place; -1 each error (watch for one error making two changes to a row). All rows crossed out except, possibly, Nc row. | M1, A2, A1 |
| Minimum spanning tree diagram showing connections between: P–S, S–Ln, Ln–F, Br–P, Br–Bm, Bm–Nr, Nr–Ln (or similar), Ln–Ld, Ld–M, M–Lv, Lv–Nc; Length = 985 miles | B1, B1 | cao; cao |
| (ii) | Advantage: shortest length of track; Disadvantage: tree, no redundancy = fragility (breakdown et al); Disadvantage: some journeys are not shortest paths | B1, B1, B1 |
| (iii) | Route P–S–Ln–Nr; Distance: 345 miles; Dijkstra working values (no extras) at Ln and Nr, and working values only superseded at Ln and Nr (ignore Nc for this M) | M1, A1, B1, B1 |
| Complete network diagram with all edges and working values shown; Route P–S–Ln–Nr; Distance: 345 miles | B1, B1 | cao; cao |
| (iv) | Distance by min connector = 425 miles | B1 |
| **Part** | **Answer/Working** | **Marks** | **Guidance** |
|----------|-------------------|-----------|------------|
| (i) | Table with 125 in P column and 90 in Br column ringed, with both rows crossed. All circles in correct place; -1 each error (watch for one error making two changes to a row). All rows crossed out except, possibly, Nc row. | M1, A2, A1 | Tabular; Prim choosings; Crossings; Accept convincing transpose. |
| | Minimum spanning tree diagram showing connections between: P–S, S–Ln, Ln–F, Br–P, Br–Bm, Bm–Nr, Nr–Ln (or similar), Ln–Ld, Ld–M, M–Lv, Lv–Nc; Length = 985 miles | B1, B1 | cao; cao |
| (ii) | Advantage: shortest length of track; Disadvantage: tree, no redundancy = fragility (breakdown et al); Disadvantage: some journeys are not shortest paths | B1, B1, B1 | Allow cost minimisation; could say "no cycles"; disallow comments relating to direct connectivity, or relating to more stops; "longer journeys" or "takes longer" allowed; allow "min connector arcs may be more expensive" or don't allow two marks for the same point described differently, e.g. longer journeys/more time/more upkeep |
| (iii) | Route P–S–Ln–Nr; Distance: 345 miles; Dijkstra working values (no extras) at Ln and Nr, and working values only superseded at Ln and Nr (ignore Nc for this M) | M1, A1, B1, B1 | Correct working values; labels; order of labelling |
| | Complete network diagram with all edges and working values shown; Route P–S–Ln–Nr; Distance: 345 miles | B1, B1 | cao; cao |
| (iv) | Distance by min connector = 425 miles | B1 | ft their mc |
---6 The table shows the distances in miles, where direct rail connections are possible, between 11 cities in a country. The government is proposing to construct a high-speed rail network to connect the cities.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
& P & S & F & Ln & Br & Nr & Bm & Ld & Nc & Lv & M \\
\hline
P & - & 150 & - & 240 & 125 & - & - & - & - & - & - \\
\hline
S & 150 & - & 150 & 80 & 105 & - & 135 & - & - & - & - \\
\hline
F & - & 150 & - & 80 & - & - & - & - & - & - & - \\
\hline
Ln & 240 & 80 & 80 & - & 120 & 115 & 120 & - & - & - & - \\
\hline
Br & 125 & 105 & - & 120 & - & 230 & 90 & - & - & - & - \\
\hline
Nr & - & - & - & 115 & 230 & - & 160 & 175 & 255 & - & - \\
\hline
Bm & - & 135 & - & 120 & 90 & 160 & - & 120 & - & - & 90 \\
\hline
Ld & - & - & - & - & - & 175 & 120 & - & 210 & 100 & 90 \\
\hline
Nc & - & - & - & - & - & 255 & - & 210 & - & 175 & - \\
\hline
Lv & - & - & - & - & - & - & - & 100 & 175 & - & 35 \\
\hline
M & - & - & - & - & - & - & 90 & 90 & - & 35 & - \\
\hline
\end{tabular}
\end{center}
(i) Use the tabular form of Prim's algorithm, starting at vertex P , to find a minimum connector for the network. Draw your minimum connector and give its total length.\\
(ii) Give one advantage and two disadvantages of constructing a rail network using only the arcs of a minimum connector.\\
(iii) Use Dijkstra's algorithm on the diagram in the Printed Answer Book, to find the shortest route and distance from P to Nr in the original network.\\
(iv) Give the shortest distance from P to Nr using only arcs in your minimum connector.
\hfill \mbox{\textit{OCR MEI D1 2011 Q6 [16]}}