离散数学(第13章)陈瑜.ppt

陈瑜,Email：yu2023/11/16,离散数学,计算机学院,2023/11/16,计算机科学与工程学院,2,第13章 欧拉图与哈密顿图,2023/11/16,计算机科学与工程学院,3,主要内容(1),Euler图及其应用 1)欧拉道路（回路）的定义 2)如何判别欧拉图 3)一个图含有欧拉道路的条件 4)连通有向图G中含有有向欧拉道路和回路的充要条件 5)Fleury算法 6)Euler图的应用(中国邮递员问题算法),2023/11/16,计算机科学与工程学院,4,主要内容(2),哈密顿图及其应用：哈密顿道路（圈）的定义连通图G是哈密顿图的必要条件连通图G是哈密顿图的充分条件连通图G是哈密顿图的充要条件 哈密顿图的应用(推销商问题),2023/11/16,计算机科学与工程学院,5,哥尼斯堡七桥问题,哥尼斯堡城市有一条横贯全城的普雷格尔(Pregel)河，城的各部分用七座桥联接，每逢假日，城中居民进行环城逛游，这样就产生了一个问题：能不能设计一次“遍游”，使得从某地出发对每座跨河桥只走一次，而在遍历了七桥之后却又能回到原地？,2023/11/16,计算机科学与工程学院,6,Euler图,定义13-1.1设G是一个无孤立结点的图，包含G的每条边的简单道路（回路）称为该图的一条欧拉道路（回路）。具有欧拉回路的图称为欧拉图。规定平凡图为欧拉图。显然，每个欧拉图必然是连通图。,因此，一条欧拉道路（回路）是经过图中每边一次且仅一次的道路（回路）。,为什么？,无重复边,2023/11/16,计算机科学与工程学院,7,Euler图,定义13-1.1设G是一个无孤立结点的图，包含G的每条边的简单道路（回路）称为该图的一条欧拉道路（回路）。具有欧拉回路的图称为欧拉图。规定平凡图为欧拉图。显然，每个欧拉图必然是连通图。,因此，一条欧拉道路（回路）是经过图中每边一次且仅一次的道路（回路）。,为什么？,2023/11/16,计算机科学与工程学院,8,Euler图,定义13-1.1设G是一个无孤立结点的图，包含G的每条边的简单道路（回路）称为该图的一条欧拉道路（回路）。具有欧拉回路的图称为欧拉图。规定平凡图为欧拉图。显然，每个欧拉图必然是连通图。,因此，一条欧拉道路（回路）是经过图中每边一次且仅一次的道路（回路）。,为什么？,2023/11/16,计算机科学与工程学院,9,例13.1,图a是欧拉图；图b不是欧拉图，但存在欧拉道路；图c不存在欧拉道路。,2023/11/16,计算机科学与工程学院,10,定理13-1.1 无向连通图G是欧拉图当且仅当G的所有结点的度数都为偶数。,证明：“”设G是Euler图，则G必然存在一条包含所有边（也包含所有结点）的回路C，对uV，u必然在C中出现一次（可出现多次），每出现u一次，都关联着G中的两条边，而当u又重复出现时，它又关联着G中的另外的两条边，（为什么？）因而u每出现一次，都将使得结点u的度数增加2度，若u在通路中重复出现j次，则deg(u)2j。即u的度数必为偶数。,2023/11/16,计算机科学与工程学院,11,定理13-1.1 无向连通图G是欧拉图当且仅当G的所有结点的度数都为偶数。,证明：“”设G是Euler图，则G必然存在一条包含所有边（也包含所有结点）的回路C，对uV，u必然在C中出现一次（可出现多次），每出现u一次，都关联着G中的两条边，而当u又重复出现时，它又关联着G中的另外的两条边，（为什么？）因而u每出现一次，都将使得结点u的度数增加2度，若u在通路中重复出现j次，则deg(u)2j。即u的度数必为偶数。,2023/11/16,计算机科学与工程学院,12,定理13-1.1 无向连通图G是欧拉图当且仅当G的所有结点的度数都为偶数。,证明：“”设G是Euler图，则G必然存在一条包含所有边（也包含所有结点）的回路C，对uV，u必然在C中出现一次（可出现多次），每出现u一次，都关联着G中的两条边，而当u又重复出现时，它又关联着G中的另外的两条边，（为什么？）因而u每出现一次，都将使得结点u的度数增加2度，若u在通路中重复出现j次，则deg(u)2j。即u的度数必为偶数。,由于在回路C中边不可能重复出现,2023/11/16,计算机科学与工程学院,13,“”设连通图G的结点的度数都是偶数，则G必含有简单回路（可用归纳法证明）。设C是一条包含G中边最多的简单回路：若C已经包含G中所有的边，则C就是Euler回路，结论成立。若C不能包含G中所有的边，则删边子图 G-E（C）仍然无奇数度结点。,由于G是连通的，C中应至少存在一点v，使G-E（C）中有一条包含v的回路C。（见示意图）,2023/11/16,计算机科学与工程学院,14,“”设连通图G的结点的度数都是偶数，则G必含有简单回路（可用归纳法证明）。设C是一条包含G中边最多的简单回路：若C已经包含G中所有的边，则C就是Euler回路，结论成立。若C不能包含G中所有的边，则删边子图 G-E（C）仍然无奇数度结点。,由于G是连通的，C中应至少存在一点v，使G-E（C）中有一条包含v的回路C。（见示意图）,2023/11/16,计算机科学与工程学院,15,“”设连通图G的结点的度数都是偶数，则G必含有简单回路（可用归纳法证明）。设C是一条包含G中边最多的简单回路：若C已经包含G中所有的边，则C就是Euler回路，结论成立。若C不能包含G中所有的边，则删边子图 G-E（C）仍然无奇数度结点。,由于G是连通的，C中应至少存在一点v，使G-E（C）中有一条包含v的回路C。（见示意图）,2023/11/16,计算机科学与工程学院,16,“”设连通图G的结点的度数都是偶数，则G必含有简单回路（可用归纳法证明）。设C是一条包含G中边最多的简单回路：若C已经包含G中所有的边，则C就是Euler回路，结论成立。若C不能包含G中所有的边，则删边子图 G-E（C）仍然无奇数度结点。,由于G是连通的，C中应至少存在一点v，使G-E（C）中有一条包含v的回路C。（见示意图）,2023/11/16,计算机科学与工程学院,17,这样，就可以构造出一条由C和C组成的G的回路，其包含的边数比C多，与假设矛盾。因此，C必是Euler回路，结论成立。,2023/11/16,计算机科学与工程学院,18,证明：“”设G具有一条Euler通路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。“”：若 G没有奇度数结点，则结论显然成立；若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简单道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。注意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。,推论非平凡连通图G含有欧拉道路当且仅当G仅有零个或者两个奇数度结点。,2023/11/16,计算机科学与工程学院,19,证明：“”设G具有一条Euler通路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。“”：若 G没有奇度数结点，则结论显然成立；若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简单道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。注意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。,推论非平凡连通图G含有欧拉道路当且仅当G仅有零个或者两个奇数度结点。,2023/11/16,计算机科学与工程学院,20,证明：“”设G具有一条Euler通路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。“”：若 G没有奇度数结点，则结论显然成立；若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简单道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。注意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。,推论非平凡连通图G含有欧拉道路当且仅当G仅有零个或者两个奇数度结点。,2023/11/16,计算机科学与工程学院,21,证明：“”设G具有一条Euler通路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。“”：若 G没有奇度数结点，则结论显然成立；若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简单道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。注意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。,推论非平凡连通图G含有欧拉道路当且仅当G仅有零个或者两个奇数度结点。,2023/11/16,计算机科学与工程学院,22,例13.2,由定理13-1.1及推论容易看出：,是欧拉图；不是欧拉图，但存在欧拉道路；既不是欧拉图，也不存在欧拉道路。,2023/11/16,计算机科学与工程学院,23,例13.2,由定理13-1.1及推论容易看出：,是欧拉图；不是欧拉图，但存在欧拉道路；既不是欧拉图，也不存在欧拉道路。,现在，我们是不是已经解决了哥尼斯堡七桥问题？,2023/11/16,计算机科学与工程学院,24,有向图的欧拉道路、欧拉图,定理13-1.2（教材p253）有向连通图G含有有向欧拉道路，当且仅当除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。）有向连通图G含有有向欧拉回路，当且仅当G中的所有结点的入度等于出度。,类似于无向图的讨论，对有向图我们有以下结论：,同样，有向Euler图的结点度数都为偶数；含有有向Euler道路的图仅有零个或者两个奇度数结点。,2023/11/16,计算机科学与工程学院,25,有向图的欧拉道路、欧拉图,定理13-1.2（教材p253）有向连通图G含有有向欧拉道路，当且仅当除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。）有向连通图G含有有向欧拉回路，当且仅当G中的所有结点的入度等于出度。,类似于无向图的讨论，对有向图我们有以下结论：,同样，有向Euler图的结点度数都为偶数；含有有向Euler道路的图仅有零个或者两个奇度数结点。,2023/11/16,计算机科学与工程学院,26,有向图的欧拉道路、欧拉图,定理13-1.2）有向连通图G含有有向欧拉道路，当且仅当除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。）有向连通图G含有有向欧拉回路，当且仅当G中的所有结点的入度等于出度。,类似于无向图的讨论，对有向图我们有以下结论：,同样，有向Euler图的结点度数都为偶数；含有有向Euler道路的图仅有零个或者两个奇度数结点。,2023/11/16,计算机科学与工程学院,27,例13.3,V1,V2,V3,V4,V1,V2,V3,V4,V8,V2,V4,V6,V1,V3,V5,V7,图a)存在一条的欧拉道路：v3v1v2v3v4v1；,(a),(b),(c),图(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b)是欧拉图；,图(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是欧拉图。,2023/11/16,计算机科学与工程学院,28,例13.4,解在图中，仅有两个度数为奇数的结点b，c，因而存在从b到c的欧拉通路，蚂蚁乙走到c只要走一条欧拉通路，边数为9条。而蚂蚁甲要想走完所有的边到达c，至少要先走一条边到达b，再走一条欧拉通路，因而它至少要走10条边才能到达c，所以乙必胜。,甲、乙两只蚂蚁分别位于右图,中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？,2023/11/16,计算机科学与工程学院,29,例13.4,解在图中，仅有两个度数为奇数的结点b，c，因而存在从b到c的欧拉通路，蚂蚁乙走到c只要走一条欧拉通路，边数为9条。而蚂蚁甲要想走完所有的边到达c，至少要先走一条边到达b，再走一条欧拉通路，因而它至少要走10条边才能到达c，所以乙必胜。,甲、乙两只蚂蚁分别位于右图,中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？,2023/11/16,计算机科学与工程学院,30,Fleury算法（构造Euler回路）,设G是一个欧拉图任取v0V，令P0v0；设P0v0e1v1e2eivi，按下面的方法从 GK=E-e1,e2,ei中选取ei+1：ei+1与vi相关联；除非无别的边可选取，否则ei+1不应该为 GkG-e1,e2,ei中的桥；当Gk为零图时，算法结束；否则，返回2。,2023/11/16,计算机科学与工程学院,31,Fleury算法（构造Euler回路）,设G是一个欧拉图任取v0V，令P0v0；设P0v0e1v1e2eivi，按下面的方法从 GK=E-e1,e2,ei中选取ei+1：ei+1与vi相关联；除非无别的边可选取，否则ei+1不应该为 GkG-e1,e2,ei中的桥；当Gk为零图时，算法结束；否则，返回2。,即如果ei+1是割边，同时还有其它边与vi相关联，则不能选ei+1,2023/11/16,计算机科学与工程学院,32,Fleury算法（构造Euler回路）,设G是一个欧拉图任取v0V，令P0v0；设P0v0e1v1e2eivi，按下面的方法从 GK=E-e1,e2,ei中选取ei+1：ei+1与vi相关联；除非无别的边可选取，否则ei+1不应该为 GkG-e1,e2,ei中的桥；当Gk为零图时，算法结束；否则，返回2。,即如果ei+1是割边，同时还有其它边与vi相关联，则不能选ei+1,能不走桥就不走桥！,2023/11/16,计算机科学与工程学院,33,Fleury算法（构造Euler回路）,设G是一个欧拉图任取v0V，令P0v0；设P0v0e1v1e2eivi，按下面的方法从 GK=E-e1,e2,ei中选取ei+1：ei+1与vi相关联；除非无别的边可选取，否则ei+1不应该为 GkG-e1,e2,ei中的桥；当Gk为零图时，算法结束；否则，返回2。,2023/11/16,计算机科学与工程学院,34,例13.5,v4,v5,v6,e4,e5,e6,e10,e9,e8,e3,在右图所示的欧拉图中，某人用算法求中的欧拉回路时，走了简单的回路：v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后，无法行遍了，试分析在哪步他犯了错误？,v1,v3,v7,e1,e2,e7,v,e1,e1,e1,e1,v2,v4,v5,v6,e4,e5,e6,e10,e9,e8,e3,v1,v3,v7,e1,e2,e7,v,e1,e1,e1,e1,v2,此人行遍v8时犯了能不走桥就不走桥的错误，因而未能行遍出欧拉回路。当他走到v8时，e2，e3，e14，e10，e1，e8,见右图，此时，e9为该图中的桥，而e7、e11均不是桥。因此，他不该走e9，而应该走e7或e11。但在行遍v3和v1时，也遇到桥，为什么没有问题呢？,v9,v9,2023/11/16,计算机科学与工程学院,35,中国邮递员问题,山东师范大学，管梅谷先生1962提出并解决。（参考文献：1962（数学通报）81.10,P32,81.5）一个邮递员从邮局出发，在其分管的投递区域内走遍所有的街道把邮件送到每个收件人手中，最后又回到邮局，要走怎样的线路使全程最短。,这个问题用图来表示：街道为图的边，街道交叉口为图的结点，问题就是要从这样一个图中找出一条至少包含每条边一次的总长最短的回路。,2023/11/16,计算机科学与工程学院,36,对此，管梅谷曾证明，若图的边数为m，则所求回路的长度最小是m，最多不超过2m，并且每条边在其中最多出现两次。中国邮递员问题，一般为在带权连通图中找一条包括全部边的且权最小的回路。,这个问题有着有效的解决办法，其中最直观的方法之一是:把图中的某些边复制成两条边，然后在所求图中找一条欧拉回路。中国邮递员问题是运筹学中一个典型的优化问题。,显然，当这个图是欧拉图时，任何一条欧拉回路都符合要求；当这个图不是欧拉图时，所求回路必然要重复通过某些边。,关键是：复制哪些边？,2023/11/16,计算机科学与工程学院,37,算法,（1）若G不含奇数度结点，则任一欧拉回路就是问题的解决。（2）若G含有2K(K0)个奇数度结点，则先求出其中任何两点间的最短路径，然后再在这些路径之中找出K条路径P1，P2，PK，使得满足以下条件：任何Pi和Pj（ij）没有相同的起点和终点。在所满足的K条最短路径的集合中，P1，P2，PK的长度总和最短。（3）根据（2）中求出的K条最短道路P1，P2，PK，在原图G中复制所有出现的在这条道路上的边，设所得之图为G。（4）构造G的欧拉回路，即得中国邮递员问题的解。,找出需复制的边,连通图中，奇数度结点的个数必为偶数个。,2023/11/16,计算机科学与工程学院,38,例13.6,1因为G含有奇数度结点，所以2G中有2K=4(K=2)个奇结点:V1，V2，V3，V5。这4点间的距离:d(V1,V2)=3，d(V1,V3)=5，d(V1,V5)=4，d(V2,V3)=2，d(V2,V5)=3，d(V3,V5)=4各路径:V1V2(3),V3V5(4)7 V1V3(5),V2V5(3)8 V1V5(4),V2V3(2)6两条长度最短P1=V1V7V5,P2=V2V33构造G的任一E图就是中国邮递员问题的解。,G,G,2023/11/16,计算机科学与工程学院,39,Euler图的应用,模数转换问题：设有旋转鼓轮其表面被等分成16个部分，如图1所示。,其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，在图中阴影部分表示导体，空白部分表示绝缘体，根据鼓轮的位置，触点将得到信息1101，如果鼓轮沿顺时针方向旋转一个部分，触点将有信息1010。问鼓轮上16个部分怎样安排导体及绝缘体，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。,图1,2023/11/16,计算机科学与工程学院,40,设有一个八个结点的有向图（图2），其结点分别记为三位二进制数000，001，010，011，100，101，110，111，设ai0，1，从结点a1a2a3可引出两条有向边，其终点分别是a2a30以及a2a31。该两条边分别记为a1a2a30和a1a2a31。,图2,2023/11/16,计算机科学与工程学院,41,按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边标号的头三位数相同。因为图2中16条边被记成不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一条欧拉回路，这16个二进制数可写成对应的二进制数序列。把这个序列排成环状,即与所求的鼓轮相对应。,2023/11/16,计算机科学与工程学院,42,按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边标号的头三位数相同。因为图2中16条边被记成不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一条欧拉回路，这16个二进制数可写成对应的二进制数序列。把这个序列排成环状,即与所求的鼓轮相对应。,2023/11/16,计算机科学与工程学院,43,按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边标号的头三位数相同。因为图2中16条边被记成不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一条欧拉回路，这16个二进制数可写成对应的二进制数序列。把这个序列排成环状,即与所求的鼓轮相对应。,2023/11/16,计算机科学与工程学院,44,习题,P257 2、3、5,2023/11/16,计算机科学与工程学院,45,哈密顿图,周游世界问题,1857（59）年爱尔兰数学家在给他朋友的一封信中，首先谈到关于十二面体的一个数学游戏：将左图中的每个结点看成一个城市，联结两个结点的边看成是交通线，他的问题就是能不能找到旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的出发地?他把这个问题称为周游世界问题。,2023/11/16,计算机科学与工程学院,46,定义13-2.1设G是一个连通图，若G中存在一条包含全部结点的基本道路，则称这条道路为G的哈密顿道路；若G中存在一个包含全部结点的圈，则称这个圈为G的哈密顿圈；含有哈密顿圈的图称为哈密顿图。规定平凡图为哈密顿图。哈密顿道路是经过图中所有结点的道路中长度最短的通路；哈密顿回路是经过图中所有结点的回路中长度最短的回路。,2023/11/16,计算机科学与工程学院,47,定义13-2.1设G是一个连通图，若G中存在一条包含全部结点的基本道路，则称这条道路为G的哈密顿道路；若G中存在一个包含全部结点的圈，则称这个圈为G的哈密顿圈；含有哈密顿圈的图称为哈密顿图。规定平凡图为哈密顿图。哈密顿道路是经过图中所有结点的道路中长度最短的通路；哈密顿回路是经过图中所有结点的回路中长度最短的回路。,2023/11/16,计算机科学与工程学院,48,定义13-2.1设G是一个连通图，若G中存在一条包含全部结点的基本道路，则称这条道路为G的哈密顿道路；若G中存在一个包含全部结点的圈，则称这个圈为G的哈密顿圈；含有哈密顿圈的图称为哈密顿图。规定平凡图为哈密顿图。哈密顿道路是经过图中所有结点的道路中长度最短的通路；哈密顿回路是经过图中所有结点的回路中长度最短的回路。,2023/11/16,计算机科学与工程学院,49,定义13-2.1设G是一个连通图，若G中存在一条包含全部结点的基本道路，则称这条道路为G的哈密顿道路；若G中存在一个包含全部结点的圈，则称这个圈为G的哈密顿圈；含有哈密顿圈的图称为哈密顿图。规定平凡图为哈密顿图。哈密顿道路是经过图中所有结点的道路中长度最短的通路；哈密顿回路是经过图中所有结点的回路中长度最短的回路。,2023/11/16,计算机科学与工程学院,50,例13.7,既存在哈密顿道路，又存在哈密顿回路，即为哈密顿图。,既不存在哈密顿道路，也不存在哈密顿圈。,既存在哈密顿道路，又存在哈密顿圈，即为哈密顿图。,存在哈密顿道路，但不存在哈密顿圈。,2023/11/16,计算机科学与工程学院,51,定理13-2.1,设无向连通图G是哈密顿图，S是V的任意非空真子集，则(G-S)|S|其中(G-S)是从G中删除S后所得到图的连通分支数。证明：设C是G的一个哈密顿圈，则对 S()V，有(C-S)|S|C-S是G-S的一个生成子图(G-S)(C-S)|S|,2023/11/16,计算机科学与工程学院,52,定理13-2.1,设无向连通图G是哈密顿图，S是V的任意非空真子集，则(G-S)|S|其中(G-S)是从G中删除S后所得到图的连通分支数。证明：设C是G的一个哈密顿圈，则对 S()V，有(C-S)|S|C-S是G-S的一个生成子图(G-S)(C-S)|S|,为什么？,2023/11/16,计算机科学与工程学院,53,注意,定理13-2.1在应用中它本身用处不大，但它的逆否命题却非常有用。我们经常利用定理10-6.1的逆否命题来判断某些图不是哈密顿图，即：若存在V的某个非空子集V1使得(G-V1)|V1|，则G不是哈密顿图。例如在右图中取V1=a,c，则(G-V1)4|V1|2，因而该图不是哈密顿图。,定理13-2.1给出的是哈密顿图的必要条件，而不是充分条件。下图所示的彼得森图，对V的任意非空子集V1，均满足(G-V1)|V1|，但它不是哈密顿图。,2023/11/16,计算机科学与工程学院,54,定理13-2.2,设G是具有n个结点的简单图。如果对任意两个结点u,vV，均有deg(u)+deg(v)n-1 则G中存在哈密顿道路。证明：首先证明满足上述条件的G是连通图。否则G至少有两支，即 G1和G2 对v1V1，v2 V2，显然 deg(v1)deg(v2)|V1|-1+|V2|-1=n-2 与已知矛盾，故G是连通的。,2023/11/16,计算机科学与工程学院,55,定理13-2.2,设G是具有n个结点的简单图。如果对任意两个结点u,vV，均有deg(u)+deg(v)n-1 则G中存在哈密顿道路。证明：首先证明满足上述条件的G是连通图。否则G至少有两支，即 G1和G2 对v1V1，v2 V2，显然 deg(v1)deg(v2)|V1|-1+|V2|-1=n-2 与已知矛盾，故G是连通的。,2023/11/16,计算机科学与工程学院,56,定理13-2.2,设G是具有n个结点的简单图。如果对任意两个结点u,vV，均有deg(u)+deg(v)n-1 则G中存在哈密顿道路。证明：首先证明满足上述条件的G是连通图。否则G至少有两支，即 G1和G2 对v1V1，v2 V2，显然 deg(v1)deg(v2)|V1|-1+|V2|-1=n-2 与已知矛盾，故G是连通的。,2023/11/16,计算机科学与工程学院,57,证明(续1),其次，证明G中存在哈密顿道路。设Lv1v2vk为G中最长的一条基本道路，显然kn。,若kn，则L为G中经过所有结点的道路，即为哈密顿道路。若kn，由L的最长性可知，v1和vk的全部邻接点都在L上。若v1vkE，则v1v2vkv1就构成G的一个包含L的圈。若v1vkE，则存在L上的结点vi，使得,Why?,2023/11/16,计算机科学与工程学院,58,证明(续2),v1viE vi-1vkE。（否则，即对viL，v1viE而vi-1vkE。设v1在L上与vi1，vi2，vit相邻（t2），则vk不能与vi1-1,vi2-1,vit-1中的任何一个相邻，这样就有d(vk)k-t-1，d(v1)=t，d(v1)+d(vk)k-1n-1。推出矛盾。）这样就可以构造一个圈 Cv1v2vi-1vkvk-1viv1。,如图所示，这个圈包含了L中的全部结点。,v1,vk,vi,vi-1,vj,vk-1,2023/11/16,计算机科学与工程学院,59,证明(续2),v1viE vi-1vkE。（否则，即对viL，v1viE而vi-1vkE。设v1在L上与vi1，vi2，vit相邻（t2），则vk不能与vi1-1,vi2-1,vit-1中的任何一个相邻，这样就有d(vk)k-t-1，d(v1)=t，d(v1)+d(vk)k-1n-1。推出矛盾。）这样就可以构造一个圈 Cv1v2vi-1vkvk-1viv1。,v1,vk,vi,vi-1,vj,vk-1,如图所示，这个圈包含了L中的全部结点。,2023/11/16,计算机科学与工程学院,60,证明(续2),v1viE vi-1vkE。（否则，即对viL，v1viE而vi-1vkE。设v1在L上与vi1，vi2，vit相邻（t2），则vk不能与vi1-1,vi2-1,vit-1中的任何一个相邻，这样就有d(vk)k-t-1，d(v1)=t，d(v1)+d(vk)k-1n-1。推出矛盾。）这样就可以构造一个圈 Cv1v2vi-1vkvk-1viv1。,v1,vk,vi,vi-1,vj,vk-1,如图所示，这个圈包含了L中的全部结点。,2023/11/16,计算机科学与工程学院,61,证明(续3),这样，对a）和b），都可以构造一个包含L中的全部结点的一个圈C。因为kn，所以V中还有一些结点不在C中，由G的连通性知，存在C外的结点u与C上结点vj相邻。显然，可以构造一条基本道路Puvjvj+1vi-1vkvk-1viv1v2vj-1。P比P长，与L的最长性相矛盾。所以，必然k=n，即L必是G的一条哈密顿道路。由此可以看到，本定理的证明方法是一种构造性证明方法。,v1,vk,vi,vi-1,vj,2023/11/16,计算机科学与工程学院,62,证明(续3),这样，对a）和b），都可以构造一个包含L中的全部结点的一个圈C。因为kn，所以V中还有一些结点不在C中，由G的连通性知，存在C外的结点u与C上结点vj相邻。显然，可以构造一条基本道路Puvjvj+1vi-1vkvk-1viv1v2vj-1。P比P长，与L的最长性相矛盾。所以，必然k=n，即L必是G的一条哈密顿道路。由此可以看到，本定理的证明方法是一种构造性证明方法。,2023/11/16,计算机科学与工程学院,63,证明(续3),这样，对a）和b），都可以构造一个包含L中的全部结点的一个圈C。因为kn，所以V中还有一些结点不在C中，由G的连通性知，存在C外的结点u与C上结点vj相邻。显然，可以构造一条基本道路Puvjvj+1vi-1vkvk-1viv1v2vj-1。P比P长，与L的最长性相矛盾。所以，必然k=n，即L必是G的一条哈密顿道路。由此可以看到，本定理的证明方法是一种构造性证明方法。,2023/11/16,计算机科学与工程学院,64,证明(续3),这样，对a）和b），都可以构造一个包含L中的全部结点的一个圈C。因为kn，所以V中还有一些结点不在C中，由G的连通性知，存在C外的结点u与C上结点vj相邻。显然，可以构造一条基本道路Puvjvj+1vi-1vkvk-1viv1v2vj-1。P比P长，与L的最长性相矛盾。所以，必然k=n，即L必是G的一条哈密顿道路。由此可以看到，本定理的证明方法是一种构造性证明方法。,2023/11/16,计算机科学与工程学院,65,定理13-2.3 设G是具有n个结点（n3）的简单图。如果对任意的两个结点u,vV，均有：deg(u)+deg(v)n，则G必是哈密顿图。证明：利用已知条件，仿照定理13-2.2 中b）的方法，可构造出一个包含所有结点的哈密顿圈。,定理13-2.3给出的是哈密顿图的充分条件，而不是必要条件。在六边形中，任意两个结点的度数之和都是46，但六边形是哈密顿图。,2023/11/16,计算机科学与工程学院,66,定理13-2.3 设G是具有n个结点（n3）的简单图。如果对任意的两个结点u,vV，均有：deg(u)+deg(v)n，则G必是哈密顿图。证明：利用已知条件，仿照定理13-2.2 中b）的方法，可构造出一个包含所有结点的哈密顿圈。(略),定理13-2.3给出的是哈密顿图的充分条件，而不是必要条件。例如，在六边形中，任意两个结点的度数之和都是46，但六边形是哈密顿图。,2023/11/16,计算机科学与工程学院,67,定理13-2.3 设G是具有n个结点（n3）的简单图。如果对任意的两个结点u,vV，均有：deg(u)+deg(v)n，则G必是哈密顿图。证明：利用已知条件，仿照定理13-2.2 中b）的方法，可构造出一个包含所有结点的哈密顿圈。,定理13-2.3给出的是哈密顿图的充分条件，而不是必要条件。例如，在六边形中，任意两个结点的度数之和都是46，但六边形是哈密顿图。,2023/11/16,计算机科学与工程学院,68,例13.8某地有5个风景点，若每个风景点均有两条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？解：将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密顿道路，因此本题有解。,2023/11/16,计算机科学与工程学院,69,例13.8某地有5个风景点，若每个风景点均有两条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？解：将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密顿道路，因此本题有解。,2023/11/16,计算机科学与工程学院,70,例13.9,证明下图(a)所示的图中，不存在哈密顿圈。,证明在图(a)中，删除结点子集V1a,b,c，得到图(b)，在图(b)中，它的连通分支为4，显然有：(G-V1)4|V1|3。由定理13-2.1可知：图(a)所示的图中不会存在哈密顿圈，即不是哈密顿图。,2023/11/16,计算机科学与工程学院,71,例13.10 判断右图所示的图是否存在哈密顿圈。,解：若该图中存在哈密顿圈，则该圈组成的图中任何结点的度数均为2。,因而结点1、2、3、4、5所关联的边均在圈中，于是在结点a、b、c、d、e处均应将不与1、2、3、4、5关联的边删除，而要删除与结点a、b、c、d、e关联的其他边，这样一来，图就不连通了，因而图中不存在哈密顿圈。,2023/11/16,计算机科学与工程学院,72,例13.10 判断右图所示的图是否存在哈密顿圈。,解：若该图中存在哈密顿圈，则该圈组成的图中任何结点的度数均为2。,因而结点1、2、3、4、5所关联的边均在圈中，于是在结点a、b、c、d、e处均应将不与1、2、3、4、5关联的边删除，而要删除与结点a、b、c、d、e关联的其他边，这样一来，图就不连通了，因而图中不存在哈密顿圈。,2023/11/16,计算机科学与工程学院,73,例13.10 判断右图所示的图是否存在哈密顿圈。,解：若该图中存在哈密顿圈，则该圈组成的图中任何结点的度数均为2。,因而结点1、2、3、4、5所关联的边均在圈中，于是在结点a、b、c、d、e处均应将不与1、2、3、4、5关联的边删除，而要删除与结点a、b、c、d、e关联的其他边，这样一来，图就不连通了，因而图中不存在哈密顿圈。,2023/11/16,计算机科学与工程学院,74,图的闭包,定理13-2.3的条件很强，有些图虽然不直接满足这个条件，但可以通过在一定条件下加边的办法来满足这个条件。定义13-2.2 设G是n阶的简单图。若存在一对不相邻的结点u,vV，满足：deg(u)+deg(v)n 则构造图G+uv，并且在图上G+uv重复上述步骤，直至不再存在这样的结点对为止，所得之图称为图G的闭包，记为c(G)。,2023/11/16,计算机科学与工程学院,75,图的闭包,定理13-2.3的条件很强，有些图虽然不直接满足这个条件，但可以通过在一定条件下加边的办法来满足这个条件。定义13-2.2 设G是n阶的简单图。若存在一对不相邻的结点u,vV，满足：deg(u)+deg(v)n 则构造图G+uv，并且在图上G+uv重复上述步骤，直至不再存在这样的结点对为止，所得之图称为图G的闭包，记为c(G)。,2023/11/16,计算机科学与工程学院,76,定理13-2.4 一个简单图G是哈密顿图当且仅当其闭包图是哈密顿图。证明：首先证明，若u