题目
The table below shows the least distances, in km, between six towns, A, B, C, D, E and F.
Mei must visit each town at least once. She will start and finish at A and wishes her route to minimise the total distance she will travel.
(a) Starting with the minimum spanning tree in the answer book, use the shortcut method to find an upper bound below 520 km for Mei’s route. You must state the shortcut(s) you use and the length of your upper bound.
(b) Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Mei’s route.
(c) Starting by deleting E, and all of its arcs, find a lower bound for the length of Mei’s route. Make your method clear.
题目中文翻译
下表显示了六个城镇 A、B、C、D、E 和 F 之间的最短距离（单位：km）。
Mei 必须每个城镇至少访问一次。她将从 A 出发并回到 A，并希望她的路线最小化旅行总距离。
(a) 从答案本中的最小生成树开始，使用快捷方式找到 Mei 路线长度低于 520 km 的上界。必须说明使用的快捷方式和上界的长度。
(b) 使用最近邻算法，从 A 开始，找到 Mei 路线长度的另一个上界。
(c) 通过删除 E 及其所有弧，找到 Mei 路线长度的下界。清楚说明方法。