A-level数学 | 这是D1里面一个十分有趣的知识点，你掌握了吗？

今天给大家讲解一下D1里面的route inspection类型的问题，也叫中国邮差问题（Chinese postman problem），这个其实和我们小时候经常思考的一个问题相关——能否一笔画完一个一个图形。

■If allthe valencies in a graph are even, then the graph is Eulerian.

■If precisely two valencies are odd, and all the rest are even, then the graph is semi-Eulerian.

当一个图像是可以一笔画完的，这样的图像是traversable，那么这个时候这个图像必须是欧拉图像，也就是说图像每个顶点所连接的arc一定是偶数个。

当一个图像也可以一笔画完，但起始点是固定的情况下， 这样的图像是semi-traversable，也就是说这个图像是半欧拉图像，而且起始点必须为图像顶点链接奇数条arc的顶点。

如果当一个图像含有两个以上的链接奇数条arc的顶点，那么这样的图像是不能一笔画出来的，这样的图像是not traversable。

You can use the route inspection (Chinese postman) algorithm to find the shortest route in a network.

■Route inspection algorithm

1.Identify any vertices with odd valency.

2.Consider all possible complete pairings of these vertices.

3.Select the complete pairing that has the least sum.

4.Add a repeat of the arcs indicated by this pairing to the network.

第一步：我们要找出哪些order是奇数的顶点。

A（3）；E（5）；F（3）；G（5）.

第二步：我们要把这些顶点进行配对。

因为我们a问里需要从A点起，到A点止，所以说明图像是欧拉图，所以要对这四个顶点两两配对。

第三步：

第四步：把最短的路径加入到总路径里就是我们所需要的答案。

在（b）问中，我们可以从不同的顶点起止，也就是说明图像为半欧拉图。也是根据Route Inspection Algorithm来解决。

最后为了检验大家是否对这节知识点有清晰的认知，我们留一道真题作为作业，快来看看你会做吗？