4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ba9337bf-7a3c-49aa-b395-dd7818cf1d13-06_873_1620_242_223}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
[The total weight of the network is 494]
Direct roads between nine factories, A, B, C, D, E, F, G, H and J, are represented in Figure 3.
The number on each arc represents the lengths, in kilometres, of the corresponding road.
The table below shows the shortest distances, in kilometres, between the nine factories.
| A | B | C | D | E | F | G | H | J |
| A | - | 15 | 7 | 25 | 15 | 42 | 64 | 51 | 46 |
| B | 15 | - | 22 | 40 | 30 | 57 | 49 | 36 | 31 |
| C | 7 | 22 | - | 32 | 22 | 49 | 71 | 58 | 53 |
| D | 25 | 40 | 32 | - | 10 | 17 | 57 | 70 | 71 |
| E | 15 | 30 | 22 | 10 | - | 27 | 67 | 66 | 61 |
| F | 42 | 57 | 49 | 17 | 27 | - | 40 | 53 | 72 |
| G | 64 | 49 | 71 | 57 | 67 | 40 | - | 13 | 32 |
| H | 51 | 36 | 58 | 70 | 66 | 53 | 13 | - | 19 |
| J | 46 | 31 | 53 | 71 | 61 | 72 | 32 | 19 | - |
\section*{Table of shortest distances}
- Starting at A, use Prim's algorithm to find a minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.
(3) - State the weight of the minimum spanning tree.
(1)
A route is needed that minimises the total distance to traverse each road at least once. The route must start at E and finish at F . - Determine the length of this route. You must give a reason for your answer.
It is now decided to start the route at C and finish the route at A . The route must include every road at least once and must still minimise the total distance travelled.
- By considering the pairings of all relevant nodes, find the roads that need to be traversed twice.
Naoko needs to visit all nine factories, starting and finishing at the same factory, and wishes to minimise the total distance travelled.
- Starting at B, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Naoko's route. Write down the cycle, obtained from the table of shortest distances, which gives this upper bound.
- By deleting C and all of its arcs, use the values in the table of shortest distances to find a lower bound for the length of Naoko's route.