| Date | November 2012 | Marks available | 6 | Reference code | 12N.3dm.hl.TZ0.1 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Find and Write down | Question number | 1 | Adapted from | N/A |
Question
In the graph given above, the numbers shown represent the distance along that edge.
Using Dijkstra’s algorithm, find the length of the shortest path from vertex S to vertex T . Write down this shortest path.
(i) Does this graph have an Eulerian circuit? Justify your answer.
(ii) Does this graph have an Eulerian trail? Justify your answer.
The graph above is now to be considered with the edges representing roads in a town and with the distances being the length of that road in kilometres. Huan is a postman and he has to travel along every road in the town to deliver letters to all the houses in that road. He has to start at the sorting office at S and also finish his route at S . Find the shortest total distance of such a route. Fully explain the reasoning behind your answer.
Markscheme
from tabular method as shown above (or equivalent) M1A1A1
Note: Award the first A1 for obtaining 3 as the shortest distance to C.
Award the second A1 for obtaining the rest of the shortest distances.
shortest path has length 17 A1
backtracking as shown above (or equivalent) (M1)
shortest path is SABT A1
[6 marks]
(i) no, as S and T have odd degree A1R1
Note: Mentioning one vertex of odd degree is sufficient.
(ii) yes, as only S and T have odd degree A1R1
Note: In each case only award the A1 if the R1 has been given.
Accept an actual trail in (b)(ii).
[4 marks]
Huan has to travel along all the edges via an open Eulerian trail of length R1
4 + 3 + 5 + 2 + 1 + 3 + 5 + 4 + 7 + 8 + 5 + 6 + 7 + 6 + 6 + 8 + 9 = 94 A1
and then back to S from T along the shortest path found in (a) of length 17 R1
so shortest total distance is 94 + 17 = 111 A1
[4 marks]
Examiners report
This was quite well answered. Some candidates did not make their method clear and others showed no method at all. Some clearly had a correct method but did not make it clear what their final answers were. It is recommended that teachers look at the tabular method with its backtracking system as shown in the mark scheme as an efficient way of tackling this type of problem.
Fairly good knowledge shown here but not by all.
Some good answers but too much confusion with methods they partly remembered about the travelling salesman problem. Candidates should be aware of helpful connections between parts of a question.
