| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Session | Specimen |
| Marks | 11 |
| 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 routine application of Prim's algorithm from a matrix, a standard Further Maths Decision topic. Parts (i)-(ii) involve mechanical execution of the algorithm and simple tree analysis. Parts (iii)-(iv) require counting comparisons using the formula n(n-1)/2 and applying quadratic scaling, both straightforward once the pattern is recognized. While this is Further Maths content, it's procedural with no novel problem-solving required. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | |
| \cline { 2 - 6 } A | - | 9 | 5 | 4 | 2 |
| \cline { 2 - 6 } B | 9 | - | 7 | 5 | 7 |
| \cline { 2 - 6 } C | 5 | 7 | - | 6 | 8 |
| \cline { 2 - 6 } D | 4 | 5 | 6 | - | 5 |
| \cline { 2 - 6 } E | 2 | 7 | 8 | 5 | - |
| \cline { 2 - 6 } | |||||
| \cline { 2 - 6 } |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (i) | e.g. |
Total weight (cid:32)16
| Answer | Marks |
|---|---|
| D | M1 |
| Answer | Marks |
|---|---|
| [4] | 1.1a |
| Answer | Marks |
|---|---|
| 1.1 | n |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (ii) | (a) |
| [1] | 3.1a | |
| (ii) | (b) | 0(cid:14)(cid:11)4(cid:14)5(cid:12)(cid:14)5(cid:14)4(cid:14)2 |
| (cid:159)20 | B1 | |
| [1] | 1.1 | |
| A | B | C |
| A | - | 9 |
| B | 9 | - |
| C | 5 | 7 |
| D | 4 | 5 |
| E | 2 | 7 |
| 7 | (iii) | (cid:11)1(cid:117)4(cid:16)1(cid:12)(cid:14)(cid:11)2(cid:117)3(cid:16)1(cid:12)(cid:14)(cid:11)3(cid:117)2(cid:16)1(cid:12)(cid:14)(cid:11)4(cid:117)1(cid:16)1(cid:12) |
| (cid:32)3(cid:14)5(cid:14)5(cid:14)3 (cid:32)16 | M1 |
| Answer | Marks |
|---|---|
| [3] | 2.1 |
| Answer | Marks |
|---|---|
| 1.1 | 1(cid:117)4, 2(cid:117)3, etc. |
| Answer | Marks |
|---|---|
| www | Or by referring to their working |
| Answer | Marks | Guidance |
|---|---|---|
| 7 | (iv) | Cubic order |
| Answer | Marks |
|---|---|
| (cid:169)100(cid:185) | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 2.2b | Stating onr using the fact that Prim’s |
| Answer | Marks |
|---|---|
| an approximation | 8 minutes 20 seconds |
| Answer | Marks |
|---|---|
| 7(i) | A B C D E |
| Answer | Marks |
|---|---|
| 7(ii)(a) | e |
| Answer | Marks | Guidance |
|---|---|---|
| - | 9 | 5 |
| Answer | Marks |
|---|---|
| 7(iv) | e |
Question 7:
7 | (i) | e.g.
A B C D E
A - 9 5 4 2
B 9 - 7 5 7
C 5 7 - 6 8
D 4 5 6 - 5
E 2 7 8 5 -
Using Prim’s algorithm starting at A
AE(cid:32)2
AD(cid:32)4
AC(cid:32)5 (or DB)
DB(cid:32)5 (or AC)
Total weight (cid:32)16
A B
p
E C S
D | M1
A1
eA1
B1
[4] | 1.1a
1.1
i
c
1.1
1.1 | n
e
m
Stating which is the starting vertex
A valid order of building the tree for
their starting vertex, clearly shown
(arcs or vertices with arcs indicated on
matrix)
Correct (labelled) tree
Weights need not be shown
7 | (ii) | (a) | Vertex A | B1
[1] | 3.1a
(ii) | (b) | 0(cid:14)(cid:11)4(cid:14)5(cid:12)(cid:14)5(cid:14)4(cid:14)2
(cid:159)20 | B1
[1] | 1.1
A | B | C | D | E
A | - | 9 | 5 | 4 | 2
B | 9 | - | 7 | 5 | 7
C | 5 | 7 | - | 6 | 8
D | 4 | 5 | 6 | - | 5
E | 2 | 7 | 8 | 5 | -
7 | (iii) | (cid:11)1(cid:117)4(cid:16)1(cid:12)(cid:14)(cid:11)2(cid:117)3(cid:16)1(cid:12)(cid:14)(cid:11)3(cid:117)2(cid:16)1(cid:12)(cid:14)(cid:11)4(cid:117)1(cid:16)1(cid:12)
(cid:32)3(cid:14)5(cid:14)5(cid:14)3 (cid:32)16 | M1
M1
A1
[3] | 2.1
1.1
1.1 | 1(cid:117)4, 2(cid:117)3, etc.
Subtracting 1 for each pass
www | Or by referring to their working
in part (i)
7 | (iv) | Cubic order
3
(cid:167)500(cid:183)
Approximately (cid:117)4(cid:32)500seconds oe
(cid:168) (cid:184)
(cid:169)100(cid:185) | M1
A1
[2] | 1.1
2.2b | Stating onr using the fact that Prim’s
has cubic order
Meust include an indication that this is
an approximation | 8 minutes 20 seconds
--- 7(i) ---
7(i) | A B C D E
A - 9 5 4 2
B 9 - 7 5 7
C 5 7 - 6 8
D 4 5 6 - 5
E 2 7 8 5 -
n
e
m
i
c
7(ii)(a) | e
p
S
7(ii)(b)
- | 9 | 5 | 4 | 2
--- 7(iii) ---
7(iii)
n
e
m
i
c
--- 7(iv) ---
7(iv) | e
p
S7 A complete graph on five vertices is weighted to form a network, as given in the weighted matrix below.
\begin{center}
\begin{tabular}{ l | c | c | c | c | c | }
& \multicolumn{1}{c}{A} & \multicolumn{1}{c}{B} & \multicolumn{1}{c}{C} & D & E \\
\cline { 2 - 6 }
A & - & 9 & 5 & 4 & 2 \\
\cline { 2 - 6 }
B & 9 & - & 7 & 5 & 7 \\
\cline { 2 - 6 }
C & 5 & 7 & - & 6 & 8 \\
\cline { 2 - 6 }
D & 4 & 5 & 6 & - & 5 \\
\cline { 2 - 6 }
E & 2 & 7 & 8 & 5 & - \\
\cline { 2 - 6 }
& & & & & \\
\cline { 2 - 6 }
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Apply Prim's algorithm to the copy of this weighted matrix in the Printed Answer Booklet to construct a minimum spanning tree for the five vertices.\\
Draw your minimum spanning tree, stating the order in which you built the tree and giving its total weight.
\item (a) Using only the arcs in the minimum spanning tree, which vertex should be chosen to find the smallest total of the weights of the paths from that vertex to each of the other vertices?\\
(b) State the minimum total for this vertex.
\item Show that the total number of comparisons needed to find a minimum spanning tree for a $5 \times 5$ matrix is 16 .
\item If a computer takes 4 seconds to find a minimum spanning tree for a network with 100 vertices, how long would it take to find a minimum spanning tree for a network with 500 vertices?
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS Q7 [11]}}