| Date | May 2018 | Marks available | 2 | Reference code | 18M.2.hl.TZ0.3 |
| Level | HL only | Paper | 2 | Time zone | TZ0 |
| Command term | Determine | Question number | 3 | Adapted from | N/A |
Question
While on holiday Pauline visits the local museum. On the ground floor of the museum there are six rooms, A, B, C, D, E and F. The doorways between the rooms are indicated on the following floorplan.
There are 6 museum s in 6 towns in the area where Pauline is on holiday. The 6 towns and the roads connecting them can be represented by a graph. Each vertex represents a town, each edge represents a road and the weight of each edge is the distance between the towns using that road. The information is shown in the adjacency table.
Pauline wants to visit each town and needs to start and finish in the same town.
Draw a graph G to represent this floorplan where the rooms are represented by the vertices and an edge represents a door between two rooms.
Explain why the graph G has an Eulerian trail but not an Eulerian circuit.
Explain the consequences of having an Eulerian trail but not an Eulerian circuit, for Pauline’s visit to the ground floor of the museum.
Write down a Hamiltonian cycle for the graph G.
Explain the consequences of having a Hamiltonian cycle for Pauline’s visit to the ground floor of the museum.
Use the nearest-neighbour algorithm to determine a possible route and an upper bound for the length of her route starting in town Z.
By removing Z, use the deleted vertex algorithm to determine a lower bound for the length of her route.
Markscheme
A2
[2 Marks]
two vertices are of odd degree A1
to have an Eulerian circuit it must have all vertices of even degree R1
hence no Eulerian circuit, but an Eulerian trail AG
[2 Marks]
it allows Pauline to go through every door once (provided she starts in
room B or room E) A1
and she cannot return to the room in which she started A1
[2 Marks]
for example: A → F → E → D → C → B → A A2
Note: Award A1 if the cycle does not return to the start vertex.
[2 Marks]
she can visit every room once without repeating and return to the start A1
[1 Mark]
Z → V → Y → X → U → W → Z A1
6 + 4 + 9 + 7 + 10 + 10 = 46 A1
[2 marks]
attempt to find the minimal spanning tree (M1)
VY
VW
UX
XY A2
Note: Award A1 if one error made.
Note: Accept correct drawing of minimal spanning tree.
weight of minimal spanning tree = 4 + 5 + 7 + 9 = 25 (A1)
since Z is removed, we add on VZ and ZY (M1)
hence lower bound for route is 25 + 13 = 38 A1
[6 marks]
