| Date | May 2017 | Marks available | 7 | Reference code | 17M.2.hl.TZ0.1 |
| Level | HL only | Paper | 2 | Time zone | TZ0 |
| Command term | Find | Question number | 1 | Adapted from | N/A |
Question
The diagram shows the graph \(G\) with the weights of the edges marked.
State what features of the graph enable you to state that \(G\) contains an Eulerian trail but no Eulerian circuit.
Write down an Eulerian trail.
Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D, stating this total weight. Your solution should show clearly that this algorithm has been used.
Markscheme
there is an Eulerian trail because \(G\) contains exactly two vertices of odd order A1
there is no Eulerian circuit because \(G\) contains vertices of odd order A1
[2 marks]
the trail must start at B and end at E (or vice versa) (R1)
BAFBCFECDE R1
[2 marks]
Note: Award full marks if the correct path is given with correct total weight if an annotated graph is given that represents the Dijkstra algorithm.
[7 marks]
