§10.2 欧拉回路与中国邮递员问题

10.2.1 欧拉回路

所谓欧拉回路是与哥尼斯堡七桥问题相联系的．在哥尼斯堡七桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点．与此相反，设G(V，E)为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G为欧拉图．

10.2.2 连通图

称图10-3中的A、B、C、D为顶点，而把连接顶点之间的线称为边，称由这些点和线组成的一个整体为图，显然图10-3中任两点都可以通过一系列线连接起来(未必是一条直接连接两点的线，如图10-3中的C、D可以由d、f两条线连接起来)，这样的图称为连通图．下面图10-7～图10-10都是连通图，而图10-11就不是连通图．

图10-7

图10-8

图10-9

图10-10

图10-11

10.2.3 中国邮递员问题

前面已看到对满足下列两个要求的图就可以一笔画出：(1)首先是连通图；(2)其次奇点个数为0或2，当且仅当奇点个数为0时，始点和终点重合，形成的一笔画称为欧拉回路，而当奇点个数为2时，形成的一笔画称为欧拉迹，如图10-12所示．

我们知道，对于可以一笔画出的图，首先必须是连通的；其次对于图中的某点，如果不是始点或终点，那么该点必有进有出，即交会于该点的弧线总是成双成对的，该点必定是偶点．

七桥问题的图的奇点的个数为4，这表明七桥问题不是欧拉回路，也不是欧拉迹，因而，不论始点和终点是否重合都不可能找到一条经过七座桥且每座桥只走一次的路线！

随着时间的推移，图论不断发展了，欧拉回路问题也有所拓广．到了20世纪，又出现了一个新的问题．

图10-12

图10-13

如图10-13所示，一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．(图10-13中路旁各数字分别表示对应路段的长度，单位：华里)．邮递员习惯按路线KHGFEDCBAIABJDEKJIHK投递(图10-13中★为邮局)．聪明的读者朋友，你知道邮递员的路线是最短的吗？如果不是，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生(山东师范大学数学系教授)在1962年首次提出的，管梅谷等一批科研人员把物资调运中的图上作业法与一笔画原理科学地结合起来，解决了这类邮递员投邮路线问题，因此该问题被国际数学界称为“中国邮递员问题”．

(请读者帮助这位邮递员设计一条最短路线，并说明最短路线比邮递员的路线少几华里？)

下面，我们来分析这个问题：

由于网络的奇点必定成双，又图10-13中奇点有6个，根据一笔画原理，图10-13不存在欧拉回路，则必须通过添加弧线，使每个顶点均变成偶点，同时考虑添加的弧线长度总和最短才满足要求．显然两奇点间可以直接添一条弧；奇点与偶点间添一条弧且该偶点还需与另一奇点添一条弧；两偶点间不必添弧．

添弧时应注意：(1)不能出现重叠添弧．重叠添弧应成对抹去，这样并不改变每一点的奇偶性；(2)每一个圈上的添弧总长不能超过圈长的一半．否则应将该圈上的原添弧抹去，而在该圈上原没有添弧的路线上添加弧，这样也不改变每一点的奇偶性．

注意了(1)、(2)，既保证了不改变每点的奇偶性，又保证了添弧总长最短．

现在我们看邮递员的投邮路线，如图10-14所示，添弧后的新图形已是不含奇点的线路，根据一笔画原理，这个线路的全部弧线可以构成一条欧拉回路．对照(1)、(2)可知，图10-14中添弧总长不是最短，必须调整．显然在［ABJKHI］圈中，添弧总长超过了该圈长的一半．调整后，如图10-15．此时，添弧不重叠并且每一个圈上的添弧总长都不超过本圈长的一半．另外，每点奇偶性相对于图10-14没有改变，全是偶点．全部弧线仍可以构成一条欧拉回路，并且这条路线才是最短投邮路线．因此，邮递员的投邮路线并非最短．

根据以上分析，最短投邮路线可以设计为：

KHGFEDCBAIHIJBJDEKJK或KJKHGFEDCBAIHIJBJDEK等．此时，最短路线比邮递员路线少0.8华里．

中国邮递员问题的巧妙解决，也使这个问题成为数学知识古为今用的典范．

图10-14

图10-15