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