| Date | November 2010 | Marks available | 12 | Reference code | 10N.3dm.hl.TZ0.3 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Draw, Find, Sketch, and Write down | Question number | 3 | Adapted from | N/A |
Question
Consider the following weighted graph.
(a) (i) Use Kruskal’s algorithm to find the minimum spanning tree. Indicate the order in which you select the edges and draw the final spanning tree.
(ii) Write down the total weight of this minimum spanning tree.
(b) Sketch a spanning tree of maximum total weight and write down its weight.
Markscheme
(a) (i) (Kruskal’s: successively take an edge of smallest weight without forming a cycle)
\({1^{{\text{st}}}}\) edge DC (weight 1) A1
\({2^{{\text{nd}}}}\) edge EG (weight 2) A1
\({3^{{\text{rd}}}}\) edge DE (weight 3) A1
\({4^{{\text{th}}}}\) edge EF (weight 6) A1
\({5^{{\text{th}}}}\) edge AD (weight 7) A1
\({6^{{\text{th}}}}\) edge AB (weight 8) A1
A1
Notes: Weights are not required on the diagram.
Allow A2(d) if the (correct) edges are in the wrong order e.g. they have used Prim’s rather than Kruskal’s algorithm.
(ii) total weight is 1 + 2 + 3 + 6 + 7 + 8 = 27 A1
[8 marks]
(b) EITHER
A3
OR
A3
Notes: Award A2 for five or four correct edges,
A1 for three or two correct edges
A0 otherwise.
Weights are not required on the diagram.
THEN
total weight is 6 + 7 + 7 + 8 + 9 + 10 = 47 A1
[4 marks]
Total [12 marks]
Examiners report
Good algorithm work was shown; sometimes there were mistakes in giving the order of the edges chosen by, for example doing Prim’s algorithm instead of Kruskal’s.
