EXM.1.AHL.TZ0.39
Let G be a weighted graph with 6 vertices L, M, N, P, Q, and R. The weight of the edges joining the vertices is given in the table below:
For example the weight of the edge joining the vertices L and N is 3.
Use Prim’s algorithm to draw a minimum spanning tree starting at M.
[5]
a.
What is the total weight of the tree?
[1]
b.
Markscheme / solution
M → Q (M1)
Q → L (A1)
M → P (A1)
P → N → R (A1)
(A1)
Note: There are other correct answers.
[5 marks]
a.
The total weight is 2 + 1 + 3 + 2 + 3 = 11. (A1)
[1 mark]
b.
Examiners’ report
[N/A]
a.
[N/A]
b.