7 A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors.
The cameras at the junctions and the lengths of the 11 corridors between them, in metres, are shown in the table below.
| A | B | C | D | E | F | G |
| A | | 64 | 60 | 111 | | | |
| B | 64 | | | 72 | 103 | | |
| C | 60 | | | 66 | | 58 | |
| D | 111 | 72 | 66 | | 32 | 127 | |
| E | | 103 | | 32 | | | 82 |
| F | | | 58 | 127 | | | 75 |
| G | | | | | 82 | 75 | |
- Model this information as a network.
- Use an appropriate algorithm to calculate the minimum distance from A to each of the other vertices.
The run-time of an algorithm for finding this minimum distance is proportional to the total number of comparisons used. For a network with \(n\) vertices, the worst case is when the algorithm is applied to a network based on the complete graph \(\mathrm { K } _ { n }\).
In each pass
- A vertex is made permanent and the temporary label at all adjacent vertices that are not yet permanent are updated. This uses 1 comparison for every such vertex (adjacent to the permanent label) that previously already had a temporary label.
- The best temporary labels at all vertices that do not yet have permanent labels are then compared to determine the next vertex to become permanent. If there are \(k\) such vertices this involves \(k - 1\) comparisons.
- By considering the number of comparisons of each type in each iteration, show that the algorithm uses a total of 6 comparisons when it is applied to a network based on the complete graph \(\mathrm { K } _ { 4 }\).
You are given that the total number of comparisons used when the algorithm is applied to a network based on \(\mathrm { K } _ { n }\) is \(( n - 1 ) ( n - 2 )\).
A computer takes 0.03 seconds to apply this algorithm on a network based on \(\mathrm { K } _ { 7 }\). - Calculate, to \(\mathbf { 1 }\) decimal place, how many seconds it will take the computer to apply the algorithm to a network based on \(\mathrm { K } _ { 70 }\).
\section*{Question 7 continues on the next page}
The manager wants to construct a tour (a closed route) that passes each camera.
- Find a lower bound for the length of this tour by initially deleting D .
- Find an upper bound for the length of this tour by using the nearest neighbour algorithm starting from D.
- Deduce the length of the shortest possible tour. Briefly explain your reasoning.
\section*{END OF QUESTION PAPER}