3.1附 中国邮路问题.ppt

《3.1附 中国邮路问题.ppt》由会员分享，可在线阅读，更多相关《3.1附 中国邮路问题.ppt（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、3.1附中国邮路问题 首先把这个实际问题转换成一个非负赋权图G，G的顶点代表街与街之间的交叉路口和终端，两个顶点相邻当且仅当这两点所对应的路口有直通街道而中间不通过其他路口，每条边的权是这条边所对应街道的长度。G的通过每条边至少一次的闭途径称为G G的环游的环游。具有最小权的环游称为G的最优环游最优环游，则中国邮路问题就是要在赋权图G中找一条最优环游。2、分析问题奇偶点图上作业法（求最优环游算法）：奇偶点图上作业法（求最优环游算法）：(1)把 中度为奇数的顶点两两配对，记为 。对每个 ，中取一条 路 ，将 上的每一条边都添加一条边，从而得到 的一个赋权Euler生成母图 。(2)去掉 中关于

2、的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接。(4)用Fleury算法求 的Euler环游。(3)检查 的每一个回路，如果某个回路 上多重边 的权和超过此回路权和的一半，则将 进行调整：删除 ，的边重数增加 1。例例1 1 下图(a)给出赋权图 ，是 的四个奇点。根据上述算法,求下图的最优环游。解：根据上述算法(1)，把 和 配对，和 配对，取 ，并对 中每条边各添加一条边；又取 ，并对 中每条 边各添加一条边。得图(b).依次按算法，得到图(c),(d),(e)奇偶点图上作业法缺陷：奇偶点图上作业法缺陷：奇偶点

3、图上作业法需要检查图中的每个回路。随着顶点个数和边数增加，回路个数增加。如下图一，图二。图一回路超过150个，图二回路至少有上千个。思考：如何求恰好有两个奇点的思考：如何求恰好有两个奇点的赋权图的赋权图的最优环游？最优环游？设 恰好有两个奇点 和 ，则可以利用2.2节求出 的一条最短 路 ，在 中只要把 中的每一条边中再添加一条边，加上权就可得Eluer图 。可以证明 的Eluer环游就是的最优环游。下左图的最优环游即为右图。思考：思考：如何求恰好有如何求恰好有 个奇点的赋权图的最优个奇点的赋权图的最优环游？环游？此此课件下件下载可自行可自行编辑修改，修改，仅供参考！供参考！感感谢您的支持，我您的支持，我们努力做得更好！努力做得更好！谢谢!