1、计算机科学学院计算机科学学院 刘芳刘芳2023-5-191第15章 欧拉图和哈密顿图 15.1 欧拉图欧拉图15.2 哈密尔顿图哈密尔顿图计算机科学学院计算机科学学院 刘芳刘芳2023-5-19215.1 欧拉图15.1.1 问题引入问题引入15.1.2 欧拉图欧拉图15.1.3 欧拉图的判定定理欧拉图的判定定理15.1.4 中国邮路问题中国邮路问题计算机科学学院计算机科学学院 刘芳刘芳2023-5-19315.1.1 问题引入哥尼斯堡七桥问题哥尼斯堡七桥问题Seven bridges of Knigsberg problem问题分析问题分析：ACBD计算机科学学院计算机科学学院 刘芳刘芳20
2、23-5-19415.1.2 欧拉图定义定义15.1：设设V，E是连通图是连通图欧拉通路欧拉通路（Euler Path）半欧拉图半欧拉图欧拉回路欧拉回路（Euler Circuit）欧拉图欧拉图 (Eulerian)说明说明规定平凡图是欧拉图；规定平凡图是欧拉图；欧拉通路是简单通路欧拉通路是简单通路,欧拉回路是简单回路；欧拉回路是简单回路；环不影响图的欧拉性。环不影响图的欧拉性。计算机科学学院计算机科学学院 刘芳刘芳2023-5-19515.1.2 欧拉图实例实例 计算机科学学院计算机科学学院 刘芳刘芳2023-5-19615.1.3 欧拉图的判定定理无向欧拉（半欧拉）图的判定定理无向欧拉（半
3、欧拉）图的判定定理定理定理15.1无向图无向图G是欧拉图是欧拉图 G是连通的且无奇度顶点。是连通的且无奇度顶点。定理定理15.2无向图无向图G是半欧拉图是半欧拉图 G是连通的，且是连通的，且G中恰有中恰有2个奇个奇度顶点度顶点计算机科学学院计算机科学学院 刘芳刘芳2023-5-19715.1.3 欧拉图的判定定理例例1：无欧拉通无欧拉通(回回)路路欧拉图欧拉图欧拉图欧拉图半欧拉图半欧拉图半欧拉图半欧拉图无欧拉通无欧拉通(回回)路路计算机科学学院计算机科学学院 刘芳刘芳2023-5-19815.1.3 欧拉图的判定定理例例2：ACBD计算机科学学院计算机科学学院 刘芳刘芳2023-5-19915
4、.1.3 欧拉图的判定定理例例3：一笔画问题及推广：一笔画问题及推广问题描述问题描述问题分析问题分析设图中有设图中有2k个奇度点，个奇度点，若若k 0，可以可以 一笔画成，且起点和终点相同；一笔画成，且起点和终点相同；若若k 1，可以可以 一笔画成，起点和终点恰为图中一笔画成，起点和终点恰为图中的两个奇度点；的两个奇度点；若若k 1，可以可以 k笔画成，每笔的起点和终点恰为笔画成，每笔的起点和终点恰为图中的两个奇度点；图中的两个奇度点；计算机科学学院计算机科学学院 刘芳刘芳2023-5-191015.1.3 欧拉图的判定定理有向欧拉（半欧拉）图的判定定理有向欧拉（半欧拉）图的判定定理定理定理1
5、5.3有向图有向图D是是欧拉图欧拉图 D是强连通且所有顶点的入度等是强连通且所有顶点的入度等于出度。于出度。定理定理15.4有向图有向图D是是半欧拉图半欧拉图 D是单向连通的且是单向连通的且D中恰有两中恰有两个奇度顶点，其中一个顶点的入度比出度大个奇度顶点，其中一个顶点的入度比出度大1,一个顶一个顶点的入度比出度小点的入度比出度小1,其余的顶点的入度等于出度。其余的顶点的入度等于出度。计算机科学学院计算机科学学院 刘芳刘芳2023-5-191115.1.3 欧拉图的判定定理例例1欧拉图欧拉图无欧拉通路无欧拉通路无欧拉通路无欧拉通路半欧拉图半欧拉图 无欧拉通路无欧拉通路半欧拉图半欧拉图计算机科学
6、学院计算机科学学院 刘芳刘芳2023-5-191215.1.3 欧拉图的判定定理例例2：问题描述问题描述计算机鼓轮设计中模数转换计算机鼓轮设计中模数转换问题问题问题分析问题分析ABC10001110计算机科学学院计算机科学学院 刘芳刘芳2023-5-191315.1.4 中国邮路问题 问题描述：问题描述：设有某邮递员为送信，从邮局出发，到所管辖的街道投设有某邮递员为送信，从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一递邮件，最后返回邮局，若必须走遍所辖各街道中每一条最少一次，则怎样选择投递路线使所走的路程最短？条最少一次，则怎样选择投递路线使所走的路程最短？问题抽
7、象：问题抽象：将街区用一个图将街区用一个图G进行表示，上述问题可以用图论的语进行表示，上述问题可以用图论的语言来描述：言来描述：在一个赋权图中，能否找到一条包含每条边最少一次在一个赋权图中，能否找到一条包含每条边最少一次且长度最短回路？且长度最短回路？计算机科学学院计算机科学学院 刘芳刘芳2023-5-191415.1.4 中国邮路问题问题分析问题分析若若G不连通，则无解不连通，则无解否则：否则：若若G是欧拉图，则是欧拉图，则G的欧拉回路就是问题的最优解。的欧拉回路就是问题的最优解。若若G是半欧拉图，且邮局就是其中一个奇度点是半欧拉图，且邮局就是其中一个奇度点问题转化为求问题转化为求G的的欧拉
8、通路欧拉通路和两点的和两点的最短路径最短路径问题。问题。若若G中次数为奇数的结点多于中次数为奇数的结点多于2则回路中必须增加更多的重复边，这时，怎样使则回路中必须增加更多的重复边，这时，怎样使重复边的总长度最小？重复边的总长度最小？计算机科学学院计算机科学学院 刘芳刘芳2023-5-191515.1.4 中国邮路问题例如：例如：计算机科学学院计算机科学学院 刘芳刘芳2023-5-191615.1.4 中国邮路问题判断条件判断条件定理：定理：设设L是图是图G的包含所有边的回路，则的包含所有边的回路，则L具有最小长具有最小长度的充分必要条件是：度的充分必要条件是：每条边最多重复一次；每条边最多重复
9、一次；G的每个回路上，所有重复边的长度之和，不的每个回路上，所有重复边的长度之和，不超过该回路长度的一半。超过该回路长度的一半。计算机科学学院计算机科学学院 刘芳刘芳2023-5-191715.2 Hamilton 图15.2.1 问题引入问题引入15.2.2 Hamilton图的定义图的定义15.2.3 Hamilton图的判定方法图的判定方法15.2.4 应用举例应用举例计算机科学学院计算机科学学院 刘芳刘芳2023-5-191815.2.1 问题引入周游世界问题周游世界问题(W.Hamilton,1859年年)计算机科学学院计算机科学学院 刘芳刘芳2023-5-191915.2.1 问题
10、引入Willam Rowan Hamilton(18051865):计算机科学学院计算机科学学院 刘芳刘芳2023-5-192015.2.2 Hamilton图的定义定义定义15.2：设图设图GV，E哈密顿通路哈密顿通路半哈密顿图半哈密顿图哈密顿回路哈密顿回路哈密顿图哈密顿图说明：说明：规定平凡图是哈密顿图规定平凡图是哈密顿图计算机科学学院计算机科学学院 刘芳刘芳2023-5-192115.2.2 Hamilton图的定义例：判断下图是否为例：判断下图是否为H图？图？计算机科学学院计算机科学学院 刘芳刘芳2023-5-192215.2.3 Hamilton图的判定方法定理定理15.6（必要条件
11、）（必要条件）设设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|成立。成立。计算机科学学院计算机科学学院 刘芳刘芳2023-5-192315.2.3 Hamilton图的判定方法|V1|3，p（
12、G V1）4p（G V1）|V1|不成立，故不成立，故G非非H图。图。GGV1例例1：计算机科学学院计算机科学学院 刘芳刘芳2023-5-192415.2.3 Hamilton图的判定方法例例2：证明下述各图不是哈密顿图证明下述各图不是哈密顿图:(a)(b)推论推论1:1:哈密尔顿图无割点哈密尔顿图无割点.计算机科学学院计算机科学学院 刘芳刘芳2023-5-192515.2.3 Hamilton图的判定方法例例3：证明下述各图不是哈密顿图。证明下述各图不是哈密顿图。计算机科学学院计算机科学学院 刘芳刘芳2023-5-192615.2.3 Hamilton图的判定方法推论推论2：对二部图对二部图
13、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图图。计算机科学学院计算机科学学院 刘芳刘芳2023-5-192715.2.3 Hamilton图的判定方法例例4：证明右图不是哈密顿图证明右图不是哈密顿图证：证：设存在一条哈密顿回路设存在一条哈密顿回路,a,f,g是是2度顶点度顶点,边边(a,c),(f,c)和和(g,c)必在这条哈密顿回路上必在这条哈密顿回路上,从而点从而点c出现出现3次次,与假
14、设矛盾与假设矛盾.故该图不是哈密顿图故该图不是哈密顿图abcde fg计算机科学学院计算机科学学院 刘芳刘芳2023-5-192815.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)nG中存在哈密顿回路，中存在哈密顿回路，G为为哈密
15、顿图哈密顿图;计算机科学学院计算机科学学院 刘芳刘芳2023-5-192915.2.4 应用举例例例1（排座问题）（排座问题）有有7个人个人,A会讲英语会讲英语,B会讲英语和汉语会讲英语和汉语,C会讲英语、意大利会讲英语、意大利语和俄语语和俄语,D会讲日语和汉语会讲日语和汉语,E会讲德语和意大利语会讲德语和意大利语,F会讲会讲法语、日语和俄语法语、日语和俄语,G会讲法语和德语会讲法语和德语.问：能否将他们沿圆桌安排就坐成一圈问：能否将他们沿圆桌安排就坐成一圈,使得每个人都能与使得每个人都能与两旁的人交谈两旁的人交谈?解：解：作无向图作无向图,每人是一个顶点每人是一个顶点,2人之间有边人之间有边
16、他们有共同的语言他们有共同的语言.ACEGFDBA是一条哈密顿回路，按此顺序就坐即可是一条哈密顿回路，按此顺序就坐即可.ABCDEFG计算机科学学院计算机科学学院 刘芳刘芳2023-5-193015.2.4 应用举例例例2 货郎担问题（旅行商问题）货郎担问题（旅行商问题）（Traveling Salesman Problem）：问题描述：问题描述：问题抽象：问题抽象：可以用结点表示城市，城市间的交通路线用边表示，而可以用结点表示城市，城市间的交通路线用边表示，而城市间的交通线路距离可用附加于边的权表示。城市间的交通线路距离可用附加于边的权表示。这样，上述问题可以归结为寻找一条权的总和为最短的这样，上述问题可以归结为寻找一条权的总和为最短的哈密尔顿回路的问题。哈密尔顿回路的问题。计算机科学学院计算机科学学院 刘芳刘芳2023-5-193115.2.4 应用举例分析分析穷举法穷举法近似算法近似算法 dc e a b 141113 812910567
