| Date | November 2008 | Marks available | 7 | Reference code | 08N.3dm.hl.TZ0.2 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Find and State | Question number | 2 | Adapted from | N/A |
Question
Use Kruskal’s algorithm to find the minimum spanning tree for the following weighted graph and state its length.
Use Dijkstra’s algorithm to find the shortest path from A to D in the following weighted graph and state its length.
Markscheme
Kruskal’s algorithm gives the following edges
CD (4) M1A1
AD (5)
EF (7) A1
EA (8)
BC (11)
FG (12) A1 N0
length of the spanning tree is 47 A1
[5 marks]
for Dijkstra’s algorithm there are three things associated with a node: order; distance from the initial node as a permanent or temporary node M1
A4
Note: Deduct A1 for each error or omission.
the shortest path is AFBCD A1
the length is 26 A1 N0
[7 marks]
Examiners report
Setting out clearly the steps of the algorithms is still a problem for many although getting the correct spanning tree and its length were not.
Setting out clearly the steps of the algorithms is still a problem for many although getting the correct spanning tree and its length were not.
