题目
Figure 2 represents a network of roads connecting a group of villages. The number on each arc is the length, in km, of the corresponding road.
[The total length of the network is 338]
Bolin needs to inspect the network in Figure 2. He must travel along each road at least once, minimising the length of his route.
Bolin’s route must start at A and finish at J.
(a) Determine the length of Bolin’s route. You must make your method clear and state the roads which need to be repeated.
A new road is constructed from F to J which has length 18 km. Bolin must inspect the changed network, starting at A and finishing at J. He must travel along each road at least once, minimising the length of his route.
(b) Determine the change to the length of Bolin’s route.
题目中文翻译
图 2 表示连接一群村庄的道路网络。每条弧上的数字是对应道路的长度（单位：km）。
[网络总长度为 338]
Bolin 需要检查图 2 中的网络。他必须每条道路至少经过一次，同时最小化路线长度。
Bolin 的路线必须从 A 出发，到 J 结束。
(a) 确定 Bolin 路线的长度。必须清楚说明方法并指出需要重复经过的道路。
现修建一条从 F 到 J 的新道路，长度为 18 km。Bolin 必须检查变化后的网络，从 A 出发到 J 结束。他必须每条道路至少经过一次，同时最小化路线长度。
(b) 确定 Bolin 路线长度的变化。
解答
(a)
解法一
思路
展开
这是指定起点 A、终点 J 的路线检查问题。原网络中的奇点为 A、F、K、M；为了得到从 A 到 J 的欧拉迹，要把端点 A 的奇偶性保留为奇数，同时让 J 变成奇数，因此实际需要配对的点为 F、J、K、M。列出三种配对，选取总重复长度最小的一组。
答题过程
展开
The vertices to be paired are F, J, K and M. The three possible pairings are
| Pairing | Total additional length (km) |
|---|---|
| FJ and KM | |
| FK and JM | |
| FM and JK |
The minimum pairing is FM and JK.
The shortest path from F to M is F-G-M, and the shortest path from J to K is J-L-K. Therefore, the roads to be repeated are
Hence the minimum route length is
(b)
解法一
思路
展开
新增 FJ 后，F 与 J 的奇偶性都改变。对于仍从 A 出发、到 J 结束的路线，现在只需把 K 与 M 配对；它们之间的最短路径是 K-G-M，长度为 14 km。把新道路长度和这段必要重复长度加入网络总长，再与 (a) 的 368 km 比较。
答题过程
展开
After the road FJ is added, the only pair that must be joined is K and M. The shortest path K-G-M has length
The new minimum route length is therefore
Thus the change in length is
Therefore, Bolin’s route increases by 2 km.