欧拉图和汉密尔顿图

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学,Discrete Mathematics,第七章 图论第4讲,7-4 欧拉图和汉密尔顿图,7-4 欧拉图和汉密尔顿图,要求：,1、理解欧拉图、汉密尔顿图的定义。,2、掌握欧拉图的判定方法。,3、会判断一些图不是汉密尔顿图。,4、熟悉一些欧拉图和汉密尔顿图。,学习本节要熟悉如下术语（,9,个）：,欧拉路、,欧拉图、,欧拉回路、,掌握6个定理，1个推论。,单向欧拉路、,单向欧拉回路、,汉密尔顿路、,汉密尔顿回路、,汉密尔顿图、,图的闭包,一、欧拉图,A,B,C,D,1、哥尼斯堡七桥问题,七桥问题等价于在图中求一条回路，此回路经过每条边一次且仅有一次。欧拉在1736年的论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。,2、欧拉图(Euler),（2）,定理7-4,.1,无向图,G,具有一条欧拉路，当且仅当,G,连通，并且有零个或两个奇数度结点。,（1）,定义7-4,.1,如果无孤立结点图,G,上有一条经过,G,的,所有边一次且仅一次,的路径，则称该路径为图,G,的,欧拉路,（,Euler walk,）。如果图,G,上有一条经过,G,边一次且仅一次的的回路，则称该回路为图,G,的,欧拉回路,，具有欧拉回路的图称为,欧拉图,（,Euler graph,）。,先分析无向图：,证明思路：,1)先证必要性,:,G,有欧拉路,G,连通,且（,有0个,或,2个奇数度结点,）,设,G,的欧拉路是点边序列,v,0,e,1,v,1,e,2,e,k,v,k,，其中结点可能重复，但边不重复。因欧拉路经过（所有边,）所有结点，所以图,G,是连通的。,对于任一非端点结点,v,i,，在欧拉路中每当,v,i,出现一次，必关联两条边，故,v,i,虽可重复出现，但是,deg,(,v,i,)必是偶数。对于端点,若,v,0,=v,k,，则,deg,(,v,0,)必是偶数，即,G,中无奇数度结点。若,v,0,v,k,，则,deg,(,v,0,)必是奇数，,deg,(,v,k,)必是奇数,即,G,中有两个奇数度结点。,必要性证毕。,2)再证充分性,:(证明过程给出了一种构造方法),G,连通,且（,有0个,或,2个奇数度结点,）,G,有欧拉路,(1),若有 2个奇数度结点,则从其中一个结点开始构造一条迹,即从,v,0,出发经关联边,e,1,进入,v,1,若,deg,(,v,1,)为偶数,则必可由,v,1,再经关联边,e,2,进入,v,2,如此下去,每边仅取一次,由于,G,是连通的,故必可到达另一奇数度结点停下,得到一条迹,L,1,:,v,0,e,1,v,1,e,2,e,k,v,k,。若,G,中没有奇数度结点,则从任一结点,v,0,出发,用上述方法必可回到结点,v,0,得到一条闭迹。,(2),若,L,1,通过了,G,的所有边,L,1,就是一条欧拉路。,(3),若,G,中去掉,L,1,后得到子图,G,则,G,中每个结点度数都为偶数,因为原来的图,G,是连通的,故,L,1,与,G,至少有一个结点,v,i,重合,在,G,中由,v,i,出发重复,(1),的方法,得到闭迹,L,2,。,(4),当,L,1,与,L,2,组合,若恰是,G,得欧拉路,否则重复,(3),可得闭迹,L,3,依此类推可得一条欧拉路。,充分性证毕,上述定理与推论可作为欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到deg(A)5，deg(B)deg(C)deg(D)=3，故欧拉回路必不存在。,（3）,定理7-4,.1,的推论,无向图,G,具有一条欧拉回路，当且仅当,G,连通且所有结点度数皆为偶数。,（4）一笔画问题,要判定一个图G是否可一笔画出，有两种情况：一是从图G中某一结点出发，经过图G的每一边一次仅一次到达另一结点。另一种就是从G的某个结点出发，经过G的每一边一次仅一次再回到该结点。上述两种情况分别可以由欧拉路和欧拉回路的判定条件予以解决。,见303页图7-4.3,(a)为欧拉路，有从v,2,到v,3,的一笔画。,(b)为欧拉回路，可以从任一结点出发，一笔画回到原出发点。,练习:,311页（1）,(1)判定下图中的图形是否能一笔画。,解：完全图K,n,每个结点的度数为n-1，要使n-1为偶数，必须n为奇数。故当n为奇数时，完全图K,n,有欧拉回路。,练习,311页,(3),(3)确定n取怎样的值，完全图K,n,有一条欧拉回路。,（5）,定义7-4.2,给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。,可以将欧拉路和欧拉回路的概念推广到有向图中。,（6）,定理7-4,.2,有向图,G,为具有一条,单向欧拉回路,，当且仅当,G,连通,，并且每个结点的,入度等于出度,。有向图,G,有,单向欧拉路,，当且仅当,G,连通,，并且恰有两个结点的入度与出度不等，,它们中一个的出度比入度多1，另一个入度比出度多1,。,证明思路与,定理7-4,.1,类似,应用：街道清扫车问题,小区大门,2,1,例1 有向欧拉图应用示例：,计算机鼓轮的设计,。,鼓轮表面分成,2,4,=16,等份，其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，在下图中阴影部分表示导体，空白体部分表示绝缘体，根据鼓轮的位置，触点将得到信息,4,个触点,a,b,c,d,读出,1101,(状态图中的边,e,13,),转一角度后将读出1010(边,e,10,)。,问鼓轮上16个部分怎样安排导体及绝缘体才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,0,a,b,c,d,设有一个八个结点的有向图，如下图所示。其结点分别记为三位二进制数000，001，111，,设,a,i,0,1，从结点,a,1,a,2,a,3,可引出两条有向边，其终点分别是,a,2,a,3,0以及,a,2,a,3,1。该两条边分别记为,a,1,a,2,a,3,0和,a,1,a,2,a,3,1。,按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是,a,1,a,2,a,3,a,4,和,a,2,a,3,a,4,a,5,的形式，即是第一条边标号的后三位数与第二条边的头三位数相同。,由于图中16条边被记为不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路。,010,101,110,100,011,001,111,000,e,10,=1010,e,13,=1101,e,5,=0101,e,3,=0011,e,11,=1011,e,6,=0110,e,7,=0111,e,14,=1110,e,15,=1111,e,12,=1100,e,2,=0010,e,4,=0100,e,1,=0001,e,8,=1000,e,9,=1001,e,0,=0000,a,1,a,2,a,3,(=000)0,a,1,a,2,a,3,(=000)1,a,1,a,2,a,3,(=001)1,a,1,a,2,a,3,(=100)0,a,1,a,2,a,3,(=111)0,a,1,a,2,a,3,(=111)1,a,1,a,2,a,3,(=110)0,a,1,a,2,a,3,(=011)1,所求的欧拉回路为：,e,0,e,1,e,2,e,4,e,9,e,3,e,6,e,13,e,10,e,5,e,11,e,7,e,15,e,14,e,12,e,8,(e,0,),（从图示位置开始）,e,13,e,10,e,5,e,11,e,7,e,15,e,14,e,12,e,8,e,0,e,1,e,2,e,4,e,9,e,3,e,6,(e,13,),所求的二进制序列为：,（从图示位置开始）,上述结论可推广到鼓轮具有,n,个触点的情况。构造,2,n-1,个结点的有向图，每个结点标记为,n-1,位二进制数,从结点,a,1,a,2,a,3,.a,n-1,出发,有一条终点为,a,2,a,3,.a,n-1,0,的边,该边记为,a,1,a,2,a,3,.a,n-1,0,；还有一条终点标记为,a,2,a,3,.a,n-1,1,的边,该边记为,a,1,a,2,a,3,.a,n-1,1,。邻接边的标记规则为：“第一条边后,n-1,位与第二条边前,n-1,位二进制数相同”。,二、汉密尔顿图,（Hamilton）,几个问题,在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱钞？,货郎担问题,旅行商人问题,(TSP),考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，如果教师所担任的课程都不多于四门，则是否存在满足上述要求的考试安排方案？,时间表问题,国际象棋的跳马是否可以遍历其棋盘，即从任一格出发跳到每一格仅一次并最后回到出发的棋盘格子？,在一个至少有,5,人出席的圆桌会议上（会议需要举行多次），为达到充分交流的目的，会议主持者希望每次会议每人两侧的人均与前次不同，这是否可行？请应用图论知识进行论证。,周游世界问题,与欧拉回路类似的是,汉密尔顿回路。它是1859年汉密尔顿首先提出的一个关于12面体的数学游戏：能否在图7-4.6中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题。,周游世界问题,汉密尔顿图,范更华,：,歪打正着学了图论 灵光一闪发现定理,科学中国人（2005）年度人物,汉密尔顿回路问题是图论最古老的研究课题之一，是至今未解决的世界难题，在许多领域有着重要应用。经过多年艰苦攻克，范更华的这一项目在这一问题的研究上开辟 了一条新的途径，证明若图中每对距离为2的点中有一点的度数至少是图的点数的一半，则该图存在哈密尔顿回路。了此成果引发了大量后续工作，以“范定理”、“范 条件”、“范类型”被广泛引用而出现于多种国际权威学术刊物，并作为定理出现在国外的教科书中。,新华网,（1）,定义7-4.3,给定图,G,，,若存在一条路经过图中的每个结点恰好一次，这条路称作,汉密尔顿路,。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作,汉密尔顿回路,。,具有汉密尔顿回路的图称作,汉密尔顿图,。,2、,汉密尔顿,图,图7-4.6存在一条汉密尔顿回路，它是汉密尔顿图,（2）,定理7-4.3,若图,G,具有汉密尔顿回路，则对于结点集,V,的每个非空子集,S,均有,W(G-S)|S|,，其中,W(G-S),是,G-S,的连通分支数。,证明 设C是G的一条汉密尔顿回路，对于V的任何一个非空子集S，在C中删去S中任一结点a,1,，则C-a,1,是连通的非回路，W(C-a,1,)=1，,|S|1，这时,W(C-S),|S|。,若再删去S中另一结点a,2,，则W(C-a,1,-a,2,)2，而,|S|2，这时,W(C-S),|S|。,由归纳法可得：W(C-S),|S|。,同时C-S是G-S的一个生成子图，因而W(G-S)W(C-S)，所以W(G-S),|S|。,C经过图G的每个结点恰好一次，C与G的结点集合是同一个，因此 C-S与G-S的结点集合是同一个。,此定理是必要条件，可以用来证明一个图不是汉密尔顿图。,如右图，取S=v1,v4，则G-S有3个连通分支，,不满足,W(G-S),|S|，,故该,图不是汉密尔顿图。,说明,：此定理是必要条件而不是充分条件。有的图满足此必要条件，但也是,非汉密尔顿图。,彼得森(Petersen)图,例如，著名的彼得森(Petersen)图，,在图中删去任一个结点或任意两个,结点，不能使它不连通；删去3个,结点，最多只能得到有两个连通分支的子图；删去4个结点，只能得到最多三个连通分支的子图；删去5个或