题目
The table above shows the least distances, in metres, between seven classrooms, A, B, C, D, E, F and G. A teacher needs to visit each classroom, starting and finishing at A, and wishes to minimise the total distance travelled.
(a) Show that there are two nearest neighbour routes that start from A. State these routes and their corresponding lengths.
(b) Starting by deleting A, and all of its arcs, find a lower bound for the length of the teacher’s route.
(c) Use your results to write down the smallest interval which you can be confident contains the optimal length of the teacher’s route.
题目中文翻译
上表显示了七个教室 A、B、C、D、E、F 和 G 之间的最小距离（单位：米）。一位教师需要访问每个教室，从 A 出发并回到 A，希望最小化旅行总距离。
(a) 证明从 A 出发有两条最近邻路线。写出这些路线及其对应的长度。
(b) 通过删除 A 及其所有弧，找到教师路线长度的下界。
(c) 使用你的结果写出你确信包含教师路线最优长度的最小区间。