4 Tom is planning a day out walking. He wants to start from his sister's house ( S ), then visit three places \(\mathrm { A } , \mathrm { B }\) and C (once each, in any order) and then finish at his own house (T).
- Complete the graph in the Printed Answer Booklet showing all possible arcs that could be used to plan Tom's walk.
Tom needs to keep the total distance that he walks to a minimum, so he weights his graph.
- (a) Why would finding the shortest path from S to T , on Tom's network, not necessarily solve Tom's problem?
(b) Why would finding a minimum spanning tree, on Tom's network, not necessarily solve Tom's problem?
The distance matrix below shows the direct distances, in km , between places.
| S | A | B | C | T |
| n S | 0 | 3 | 2 | 5 | 4 |
| nA | 3 | 0 | 2 | 2.5 | 2 |
| nB | 2 | 2 | 0 | 3.2 | 2.5 |
| n | 5 | 2.5 | 3.2 | 0 | 2 |
| \cline { 2 - 6 }
T | 4 | 2 | 2.5 | 2 | 0 |
| \cline { 2 - 6 } | | | | | |
| \cline { 2 - 6 } |
- - Use an appropriate algorithm to find a minimum spanning tree for Tom's network.
- Give the total weight of the minimum spanning tree.
- - Find the route that solves Tom's problem.
- Give the minimum distance that Tom must walk.