The factory supplies groceries to stores in five towns, `Q`, `R`, `S`, `T` and `U`, represented by vertices on the graph below.
The edges of the graph represent roads that connect the towns and the factory.
The numbers on the edges indicate the distance, in kilometres, along the roads.
Vehicles may only travel along the road between towns `S` and `Q` in the direction of the arrow due to temporary roadworks.
Each day, a van must deliver groceries from the factory to the five towns.
The first delivery must be to town `T`, after which the van will continue on to the other four towns before returning to the factory.
- i. The shortest possible circuit from the factory for this delivery run, starting from town `T`, is not Hamiltonian.
Complete the order in which these deliveries would follow this shortest possible circuit. (1 mark)
--- 0 WORK AREA LINES (style=lined) ---
factory – `T` – ___________________________ – factory
- ii. With reference to the town names in your answer to part (a)(i), explain why this shortest circuit is not a Hamiltonian circuit. (1 mark)
--- 1 WORK AREA LINES (style=lined) ---
- Determine the length, in kilometres, of a delivery run that follows a Hamiltonian circuit from the factory to these stores if the first delivery is to town `T`. (1 mark)
--- 3 WORK AREA LINES (style=lined) ---