题目
The table shows the least distances, in metres, between seven signposts, P, Q, R, S, T, U and V.
| P | Q | R | S | T | U | V | |
|---|---|---|---|---|---|---|---|
| P | – | 105 | 90 | 195 | 270 | 95 | 155 |
| Q | 105 | – | 195 | 295 | 370 | 190 | 255 |
| R | 90 | 195 | – | 110 | 185 | 180 | 245 |
| S | 195 | 295 | 110 | – | 75 | 115 | 170 |
| T | 270 | 370 | 185 | 75 | – | 180 | 245 |
| U | 95 | 190 | 180 | 115 | 180 | – | 65 |
| V | 155 | 255 | 245 | 170 | 245 | 65 | – |
Aisha must visit each signpost to check that it has not been damaged. She needs to find a route which minimises the distance travelled, starting and finishing at P.
(a) Use Prim’s algorithm, starting at P, to obtain a minimum spanning tree for the network. You must clearly show the order in which you select arcs.
(b) Use the answer to part (a) to obtain an initial upper bound for the length of Aisha’s route.
(c) Use the nearest neighbour algorithm, starting at P, to find a second upper bound for the length of Aisha’s route. You should state both the route and its length.
(d) By deleting T and all of its arcs, and using the answer to part (a), obtain a lower bound for the length of Aisha’s route.
题目中文翻译
下表显示了七个路标 P、Q、R、S、T、U 和 V 之间的最短距离（单位：米）。
| P | Q | R | S | T | U | V | |
|---|---|---|---|---|---|---|---|
| P | – | 105 | 90 | 195 | 270 | 95 | 155 |
| Q | 105 | – | 195 | 295 | 370 | 190 | 255 |
| R | 90 | 195 | – | 110 | 185 | 180 | 245 |
| S | 195 | 295 | 110 | – | 75 | 115 | 170 |
| T | 270 | 370 | 185 | 75 | – | 180 | 245 |
| U | 95 | 190 | 180 | 115 | 180 | – | 65 |
| V | 155 | 255 | 245 | 170 | 245 | 65 | – |
Aisha 必须访问每个路标以检查其是否损坏。她需要找到一条从 P 出发并回到 P 的路线，使行驶距离最小化。
(a) 使用 Prim 算法，从 P 出发，求网络的最小生成树。必须清楚显示选择弧的顺序。
(b) 利用 (a) 的答案，求 Aisha 路线长度的初始上界。
(c) 使用最近邻算法，从 P 出发，求 Aisha 路线长度的第二个上界。应说明路线及其长度。
(d) 通过删除 T 及其所有弧，并利用 (a) 的答案，求 Aisha 路线长度的下界。