3.1附 中国邮路问题.pptVIP

首先把这个实际问题转换成一个非负赋权图G，G的顶点代表街与街之间的交叉路口和终端，两个顶点相邻当且仅当这两点所对应的路口有直通街道而中间不通过其他路口，每条边的权是这条边所对应街道的长度。G的通过每条边至少一次的闭途径称为G的环游。具有最小权的环游称为G的最优环游，则中国邮路问题就是要在赋权图G中找一条最优环游。 * 3.1附录 中国邮路问题 邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。 1、提出问题 返回 结束 上图表示从R1-R15个街道交叉点，街道上的数字表示该街道的长度，单位为米。 2、分析问题 街道结构图 由上构造右图 3、解决问题 返回 结束 寻找Euler图的最优环游的基本思路： （1）用双倍边方法求 的一个Euler赋权母图 ，使 达到最小。 （2）用Fleury算法求得 的Euler环游 ,就是 图 的环游； 定理3.2.1（管梅谷，1960）设 是一个连通的赋权图， 是 的一个Euler赋权生成母图，则 当且仅当 没有重复数大于2的边。并且 的每一个长度至少是3的回路中多重边的权和不超过此回路权和的一半。 返回 结束 奇偶点图上作业法（求最优环游算法）： (1)把 中度为奇数的顶点两两配对，记为 。对每个 ， 中取一条 路 ，将 上的每一条边都添加一条边，从而得到 的一个赋权Euler生成母图 。 (2)去掉 中关于 的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接。 (4)用Fleury算法求 的Euler环游。 (3)检查 的每一个回路，如果某个回路 上多重边 的权和超过此回路权和的一半，则将 进行调整：删除 ， 的边重数增加 1。 例1 下图(a)给出赋权图 ， 是 的四个奇点。根据上述算法,求下图的最优环游。 解：根据上述算法(1)，把 和 配对，和 配对，取 ，并对 中每条边各添加一条边；又取 ，并对 中每条 边各添加一条边。得图(b).依次按算法，得到图(c),(d),(e) *