D2 June 2005 Q2
2.
The network in the diagram shows the distances, in km, of the cables between seven electricity relay stations \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\). An inspector needs to visit each relay station. He wishes to travel a minimum distance, and his route must start and finish at the same station.
By deleting \(C\), a lower bound for the length of the route is found to be 129 km.
(a) Find another lower bound for the length of the route by deleting \(F\). State which is the better lower bound of the two. (5)
(b) By inspection, complete the table of least distances. (2)
The table can now be taken to represent a complete network.
(c) Using the nearest-neighbour algorithm, starting at \(F\), obtain an upper bound to the length of the route. State your route. (4)
| Scheme | Marks |
|---|---|
| Deleting \(F\) leaves r.s.t | |
 | |
| r.s.t. length = 86 | M1 A1 |
| so lower bound \(= 86 + 16 + 19 =\) 121 | M1 A1 |
| \(\therefore\) best L.B is 129 by deleting \(C\) (ft from choice) | B1ft |
| (5) |
| Scheme | Marks |
|---|---|
| Add 33 to \(BF\) and \(FB\) | B1 |
| Add 31 to \(DE\) and \(ED\) | B1 |
| (2) |
| Scheme | Marks |
|---|---|
| Tour, visits each vertex, order correct using table of least distances. | M1 A1 |
| e.g. \(F\ C\ D\ A\ B\ E\ G\ F\) (actual route \(F\ C\ D\ C\ A\ B\ E\ G\ F\)) | A1 |
| upper bound of 138 km | A1 |
| (4) | |
| (11 marks) |