第十五章欧拉图与哈密顿图s.ppt

《第十五章欧拉图与哈密顿图s.ppt》由会员分享，可在线阅读，更多相关《第十五章欧拉图与哈密顿图s.ppt（40页珍藏版）》请在三一办公上搜索。

1、第十五章 欧拉图与哈密顿图,15.1 欧拉图,1736年数学家欧拉发表了第一篇图论论文，解诀了哥尼斯堡七桥问题。,定义（欧拉通路和欧拉回路）通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路 通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路 定义（欧拉图和半欧拉图）具有欧拉回路的图称为欧拉图 具有欧拉通路无欧拉回路的图称为半欧拉图 规定平凡图是欧拉图,（1）欧拉图。（2）半欧拉图。（3）不存在欧拉通路，也不存在欧拉回路。（4）欧拉图。（5）不存在欧拉通路，也不存在欧拉回路。（6）不存在欧拉通路，也不存在欧拉回路。,例,（1）（2）（3）,（4）（5）（6）

2、,无向欧拉图与无向半欧拉图的判断方法 定理15.1（无向欧拉图的判定）无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。定理15.2（无向半欧拉图的判定）无向图G是半欧拉图当且仅当G是连通图，且G中恰有两个奇度顶点。,（1）（2）（3）,判断所示两图是否为欧拉图、半欧拉图？,有向欧拉图与有向半欧拉图的判断方法 定理15.3（有向欧拉图的判定）有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。定理15.4（有向半欧拉图的判定）有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。,（4）

3、（5）（6）,由两判定定理，立即可知（4）为欧拉图，（5）、（6）即不是欧拉图，也不是半欧拉图。,欧拉图的性质：欧拉图可以分解成若干个边不重的圈。,定理15.5（欧拉图的判定）G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。,中国的“一笔画”的问题 从图某一点出发，线可以相交但不能重合将图画完的问题。可以看出在“一笔画”的问题中，终点与始点重合的图对应着欧拉图，不重合的对应半欧拉图。,例15.2（P296）,v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2,Fleury算法（1）任取v0V(G)，令P0=v0。（2）设Pi=v0e1v1e2.eivi已经行遍，则按

4、下面方法来从E(G)-e1,e2,.,ei中选取ei+1：（a）ei+1与vi相关联；（b）除非无别的边可供选择，否则ei+1不应该为 G-e1,e2,.,ei中的桥。（3）当（2）不能再进行时，算法停止，得到的Pn=v0e1v1e2.envn为G中的一条欧拉回路。,桥：设eE(G)，若p(G-e)p(G)，则称e为G中的桥。,例15.2（P296）,v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2,例15.2（P296）,利用欧拉图可以解决哥尼斯堡七桥问题：从某地出发，对每座跨河桥只走一次，而在遍历了七座桥之后，却又能回到原地。,由定理15.1（无向欧拉图的判定定理）可知该问

5、题无解。,思考 如下图所示，从一房间出发，问能否不重复地穿过每一道门，通过所有房间？,15.2 哈密顿图,1859年，爱尔兰数学家威廉哈密尔顿发明了一个旅游世界的游戏。将一个正十二面体的20个顶点分别标上世界上大城市的名字，要求玩游戏的人从某城市出发沿12面体的棱，通过每个城市恰一次，最后回到出发的那个城市。,哈密尔顿游戏是在左图中如何找出一个包含全部顶点的圈。,定义（哈密顿通路和哈密顿回路）经过图（有向图或无向图）每个顶点一次且仅一次的通路称为哈密顿通路。经过图每个结点一次且仅一次的回路（初级回路）称为哈密顿回路。定义（哈密顿图和半哈密顿图）存在哈密顿回路的图称为哈密顿图。存在哈密顿通路但不

6、存在哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。,（1）（2）（3）（4）为哈密顿图（5）为半哈密顿图（6）既不是哈密顿图，又不是半哈密顿图。,（1）（2）（3）,（4）（5）（6）,到目前为止，还没有找到判断哈密顿图简单的充分必要条件。下面介绍哈密顿图和半哈密顿图的必要条件 定理15.6 设无向图G=是哈密顿图，V1是V的任意非空子集，则有p(G-V1)|V1|,其中p(G-V1)为G-V1的连通分支数。推论 设无向图G=是半哈密顿图，V1是V的任意非空子集，则有p(G-V1)|V1|+1。注意：（1）定理15.6和推论是必要条件。（2）两定理可以证明一个图不是哈密尔顿图或半哈密顿图。,

7、易见p(G-v1,v2)=3，|v1,v2|=2p(G-v1,v2)|v1,v2|不满足定理15.6，所以图G不是哈密顿图。,例如,G,G-v1,v2,彼得松图,彼得松图满足定理15.6，但不是哈密顿图。,例如,下面给出哈密顿图和半哈密顿图的充分条件 定理15.7 设G=为n阶无向简单图，如G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)n-1，则G中存在哈密顿通路，即G为半哈密顿图。推论 设G=为n（n3）阶无向简单图，如G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)n，则G是哈密顿图。说明：该推论是充分条件但不是必要的。例如：,该五边形是哈密顿图，但任意两个不

8、相邻的顶点度数之和为4，图形阶数为5。,例 在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。如果他们中任两个无共同语言的人与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。解：将这8个人看为平面上的8个点，设为v1,v2,v3,v4,v5,v6,v7,v8。如果vi和vj有共同语言，就在vi和vj之间连无向边（vi,vj）。这样得到一个8阶无向简单图G。viV，d(vi)为与vi有共同语言的人数。由已知条件可知，vi,vjV且ij，均有d(vi)+d(vj)8。由定理15.7的推论可知，G中存在哈密顿回路，设C=vi1vi2 vi7v

9、i8为G中一条哈密顿回路，按这条回路的顺序安排座次即可。,座位问题,亚瑟王和他的骑士们,亚瑟王一次召见他的p个骑士，已知每一个骑士在骑士中的仇人不超过p/2-1个。证明：能让这些骑士围坐在圆桌旁，使每个人都不与他的仇人相邻。,15.3 带权图及其应用,定义15.3（带权图）给定G=（G为有向图或无向图），对G中任意的边e=(vi,vj)(或)，有一实数wij与之相对应，称该实数wij为边e上的权，并将wij标注在边e上，称G为带权图，此时将带权图G记为。带权图应用的领域很广，典型应用有最短路径（无向图）和关键路径（有向图）。,最短路径最具有代表性的问题有：中国邮递员问题欧拉图 货郎担问题（旅行

10、商问题）哈密顿图,中国邮递员问题 问题描述：一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。转化为图论问题：给定一个带权无向连通图，要求找一个回路（未必是简单的），过每边至少一次，并使回路的总权最小。问题的解决：欧拉图法:如果该邮递员负责的范围内，街道图为欧拉图，那么他就可以从邮局出发，走过每条街道一次，最后回到邮局，这样他所走过的路程也就是最短路程。奇偶点图上作业法:如果该邮递员负责的范围内，街道图有奇度点，则必须在某些街道上重复走一次或多次。,如果在某条路线中边（vi,vj）上重复走了几次，我们在图中vi,vj之间增加几条边，令所增加边

11、的权与原来的权相等，并把新增加的边，称为重复边。于是这条路线就是相应新图中的欧拉回路。,由于在任何一个图中，奇度点个数为偶数，所以如果图中有奇度点，就可以把它们配成对。又因为图是连通的，故每一对奇度点之间必有通路，把权和最小的通路上的所有边作为重复边加到图中去，可见新图中无奇度点。我们把增加重复边而使新图不含奇度点的方案称为可行方案，称使重复边的权和最小的可行方案为最优方案。这样一来，原来的问题就可以转化为在一个有奇度点的图中，要求增加一些重复边，使新图不含奇度点，即为一个欧拉图，并且所加重复边的权和最小。现在的问题是在确定一个可行方案之后，怎么判断这个方案是否为最优方案？,图中有四个奇度点，

12、v2,v4,v6,v8，将它们分成两对，比如说v2与v4为一对，v6与v8为一对。连接的v2与v4、v6与v8的通路有好几条，但要取权和最小的一条。,这个图中没有奇度点，故它是欧拉图。对于这个可行方案，重复边的权和为17。,在最优方案中，图中每个圈的重复边的权和不大于该圈权和的一半。对于上述的可行方案，在圈v1v2v9v6v7v8v1中，圈的权和为24，但重复边的权和为13，大于该圈权和的一半，因此需要进行调整。这样可以得到另一可行方案：,这一方案中，重复边的权和为15，并且图中每个圈的重复边的权和不大于该圈权和的一半。,课后练习：求下图所示的中国邮递员问题。,货郎担问题（旅行商问题）问题描述

13、如下：设有n个城市，城市之间均有道路，道路的长度均大于等于0，可能为（对应关联的城市之间无交通线）。今有一个旅行商从某个城市出发，要经过其它n-1个城市恰一次，最后回到出发城市，问如何走使得经过的总路程最短？转化为图论问题：以城市为结点，两城市之间的路为边，路程长度为边上的权，则问题转化为在带权无向图G=中找一个权和最小的哈密尔顿回路。,解：求哈密顿回路可以从任何顶点出发。下面从a点出发，并考虑顺时针与逆时针顺序不同的哈密顿回路。C1=abcda 权和为8C2=abdca 权和为10C3=acbda 权和为12C4=acdba 权和为10C5=adbca 权和为12C6=adcba 权和为8 不考虑顺时针与逆时针顺序，则C1=C6，并为最短的哈密顿回路。,例15.7 下图为4阶完全带权图，求出它的不同的哈密顿回路，并指出最短的哈密顿回路。,最邻近法：此法不是一个最有效的方法,是一种近似算法。设G=是带权无向图,共有n个结点,(1)任取一点记为v1,在其余n-1个点中,找出最邻近v1的点,记为v2形成初级通路v1v2。(2)在其余n-2个点中,找出最邻近v2的点,记作v3,形成初级通路v1v2v3,如此一直下去直到找到一条哈密尔顿回路为止。说明：此算法与初始点的选取有关。,旅行商问题的精确求法：匈牙利算法,