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.

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]

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.