5 Jess and Henry are out shopping. The network represents the main routes between shops in a shopping arcade. The arcs represent pathways and escalators, the vertices represent some of the shops and the weights on the arcs represent distances in metres.
\includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-6_586_1084_367_495}
The total weight of all the arcs is 1200 metres.
The table below shows the shortest distances between vertices; some of these are indirect distances.
| M | \(N\) | \(P\) | \(R\) | \(S\) | \(T\) | \(V\) | \(W\) |
| M | - | 70 | 110 | 190 | 60 | 190 | 140 | 90 |
| N | 70 | - | 40 | 130 | 120 | 170 | 80 | 150 |
| \(P\) | 110 | 40 | - | 100 | 80 | 140 | 120 | 110 |
| \(R\) | 190 | 130 | 100 | - | 130 | 40 | 50 | 160 |
| \(S\) | 60 | 120 | 80 | 130 | - | 170 | 80 | 30 |
| \(T\) | 190 | 170 | 140 | 40 | 170 | - | 90 | 200 |
| \(V\) | 140 | 80 | 120 | 50 | 80 | 90 | - | 110 |
| W | 90 | 150 | 110 | 160 | 30 | 200 | 110 | - |
- Use a standard algorithm to find the shortest distance that Jess must travel to cover every arc in the original network, starting and ending at \(M\).
- Find the shortest distance that Jess must travel if she just wants to cover every arc, but does not mind where she starts and where she finishes. Which two points are her start and finish?
Henry suggests that Jess only needs to visit each shop.
- Apply the nearest neighbour method to the network, starting at \(M\), to write down a closed tour through all the vertices. Calculate the weight of this tour. What does this value tell you about the length of the shortest closed route that passes through every vertex?
Henry thinks that Jess does not need to visit shop \(W\). He uses the table of shortest distances to list all the possible connections between \(M , N , P , R , S\) and \(V\) by increasing order of weight. Henry's list is given in your answer book.
- Use Kruskal's algorithm on Henry's list to find a minimum spanning tree for \(M , N , P , R , S , T\) and \(V\). Draw the tree and calculate its total weight.
Jess insists that they must include shop \(W\).
- Use the weight of the minimum spanning tree for \(M , N , P , R , S , T\) and \(V\), and the table of shortest distances, to find a lower bound for the length of the shortest closed route that passes through all eight vertices.