6 A graph is shown in Fig. 1.1.
The graph is weighted to form the network represented by the weighted matrix in Fig. 1.2. The weights represent distances in km.
A dash (-) means that there is no direct arc between that pair of vertices.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Fig. 1.1}
\includegraphics[alt={},max width=\textwidth]{c4755464-aa15-4720-8f33-5eb7169f4a20-6_439_728_557_248}
\end{figure}
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Fig. 1.2}
| A | B | C | D | E | F |
| A | - | 5 | 3 | 2 | 8 | - |
| B | 5 | - | 3 | 4 | 7 | 6 |
| C | 3 | 3 | - | 1 | 6 | 5 |
| D | 2 | 4 | 1 | - | - | - |
| E | 8 | 7 | 6 | - | - | 6 |
| F | - | 6 | 5 | - | 6 | - |
\end{table}
The shortest path from D to F has total weight 6.
- Write down a path from D to F of total weight 6.
The total weight of the 12 arcs in the network is 56.
- Use the route inspection algorithm to calculate the total weight of the least weight route that covers every arc at least once, starting at vertex A.
- Determine the total weight of the least weight route that covers every arc at least once, starting at vertex B but finishing at any vertex.
Sasha wants to find a continuous route through every vertex, starting and finishing at vertex A, with the least total weight.
- Use an appropriate algorithm to find a lower bound for the total weight of Sasha's route.
- Use the Nearest Neighbour Algorithm, starting at vertex A, to find an upper bound for the total weight of Sasha's route.
Sasha decides to use the route \(A - B - F - E - C - D - A\).
- Comment on the suitability of this route as a solution to Sasha's problem.