下表显示了六个城镇 A、B、C、D、E 和 F 之间的最短距离（单位：km）。

Mei 必须每个城镇至少访问一次。她将从 A 出发并回到 A，并希望她的路线最小化旅行总距离。

(a) 从答案本中的最小生成树开始，使用快捷方式找到 Mei 路线长度低于 520 km 的上界。必须说明使用的快捷方式和上界的长度。

(b) 使用最近邻算法，从 A 开始，找到 Mei 路线长度的另一个上界。

(c) 通过删除 E 及其所有弧，找到 Mei 路线长度的下界。清楚说明方法。

先把最小生成树的每条边重复一次，得到长度 $2\times314=628$ km 的欧拉网络。然后用一条新边跨过已经访问过的顶点，并删去被取代的三条边；选择加入 $CD$，同时删去 $AD,AB,BC$，可把长度降到 520 km 以下。

Doubling every edge of the minimum spanning tree gives a connected Eulerian network of length

Use the shortcut $C-D$ by adding $CD$ and removing $AD$, $AB$ and $BC$. The resulting upper bound is

Hence an upper bound below $520$ km is

官方评分资料还给出另一组有效快捷方式：加入 $EF$，删去 $EB,BA,AF$。它同样保持网络连通且各顶点度数为偶数，并给出更小的上界。

Again, begin with the doubled minimum spanning tree, whose length is $628$ km.

Add $EF$ and remove $EB$, $BA$ and $AF$. Therefore

Thus another valid upper bound is

从 $A$ 出发，每一步都前往尚未访问且距离当前城镇最近的城镇；访问全部城镇后回到 $A$。依次得到 $A-B-E-F-D-C-A$。

Applying the nearest neighbour algorithm from $A$ gives

The corresponding length is

Hence the upper bound is

删除 $E$ 及其所有边后，在其余五个顶点上求最小生成树。再把连接 $E$ 的两条最短边加回；任何完整巡回都必须至少用两条边连接被删除的顶点，因此所得总长度是下界。

After deleting $E$, a minimum spanning tree on $A,B,C,D,F$ consists of

Its length is

The two shortest edges incident to $E$ are

Therefore the lower bound is

Hence the required lower bound is