题目
Figure 3 models a network of roads. The number on each edge gives the length, in km, of the corresponding road. The vertices, A, B, C, D, E, F and G, represent seven towns. Derek needs to visit each town. He will start and finish at A and wishes to minimise the total distance travelled.
[The total weight of the network is 291]
(a) By inspection, complete the two copies of the table of least distances in the answer book.
(b) Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Derek’s route. Write down the route that gives this upper bound.
(c) Interpret the route found in (b) in terms of the towns actually visited.
(d) Starting by deleting A and all of its arcs, find a lower bound for the route length.
Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G.
(e) By considering the pairings of all relevant nodes, find the length of Clive’s route. State the edges that need to be traversed twice. You must make your method and working clear.
题目中文翻译
图 3 模拟了一个道路网络。每条边上的数字表示对应道路的长度（单位：km）。顶点 A、B、C、D、E、F 和 G 代表七个城镇。Derek 需要访问每个城镇。他将从 A 出发并回到 A，并希望最小化旅行总距离。
[网络总权重为 291]
(a) 通过检查，完成答案本中两份最短距离表。
(b) 从 A 开始，使用最近邻算法找到 Derek 路线长度的上界。写出给出此上界的路线。
(c) 根据实际访问的城镇解释 (b) 中找到的路线。
(d) 通过删除 A 及其所有弧，找到路线长度的下界。
Clive 需要沿道路行驶以检查其是否状况良好。他希望最小化旅行总距离，必须从 A 开始并在 G 结束。
(e) 通过考虑所有相关节点的配对，找到 Clive 路线的长度。写出需要经过两次的边。必须清楚说明方法和计算过程。