运筹学之中国邮递员问题.pdf

运筹学之 中国邮递员问题 昆明理工大学 信息工程与自动化学院 七桥问题 Seven Bridges Problem （引 点）  18世纪著名古典数学问题之一。在哥尼斯 堡的一个公园里，有七座桥将普雷格尔河 中两个岛以及岛与河岸连接起来。问是否 可能从这四块陆地中任一块出发，恰好通 过每座桥一次，再回到起点？ (图见P251页，图10-1) 从七桥问题到一笔画思想  欧拉于1736年研究并解决了此问题， 他 用点表示岛和陆地，两点之间的连线表 示连接它们的桥，将河流、小岛和桥简 化为一个网络，把七桥问题化成判断连 通网络能否一笔画的问题。之后他发表 一篇论文，证明了上述走法是不可能 的。并且给出了连通网络可一笔画的充 要条件这一著名的结论。 如图可见P251页图10-1 （b ） A C D B 因为图中的每个点都只与奇数条相关联，所以不可能一笔画出 一笔画问题  什么是一笔画问题呢？  一笔画问题：从某一点开始画画，笔不 离纸，各条线路仅画一次，最后回到原 来的出发点。 想一想： v 1 a b c v2 v3 v4 图1 图2 • 图1和图2当中哪一个图满足：从图中任何一点出 发，途径每条边，最终还能回到出发点？ • 由此试想一下：一个图应该满足什么条件才能达到 上面要求呢？ 一笔画问题（中国邮路问题基础）  凡是能一笔画出的图，奇点的个数最多 有两个。始点与终点重合的一笔画问 题，奇点的个数必是0 。  在一个多重边的连通图中，从某个顶点 出发，经过不同的线路，又回到原出发 点，这样的线路必是欧拉图，即能一笔 画出的图必是欧拉图。  定理1：连通的多重图G是欧拉图，当且 仅当G中无奇点。  定理2 ：任何一个图中的奇点个数必为偶 数。  推论：连通的多重图有欧拉链，当且仅 当图中有两个奇点。  什么是欧拉链?  给定一个连通多重图G，若存在一条链， 过每边一次，则称这条链为欧拉链。  那什么又事欧拉圈呢？  若存在一个简单圈，过每边一次，且仅 一次，则称为欧拉圈。  一个图若有欧拉圈就可以称之为欧拉图 中国邮递员问题  一个邮递员送信，要走完他负责投递的 全部街道，投完后回到邮局，应该怎样 走，使所走的路程最短？  这个问题是我国管梅谷同志1962年首先 求出来的，因此在国际上通称为中国邮 递员问题。在物流活动中，经常会遇到 这样的问题，如：每天在大街小巷行驶 的垃圾车、洒水车、各售货点的送货车 等都需要解决一个行走的最短路程问 题。  这个问题就是一笔画问题。  定理：连通多重图G有欧拉圈，当且仅当 G 中无基点。  推论：连通多重图G有欧拉链，当且仅当 G恰有两个基点。  如图P277 图10-30 所示，现在的问题 是： 如果我们已经知道图G是可以一笔画的， 首先引入割边概念，设e是连通图G 的一个 边，如果从G 中丢去e，图就不连通了， 则称e是图G 的割边。 奇偶点图上作业法  如果在邮递员所负责的范围内，街道图 中没有奇点，那他就可以从邮局出发， 走过每街道一次，且仅一次，最后回到