第三讲 图论模型.ppt

图论模型;哥尼斯堡七桥问题 (1736 年);;哥尼斯堡七桥问题;SIX BRIDGES;哪 些 图 可 以 一 笔 画 ?;这些图形能一笔画吗？ ;能一 笔 画的图;; 一笔画;8;此图可以一笔画吗?;3; 偶点 奇点 ;奇点= 4 偶点= 3; 一笔画;全是偶点，没有奇点;; 一笔画的图 至多有两个奇点 ;两个奇点;非 一 笔 画 多过两个奇点！;欧拉定理（1736） 让我们再回到七桥问题中来。在七桥问题的图中有四个奇点，因此，欧拉断言这个图无法一笔画出，也即游人不可能不重复地一次走遍七座桥.更进一步地，欧拉在解决七桥问题的同时彻底地解决了一笔画的问题，给出了下面的欧拉定理： ①由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图 ②凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。 ③其他情况的图，都不能一笔画出。 综上三点，我们可以得出欧拉定理的又一描述：一个图G能一笔画的充要条件是G连通并且奇顶点的个数等于0或2。 欧拉定理的又一说法：一个图G是欧拉图的充要条件是G连通且G中每个点都是偶点。;欧拉 1707 - 1783 ;欧拉 （EULER 15.4.1707-18.9.1783);;邮递员问题;5; 这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．若街道图如上图所示，P点表示“邮局”，那么——如何寻找最短邮递路线呢? ;相关概念 赋权图(weighted graph)：对图中的顶点和边 赋以具体的含义和权（权的集合用W表示），这样的图称为赋权图，记为N=(V,E,W)。 环游（cycle）:在一个赋权图N=(V,E,W) 中， 经过 N 中每一边至少一次的回路称为 N 的环游。 欧拉环游（Eulerian cycle） :而经过 N 中每一边恰好一次的环游称为欧拉环游/欧拉回路。 欧拉图（Eulerian graph） :如果图G包含欧拉环游,则该图G称为 欧拉图。; 我们已知道，一笔画和欧拉图既有联系又有区别。一个图能一笔画不一定是欧拉图，因为一笔画的图可能有两个奇顶点，而欧拉图没有奇顶点；另一方面，一笔画和欧拉图都又是连通的。下面要继续介绍求欧拉环游的算法——弗罗莱算法： ;弗罗莱算法（Fleury’s Algorithm） 算法步骤如下：（1）在图G(V,E)中,V= , 任取起始点 （2）设路 已选出，Gr=G- ,则从E\ 中选出 边，使之与 相连，除非没有其它选择， 仍应为连通的。 （3）重复步骤（2），直至不能进行下去为止。 接下来我们一起来看看用弗罗莱算法求下图的欧拉环游的过程：;分析：因为该图的各个顶点都是偶点，所以该图可以一笔画，且下图是用弗罗莱算法找出的从A点出发的一个欧拉图（被标注 “9”和“19”的边为此连通图的割边）。 ;我们已较深入地讨论了一笔画问题，现在要回到中国邮递员问题中来。 邮递员问题实际要求的就是在赋权图G中找出一条权最小的环游，即最优环游/回路，也就是说要从包含G的每条边的回路中找一条权数最小的回路。下面求最优邮路的方法称“管梅谷算法”（或称奇偶点图上作业法）。;奇偶点图上作业法如下: 如果G是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，此即G的最优环游； 若不然，G不是欧拉图，即如果存在奇点，则下面给出在有奇点的连通图中寻找最小权数的回路的方法：;奇偶点图上作业法 口诀： ????????? ?? 先分奇偶点，奇点对对连； ????????? ? ?连线不重迭，重迭需改变； ???????? ?? ?圈上连线长，不得过半圈。; 在现实生活中，很多问题都可以转化为中国邮递员问题，例如道路清扫时如何使开空车的总时间最少的问题等等．因为“奇偶点图上作业法”要验证每个回路，很不方便,所以当点数较多时，Edmonds和Johnson在1973年提出一种比较有效的方法：可用Edmonds和Johnson算法（这一算法较为复杂，这里不作介绍）。;P;Travelling salesman