可行遍性及赛题讲解ppt课件

《可行遍性及赛题讲解ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、可行遍性问题Euler图中国邮递员问题Hamilton图推销员问题建模案例：最佳灾情巡视路线文理学院数学系：徐艳xuyan555@sina.com1Euler图1、图的定义定义一个二元有序数组（V，E）称为一个图，记作G=（V，E）。V称为顶点，E为边。若每个边对应一个数F，称（V，E，F）为赋权图。如果两点是有序的，则称有向图，否则，无向图。常用术语：（1）端点相同的边称为环。（2）若一对顶点之间有两条以上的边联结，则这些边称为重边。1Euler图（3）有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边。（4）

2、边和它的端点称为互相关联的。（5）既没有环也没有重边的图称为简单图。（6）任意两顶点都相邻的简单图，称为完备图。1Euler图2、顶点的次数定义（1）在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数，记为d(v)。（2）在有向图中，从顶点v引出的边的数目称为v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d-(v)。d(v)=d+(v)+d-(v)称为v的次数。容易验证公式：由公式可以证明任何图中奇次顶点的总数必为偶数；生活中握过奇次手的人数是偶数。1Euler图例子哥尼斯堡（Konigsberg）七桥问题Eule

3、r在1736年访问Konigsberg时，他发现Konigsberg城中有一条名叫Pregel的河流，河上建有七座桥如图所示:市民有趣的消遣活动是星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点，是否可能？1Euler图1Euler图定理对于非空连通图G，下列命题等价：（1）G是Euler图；（2）G无奇次数顶点；（3）G的边集能划分为圈。定理图G是Euler图的充分必要条件是：图G连通且所有顶点的次数均为偶次。可见，七桥问题中，每个顶点都是奇次的，由上述定理知，七桥问题不是Euler图，所以不存在Euler迹

4、，此图不可以“一笔画”。1Euler图确定Euler图中Euler环游的方法Fleury算法解决了这一问题。Fleury算法的基本思想：从任一点出发，每当访问一条边时，先要进行检查。如果可供访问的边不止一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选为止。注：割边的定义：设G连通，，若从G中删除边e后，图G－{e}不连通，则称边e为图G的割边。1Euler图1Euler图2中国邮递员问题邮递员从邮局出发，经过他所投递范围的每一条街道至少一次，完成邮件的投递任务后返回邮局。如何安排他的路线，使得总路程最短。这个问题最早

5、由山东大学的管梅谷1962年提出，并给出了一个解法，被国际上称为中国邮递员问题。2中国邮递员问题一、Euler图中的最优环游显然这时任意一个Euler环游都是最优环游。可以用Fleury算法找出。二、非Euler图中的最优环游邮递员要完成任务，某些边经过的次数超过一次，即图G不是Euler图。解决这类问题的一般方法是，把邮递员重复走过的边在原图上画出，权与原边一样(这种边称为重复边)，使原图变成Euler图，但希望的所有添加的重复边的权的总和为最小。2中国邮递员问题uxvwyz16252334221uxvwyz162533422122112怎

6、样添加一些重复边，使得原图变为Euler图，并且重复边的权和达到最小？2中国邮递员问题情形1G正好有两个奇次顶点。设G正好有两个奇次顶点u和v，求G的最佳环游的算法如下：（1）用Dijkstra(迪克斯特拉）算法求出顶点u和v之间的最短路径P。（2）令G*=G∪P，则G*为Euler图。（3）用Fleury算法求出G*的Euler环游，这就是G的最佳环游。2中国邮递员问题情形2图G有2n个奇次顶点（n≥2)Edmonds于1965年提出的最小对集算法，很好的解决了这一类问题。Edmonds算法的基本思想：先将奇次顶点配对，要求最佳配对，即点对

7、之间距离总和最小，再沿点对之间的最短路径添加重复边得Euler图G*，G*的Euler环游便是原图的最佳环游。2中国邮递员问题Edmonds最小对集算法：（1）用Floyd算法求出所有奇次顶点之间的最短路径和距离。（2）以G的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1。（3）用Edmonds算法求出G1的最小权理想匹配M,得到奇次顶点的最佳配对。（4）在G中沿配对顶点之间的最短路径添加重复边得Euler图G*.(5)用Fleury算法求出G*的Euler环游，这就是G的最佳环游

8、。2中国邮递员问题例求图1所示投递区的一条最佳邮递路线。v1v2v3v4v5v6v7v8v9123569810111234图12中国邮递员问题解图中有v4,v7,v