大学离散数学 欧拉图和哈密尔顿图.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,计算机科学学院 刘芳,2025/10/27 周一,1,第,15,章 欧拉图和哈密顿图,15.1,欧拉图,15.2,哈密尔顿图,2025/10/27 周一,2,15.1,欧拉图,15.1.1,问题引入,15.1.2,欧拉图,15.1.3,欧拉图的判定定理,15.1.4,中国邮路问题,2025/10/27 周一,3,15.1.1,问题引入,哥尼斯堡七桥问题,Seven bridges of,K,nigsberg,problem,问题分析,：,A,C,B,D,2025/10/27 周一,4,15.1.2,欧拉图,定义,15.1,：,设,V,，,E,是连通图,欧拉通路,（,Euler Path,）,半欧拉图,欧拉回路,（,Euler Circuit,）,欧拉图,(,Eulerian,),说明,规定平凡图是欧拉图；,欧拉通路是简单通路,欧拉回路是简单回路；,环不影响图的欧拉性。,2025/10/27 周一,5,15.1.2,欧拉图,实例,2025/10/27 周一,6,15.1.3,欧拉图的判定定理,无向欧拉（半欧拉）图的判定定理,定理,15.1,无向图,G,是欧拉图,G,是连通的且无奇度顶点。,定理,15.2,无向图,G,是半欧拉图,G,是连通的，且,G,中恰有,2,个奇度顶点,2025/10/27 周一,7,15.1.3,欧拉图的判定定理,例,1,：,无欧拉通,(,回,),路,欧拉图,欧拉图,半欧拉图,半欧拉图,无欧拉通,(,回,),路,2025/10/27 周一,8,15.1.3,欧拉图的判定定理,例,2,：,A,C,B,D,2025/10/27 周一,9,15.1.3,欧拉图的判定定理,例,3,：一笔画问题及推广,问题描述,问题分析,设图中有2,k,个奇度点，,若,k,0，,可以 一笔画成，且起点和终点相同；,若,k,1，,可以 一笔画成，起点和终点恰为图中的两个奇度点；,若,k,1，,可以,k,笔画成，每笔的起点和终点恰为图中的两个奇度点；,2025/10/27 周一,10,15.1.3,欧拉图的判定定理,有向欧拉（半欧拉）图的判定定理,定理,15.3,有向图,D,是,欧拉图,D,是强连通且所有顶点的入度等于出度。,定理,15.4,有向图,D,是,半欧拉图,D,是单向连通的且,D,中恰有两个奇度顶点，其中一个顶点的入度比出度大1,一个顶点的入度比出度小1,其余的顶点的入度等于出度。,2025/10/27 周一,11,15.1.3,欧拉图的判定定理,例,1,欧拉图,无欧拉通路,无欧拉通路,半欧拉图,无欧拉通路,半欧拉图,2025/10/27 周一,12,15.1.3,欧拉图的判定定理,例2：,问题描述,计算机鼓轮设计中模数转换问题,问题分析,A,B,C,1,0,0,01,1,1,0,2025/10/27 周一,13,15.1.4,中国邮路问题,问题描述：,设有某邮递员为送信，从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条最少一次，则怎样选择投递路线使所走的路程最短？,问题抽象：,将街区用一个图,G,进行表示，上述问题可以用图论的语言来描述：,在一个赋权图中，能否找到一条包含每条边最少一次且长度最短回路？,2025/10/27 周一,14,15.1.4,中国邮路问题,问题分析,若,G,不连通，则无解,否则：,若,G,是欧拉图，则,G,的欧拉回路就是问题的最优解。,若,G,是半欧拉图，且邮局就是其中一个奇度点,问题转化为求,G的,欧拉通路,和两点的,最短路径,问题。,若,G,中次数为奇数的结点多于2,则回路中必须增加更多的重复边，这时，怎样使重复边的总长度最小？,2025/10/27 周一,15,15.1.4,中国邮路问题,例如：,2025/10/27 周一,16,15.1.4,中国邮路问题,判断条件,定理：,设,L,是图,G,的包含所有边的回路，则,L,具有最小长度的充分必要条件是：,每条边最多重复一次；,G,的每个回路上，所有重复边的长度之和，不超过该回路长度的一半。,2025/10/27 周一,17,15.2,Hamilton,图,15.2.1,问题引入,15.2.2,Hamilton,图的定义,15.2.3,Hamilton,图的判定方法,15.2.4,应用举例,2025/10/27 周一,18,15.2.1,问题引入,周游世界问题(,W.Hamilton,1859,年),2025/10/27 周一,19,15.2.1,问题引入,Willam,Rowan Hamilton,(18051865):,2025/10/27 周一,20,15.2.2 Hamilton,图的定义,定义,15.2,：,设图,G,V,，,E,哈密顿通路半哈密顿图,哈密顿回路哈密顿图,说明：,规定平凡图是哈密顿图,2025/10/27 周一,21,15.2.2 Hamilton,图的定义,例：判断下图是否为,H,图？,2025/10/27 周一,22,15.2.3 Hamilton,图的判定方法,定理,15.6,（必要条件）,设,G,V,，,E,是,H,图，则对,V,的每个非空子集,V,1,均有下式成立：,p,（,G,V,1,）|,V,1,|,-（1）,证明：,若,G,是,H,回路,C,，则（1）显然成立；,若,G,是,H,图，则设,C,是,G,的一条,H,回路，则对,V,的任意非空子集,V,1,，,均有,p（C,V,1,）|,V,1,|，,而,C,V,1,是,G,V,1,的生成子图，,故有,p（G,V,1,）,p（C,V,1,）,于是有：,p（G,V,1,）|V,1,|,成立。,2025/10/27 周一,2315.2.3 Hamilton,图的判定方法,|,V,1,|3，,p,（,G,V,1,）4,p,（,G,V,1,）|,V,1,|,不成立，故,G,非,H,图。,G,GV,1,例1：,2025/10/27 周一,24,15.2.3 Hamilton,图的判定方法,例2：,证明下述各图不是哈密顿图:,(,a,),(,b,),推论,1:,哈密尔顿图无割点.,2025/10/27 周一,25,15.2.3 Hamilton,图的判定方法,例,3,：,证明下述各图不是哈密顿图。,2025/10/27 周一,26,15.2.3 Hamilton,图的判定方法,推论,2,：,对二部图,G,V,1,V,2,E,若|,V,1,|,V,2,|，,则一定不是,H,图。,证明：,对二部图,G,V,1,V,2,E,设|,V,1,|,V,2,|，,则,p,(,G,V,1,)|,V,2,|,V,1,|，,这与定理,15.6,p,(,G,V,1,)|,V,1,|,相矛盾,故,G,不是,H,图,。,2025/10/27 周一,27,15.2.3 Hamilton,图的判定方法,例,4,：,证明右图不是哈密顿图,证：,设存在一条哈密顿回路,a,f,g,是2度顶点,边(,a,c,),(,f,c,),和(,g,c,),必在这条哈密顿回路上,从而点,c,出现3次,与假设矛盾.,故该图不是哈密顿图,a,b,c,d,e,f,g,2025/10/27 周一,28,15.2.3 Hamilton,图的判定方法,哈密顿回路(通路)的充分条件,定理,15.7,：,设,G,是,n,(,n,3),阶无向简单图,若任意两个不相邻的顶点,u,v,有：,d,(,u,)+,d,(,v,),n,-1,，,则,G,中存在,哈密顿通路,;,推论：,设,G,是,n,(,n,3),阶无向简单图,若任意两个不相邻的顶点,u,v,有：,d,(,u,)+,d,(,v,),n,G,中存在哈密顿回路，,G,为,哈密顿图,;,2025/10/27 周一,29,15.2.4,应用举例,例,1,（排座问题）,有7个人,A,会讲英语,B,会讲英语和汉语,C,会讲英语、意大利语和俄语,D,会讲日语和汉语,E,会讲德语和意大利语,F,会讲法语、日语和俄语,G,会讲法语和德语.,问：能否将他们沿圆桌安排就坐成一圈,使得每个人都能与两旁的人交谈?,解：,作无向图,每人是一个顶点,2人之间有边,他们有共同的语言.,ACEGFDBA,是一条哈密顿回路，按此顺序就坐即可.,A,B,C,D,E,F,G,2025/10/27 周一,30,15.2.4,应用举例,例,2,货郎担问题（旅行商问题）,（,T,raveling,S,alesman,P,roblem,）,：,问题描述：,问题抽象：,可以用结点表示城市，城市间的交通路线用边表示，而城市间的交通线路距离可用附加于边的权表示。,这样，上述问题可以归结为寻找一条权的总和为最短的哈密尔顿回路的问题。,2025/10/27 周一,31,15.2.4,应用举例,分析,穷举法,近似算法,