图 3 模拟了一个需要检查的自行车道网络。每条弧上的数字表示对应自行车道的长度（单位：km）。Lance 需要每条车道至少经过一次，并希望最小化检查路线的长度。

[网络总权重为 166]

他必须从 A 出发并回到 A。

(a) 使用适当的算法找到路线的长度。写出 Lance 需要经过两次的自行车道。应清楚说明方法和计算过程。

(b) 写出顶点 C 在 Lance 路线中出现的次数。

现在决定检查路线可以在任何顶点结束。Lance 仍然从 A 开始，必须每条车道至少经过一次。

(c) 确定结束点以使路线长度最短。必须给出理由并写出此新最小路线的长度。

这是闭合的中国邮递员问题。先找出奇度顶点 A、C、D、E，再比较它们的三种配对方式。每一对都取两点间的最短路径，选择额外总权重最小的配对；把这些路径上的弧重复一次后，所有顶点均为偶度。

The odd vertices are A, C, D and E. The three possible pairings are:

The minimum pairing is $(\text{A,D})+(\text{C,E})$. The corresponding shortest paths are AD and C-G-H-E, so the repeated arcs are

The minimum route length is

原网络中 C 的度数为 5；最短邮递员路线还会重复 CG，使 C 的度数增加 1，成为 6。在欧拉回路中，每次到达 C 都要沿另一条边离开，因此 C 出现的次数为 $6\div2$。

Vertex C has degree $5$ in the original network. Since CG is repeated, its degree in the augmented network is $6$.

Therefore vertex C appears

路线固定从奇度顶点 A 出发。若终点选为另一个奇度顶点，则 A 和该终点可以保持奇度，只需把其余两个奇度顶点连接起来。分别比较终点为 C、D、E 时需要重复的最短路径；其中不经过 A 的 C-D 最短路径权重最小，所以终点应为 E。

The possible additional paths not involving A are:

The shortest of these is C-G-D, with weight $7$. Thus CG and GD are repeated and the route finishes at

The new minimum route length is