2024 Paper 2, Q2
The table shows the travel time (minutes) between five islands in the Torres Strait for a ferry service.
| Waiben | Palilug | Ngurapai | Keriri | Gealug | |
|---|---|---|---|---|---|
| Waiben | — | \(18\) | — | \(14\) | |
| Palilug | — | \(25\) | \(16\) | ||
| Ngurapai | \(20\) | \(28\) | |||
| Keriri | — | ||||
| Gealug |
Construct a weighted graph and use it to calculate the total travel time for a ferry that completes a Hamiltonian cycle beginning at Waiben.
Draw the graph and the cycle appears
Six numbers in the table give six edges. Once they are drawn, two of the islands turn out to have only two routes each, and that decides most of the cycle for you.
Two marks for the graph
Each route appears once, above the diagonal. A dash means there is no direct ferry. Draw one edge for each number.
One mark is for the five labelled islands and six edges, and a separate mark is for writing the time on every edge.
A Hamiltonian cycle starts and finishes at Waiben and visits every other island exactly once. It does not have to use every route.
Try to find another cycle
Tap routes to build a cycle from Waiben. You will find that the 28-minute route can never be part of one, so there is only one cycle, travelled in either direction.
Can a Hamiltonian cycle use the 28-minute route from Ngurapai to Gealug?
Gealug can also be reached from Waiben and from Palilug. The 28-minute route is never needed.
Yes. Palilug and Keriri each have only two routes, and the cycle must use all four of them. Add Waiben’s two routes and Ngurapai and Gealug already have two edges each, so there is no room for a sixth.
Reversing the cycle uses the same five routes in the opposite order. The 28-minute route is still left out.
QCAA marking guide · 4 marks
Draw the five islands and join each pair that has a number in the table, as in the animation above.
Marker: correctly constructs a graph showing all 5 labelled vertices and all 6 edges. Any equivalent layout, including crossed edges, is accepted.
Write each travel time on its edge: 18, 14, 25, 16, 20 and 28.
Marker: correctly shows weights on all 6 edges.
\[\text{W}-\text{G}-\text{P}-\text{K}-\text{N}-\text{W}\]
Marker: identifies a Hamiltonian cycle beginning at Waiben. The reverse, W–N–K–P–G–W, is accepted, and so is the cycle marked on the graph.
\[14+16+25+20+18=93\ \text{min}\]
The ferry takes 93 minutes, or 1 h 33 min.
Marker: determines the total travel time. Equivalent times in other units are accepted.
Why there is only one answer
An island on a cycle uses exactly two of its edges. Palilug and Keriri only have two, so all four of their edges are in. Waiben also has only two. That is five edges, which is the whole cycle.
The six routes add to 121 minutes. The cycle leaves out only the 28-minute route, and \(121-28=93\).
Drawing a graph from a table and finding a Hamiltonian cycle are both familiar skills. The complexity is that the table is half filled with dashes and the graph has to come first. The question says "construct", so two of the four marks are for the drawing. I want you to cross out each number in the table as you draw its edge, so you know none have been missed.
Question wording and marking-guide steps are from the 2024 QCAA General Mathematics external assessment, © State of Queensland (QCAA) 2024, licensed under CC BY 4.0, and have been adapted. Tangent Tuition is not affiliated with the QCAA.
Spot a mistake on this page? Report it