3.
\begin{table}[h]
| \cline { 2 - 9 }
\multicolumn{1}{c|}{} | A | B | C | D | E | F | G | H |
| A | - | 24 | 42 | 48 | 34 | 37 | 32 | 22 |
| B | 24 | - | 40 | 35 | 30 | 41 | 39 | 44 |
| C | 42 | 40 | - | 21 | 26 | 45 | 38 | 36 |
| D | 48 | 35 | 21 | - | 32 | 37 | 29 | 27 |
| E | 34 | 30 | 26 | 32 | - | 34 | 40 | 28 |
| F | 37 | 41 | 45 | 37 | 34 | - | 43 | 41 |
| G | 32 | 39 | 38 | 29 | 40 | 43 | - | 38 |
| H | 22 | 44 | 36 | 27 | 28 | 41 | 38 | - |
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{table}
Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H.
- Use Prim's algorithm, starting at A , to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree.
- State the weight of the minimum spanning tree.
\begin{table}[h]
| \cline { 2 - 9 }
\multicolumn{1}{c|}{} | \(\mathbf { A }\) | \(\mathbf { B }\) | \(\mathbf { C }\) | \(\mathbf { D }\) | \(\mathbf { E }\) | \(\mathbf { F }\) | \(\mathbf { G }\) | \(\mathbf { H }\) |
| \(\mathbf { J }\) | 31 | 27 | 50 | 29 | 43 | 25 | 49 | 35 |
\captionsetup{labelformat=empty}
\caption{Table 2}
Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels. - Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav's route. You must state your route and its length.
- Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav's route.