中国邮递员问题的匹配算法

2013-09-26汪海森卓彩娥闽江学院数学系福建福州350108

长江大学学报(自科版) 2013年25期

汪海森，林耿，卓彩娥（闽江学院数学系，福建福州 350108）

在20世纪60年代，著名数学家管梅谷先生[1]提出一个关于中国邮递员的问题：一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，怎样选择投递路线使所走的路程最短？把该问题抽象成数学图论问题，可以描述为：在一个赋权图G＝（V，E）中，能否找到一条回路C，使C包含G的每条边至少一次且C的长度最短？目前，学者们根据不同思想提出了许多求解中国邮递员问题的算法。这些方法大致可以分成基于图论方法[2－3]和基于智能搜索方法[4－5]2类。笔者提出了一种基于奇度顶点匹配的算法求解中国邮递员问题。首先收缩图中的偶点，形成一个由偶数个奇度顶点组成的新图；然后应用贪心方法找出图的一个配对，加入这些配对点间的边后，得到中国邮递员问题的一个近似最优的投递方案。

1 预备知识

定义1[6]图G的环游是指经过图G每条边至少一次的闭途径，欧拉回路是指经过图G每条边恰好一次的环游。一个图若包含欧拉回路，则这个图称为欧拉图。

引理1[6]图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。

由引理1可知，如果G中没有奇度顶点，则G是欧拉图，那么欧拉回路就是最小的投递路线。当图G中只有2个奇度顶点时，找出这2个点间的最短路径并加入图G中，此时图为欧拉图，且图中的欧拉回路为最小投递路线。当图G中的奇度顶点多于2个时，则奇度顶点的个数为偶数个。对这些奇度顶点进行配对，可以找出一条投递路线。

定义2[7]设图G＝（V，E），E′是E的子集，若E′中任何2条边均不相邻，则称E′为G中的匹配。若在E′中再添加任意一条边，所得集合都不是匹配了，则称E′为极大匹配。边数最多的匹配称为最大匹配。

定义3[7]设M为图G的一个匹配，若存在M中的边以v为端点，则称v是M-饱和点；否则称v是M-不饱和点。若G中的每个节点都是M-饱和的，则称M是完全匹配。

2 求解算法

当图G中包含多于2个奇度顶点时，通过如下方法对它们进行配对：首先，去掉原图G中的偶度顶点，得到一个只包含原图中奇度顶点的新图G′。然后，初始化M＝∅，从图G′中的任意一个顶点出发，找到一条权最小的边｛i，j｝，将该边加入M，并将与顶点i，j关联的边从G′中删除。重复以上步骤，直到找到一个完全匹配。基于以上分析，笔者提出求解中国邮递员问题的匹配算法，具体算法描述如下：

Step 1 除去原图G中的偶度顶点，那么，所得到的新图G′只包含原奇度数结点与它们之间的路径；初始化M＝∅。

Step 2 从G′中任意一个顶点i出发，寻找与它相邻的权为最小的边｛i，j｝。如果边｛i，j｝也是顶点j关联的边中权最小的边，转Step 3；否则，令i＝j，转Step 2。

Step 3 令M＝M∪｛i，j｝并将与顶点i，j关联的边从G′中删除。如果G′非空且连通，转Step 2；如果G′不连通，则增加一条最短路，使得G′连通，转Step 2；如果G′为空，转Step 4。

Step 4 将M加入图G后，所得图为欧拉图，欧拉回路为近似最小投递路线。

3 实例分析

图1 例1示意图

图2 预处理后的图

例1 求如图1所示的中国邮路问题。

解（1）去掉如图1中的偶度数结点，即 V1，V3，V9，V11，V13得到新的图，如图2所示。

（2）从任意一点出发，假设从V2出发，由图2可知以它为顶点的权最小的边为｛V2，V6｝，而以V6为顶点的边的权并没有比边｛V2，V6｝小，故边｛V2，V6｝就是一个配对。去掉以V2，V6为顶点的关联边，再从其他点出发，可知以V4为顶点的权为最小的边为｛V4，V8｝，以V5为顶点的权为最小的边为｛V5，V12｝，以V7为顶点的权为最小的边为｛V7，V10｝。即可得到如图3所示的配对方法。

（3）根据配对原则，在原图即图1中添加重复边，如图4所示，经检验，此配对方案最优，所重复的边的权之和为7。