关于中国邮递员问题的最优完全子图算法-上海师范大学学报.PDFVIP

维普资讯 第35卷第4期 上海师范大学学报(自然科学版) Vo1．35，No．4 2006年 8月 JournalofShanghaiNormalUniversity(NaturalSciences) 2006 ，Aug． 关于中国邮递员问题的最优完全子图算法 李念祖 (上海第二工业大学经济管理学院，上海 201209) 摘 要：利用线图的概念，把 中国邮递员问题转化成求顶点赋权 图的最优完全子图的问题 关键词：最优邮递路线；最短路；最优匹配；线图；最优完全子图 中图分类号：O157、5 文献标识码：A 文章编号：1000．5137(2006)04-0026-04 O 引 言 一 个邮递员的工作是：在邮局里挑选出他所负责的街区的各条街道的邮件，并按一定次序加以排 列，然后按一定路线递送这些邮件，最后返回邮局．自然，邮递员必须走过他负责的街区的每一条街道至 少一次，并希望选择一条总路程最短的递送路线．寻找这样的一条最短递送路线的问题，在国际学术界 称之为中国邮递员问题，因为它首先是由中国数学家提出并加以研究的． 用图论的语言来描述中国邮递员问题，就是：设在边带权的有限连通赋权图G：(，E)中，各条边 ei∈E的权Z(e)≥0；G中任意一条包含G的每条边至少一次的闭链 W ：roe …enuo．称为G的一 条环游，其权z()定义为z(W)=∑z(ei)．则中国邮递员问题就是在G中求一条具有最小权的环游 i。一‘= 1 W ，即：求环游 ，使得z( )=minz()， 是环游．这种环游称为 G的最优邮递路线，或最优 环游． 1 预备知识 对于没有奇点的连通赋权图G，可以利用Fleury算法求得 G的一条最优邮递路线 … ． 对于有奇点的连通赋权图G，1956年我国数学家管梅谷教授提出通常被称为 “奇偶点图上作业法” 的算法来求G的最优邮递路线 J． 1973年Edmonds和Johnson给出一个比较有效的算法，把求有奇点的连通赋权图的最优邮递路线 问题转化为求最短路及最优匹配问题[3]．本文作者把他们的算法叙述为下列 J． 定理1 设G=(，E)是一个有2后个奇点 (后O)的连通赋权图，边e∈E的权为Z(e)≥0，所 有奇点的集合为 Vo= 。， ，…， }∈V．作以 为顶点集的赋权完全图 (G)= ( ，E。)，其中 G 边 ( ， ) 的权Z( )为图G中顶点Ui和顶点 “之间的最短路的长．称 ()为G的奇点最短 。 s 路伴随完全图．在 (G)中求最小权完美匹配 (G)，即L(M )=min∑l(v )，其中M是 (G)的完美匹配．则在 G中把对应于 的每一条边的两个端点(G的奇点)之间的最短路的每条边 各重复一次后得到的赋权图G必无奇点，其任一Euler环游就是图G的最优邮递路线． 收稿 日期：2006-03．11 作者简介：李念祖 (1941一)，男，上海第二工业大学经济管理学院教授，上海师范大学数理信息学院兼职教授 维普资讯 第4期 李念祖：关于中国邮递员问题的最优完全子图算法 27 由于G的奇点最短路伴随完全图是偶数阶的完全图，其完美匹配就是它的最大匹配，所以可以根 据 1970年Edmonds和Johnson提出的求解赋权图的最优最大匹配的算法 求 (G)的最优完美匹 配．但是Edmonds和JohnSOn的这个算法仍然比较复杂．本文作者利用线图的概念 ，把求 (G)的最 优完美匹配的问题转化为求顶点带权图的最优最大完全