第11章-特殊图PPT学习课件.ppt

主标题,主文本标题,二级标题,三级标题,四级标题,五级标题,电子科技大学离散数学课程组,国家精品课程,110-,*,2,离 散 数 学,电子科技大学,计算机科学与工程学院,示 范 性 软 件 学 院,05 一月 2025,2,第,11,章 特殊图,偶图,3,平面图,4,欧拉图,1,集合的表示方法,2,哈密顿图,2,2,11.0,内容提要,几个特殊图的概念：欧拉图、哈密顿图、偶图、平面图；,欧拉图、哈密顿图、偶图、平面图的判定；,偶图的匹配、图的着色；,欧拉图、哈密顿图、偶图、平面图的应用,2,10.1,本章学习要求,重点掌握,一般掌握,了解,1,1,各个特殊图相关基本概念,2,各个特殊图的性质,3,各个特殊图的判定方法,3,1,各个特殊图的应用,2,图的着色,2,1,哈密顿图、平面图的判断,2,证明方法,2,11.2,欧拉图,11.2.1,欧拉图的引入与定义,A,B,C,D,b,5,b,2,b,1,b,3,b,4,b,7,b,6,B,C,A,D,b,6,b,2,b,5,b,7,b,4,b,1,b,3,2,定义,11.2.1,设,G,是,无孤立结点的图,，若存在一条通路,(,回路,),，,经过图中每边一次且仅一次,，则称此通路,(,回路,),为该图的一条,欧拉通路,(,回路,)(Eulerian Entry/Circuit),。具有欧拉回路的图称为,欧拉图,(Eulerian Graph),。,规定：,平凡图为欧拉图。,以上定义既适合无向图，又适合有向图。,2,欧拉通路和欧拉回路的特征,欧拉通路,是经过,图中所有边,的通路中,长度最短的通路,，即为,通过图中所有边的简单通路,；,欧拉回路,是经过,图中所有边,的回路中,长度最短的回路,，即为,通过图中所有边的简单回路,。,如果仅用边来描述，,欧拉通路和欧拉回路就是图中所有边的一种全排列,。,2,例,11.2.1,判断下面的,6,个图中，是否是欧拉图？是否存在欧拉通路？,v,3,v,1,v,2,v,4,(c),v,3,v,1,v,2,v,4,(a),v,3,v,1,v,2,v,4,(b),v,3,v,1,v,2,v,4,(f),v,3,v,1,v,2,v,4,(d),v,3,v,1,v,2,v,4,(e),欧拉图,欧拉图,不是欧拉图，但存在欧拉通路,不存在欧拉通路,不存在欧拉通路,不是欧拉图，但存在欧拉通路,2,11.2.2,欧拉图的判定,定理,11.2.1,无向图,G=,具有一条欧拉通路，当且仅当,G,是连通的，且仅有零个或两个奇度数结点。,分析,只要找到了，就是存在的。我们具体找一条欧拉通路。对于结点的度数，我们在通路中去计算。,证明,若,G,为平凡图，则定理显然成立。故我们下面讨论的均为非平凡图。,2,必要性：,设,G,具有一条欧拉通路,L=,，则,L,经过,G,中的每条边，由于,G,中无孤立结点，因而,L,经过,G,的所有结点，所以,G,是连通的。,对欧拉通路,L,的任意非端点的结点 ，在,L,中每出现 一次，都关联两条边 和 ，而当 重复出现时，它又关联另外的两条边，由于在通路,L,中边不可能重复出现，因而每出现一次都将使获得,2,度。若在,L,中重复出现,p,次，则,deg()=2p,。,2,若端点 ，设 、在通路中作为非端点分别出现,p1,和,p2,次，则,deg()=2p1+1,，,deg()=2p2+1,因而,G,有两个度数为奇数的结点。,若端点,=,，设在通路中作为非端点出现,p3,次，则,deg()=1+2p3+1=2(p3+1),因而,G,无度数为奇数的结点。,2,充分性：构造性证明。,我们从两个奇度数结点之一开始,(,若无奇度数结点，可从任一结点开始,),构造一条欧拉通路，以每条边最多经过一次的方式通过图中的边。对于度数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以到达另一个奇度数结点而告终,(,若无奇度数结点，则以回到原出发点而告终,),。如果图中所有的边已用这种方式经过了，显然这就是所求的欧拉通路。如果图中不是所有的边都经过了，我们去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶数。,2,因为原来的图是连通的，因此，这个子图必与我们已经过的通路在一个或多个结点相接。从这些结点中的一个开始，我们再通过边构造通路，因为结点的度数全是偶数，因此，这条通路一定最终回到起点。我们将这条回路加到已构造好的通路中间组合成一条通路。如有必要，这一过程重复下去，直到我们得到一条通过图中所有边的通路，即欧拉通路。,由定理,11.2.1,的证明知：,若连通的无向图有两个奇度数结点，则它们是,G,中每条欧拉通路的端点,。,2,结论,推论,11.2.1,无向图,G=,具有一条欧拉回路，当且仅当,G,是连通的，并且所有结点的度数均为偶数。,定理,11.2.2,有向图,G,具有一条欧拉通路，当且仅当,G,是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大,1,，另一个结点的出度比入度大,1,。,推论,11.2.2,有向图,G,具有一条欧拉回路，当且仅当,G,是连通的，且所有结点的入度等于出度。,2,欧拉通路与欧拉回路判别准则,对任意给定的无向连通图，只需通过对图中各结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图；对任意给定的有向连通图，只需通过对图中各结点出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。,利用这项准则，很容易判断出哥尼斯堡七桥问题是无解的，因为它所对应的图中所有,4,个结点的度数均为奇数；也很容易得到例,11.2.1,的结论。,2,定义,11.2.2,设,G=,eE,，如果,p(G-e),p(G),称,e,为,G,的,桥,(Bridge),或,割边,(Cut edge),。,显然，,所有的悬挂边都是桥,。,2,Fleury,算法,算法,11.2.1,求欧拉图,G=,的欧拉回路的,Fleury,算法：,（,1,）任取,v,0,V,，令,P,0,=v,0,，,i=0,；,（,2,）按下面的方法从,E-e,1,e,2,e,i,中选取,e,i+1,：,a.e,i+1,与,v,i,相关联；,b.,除非无别的边可选取，否则,e,i+1,不应该为,G,=G-e,1,e,2,e,i,中的桥；,（,3,）将边,e,i+1,加入通路,P,0,中，令,P,0,=v,0e,1,v,1,e,2,e,i,v,i,e,i+1,v,i+1,，,i=i+1,；,（,4,）如果,i=|E|,，结束，否则转,(2),。,2,例,11.2.2,用,Fleury,算法求欧拉图的一条欧拉回路。,v,1,v,7,v,5,v,3,v,2,v,8,v,4,e,1,e,2,e,3,e,4,e,5,e,6,e,10,e,7,e,8,e,9,e,11,e,12,v,6,分析,求从,v,1,出发，按照,Fleury,算法，每次走一条边，在可能的情况下，不走桥。例如，在得到,P,7,=v,1,e,1,v,2,e,2,v,3,e,3,v,4,e,4,v,5,e,5,v,6,e,6,v,7,e,7,v,8,时，,G,=G-e,1,e,2,e,7,中的,e,8,是桥，因此下一步选择走,e,9,，而不要走,e,8,。,解,从,v,1,出发的一条欧拉回路为：,P,12,=v,1,e,1,v,2,e,2,v,3,e,3,v,4,e,4,v,5,e,5,v,6,e,6,v,7,e,7,v,8,e,9,v,2,e,10,v,4,e,11,v,6,e,12,v,8,e,8,v,1,2,11.2.3,欧拉图的难点,仅有欧拉通路而无欧拉回路的图不是欧拉图；,图中是否存在欧拉通路、欧拉回路图的判定非常简单，只需要数一下图中结点的度数即可；,使用,Fleury,算法求欧拉通路,(,回路,),时，每次走一条边，在可能的情况下，不走桥。,2,11.2.4,欧拉图的应用,1,、一笔画问题,所谓,“,一笔画问题,”,就是画一个图形，笔不离纸，每条边只画一次而不许重复，画完该图。,“,一笔画问题,”,本质上就是一个无向图是否存在欧拉通路,(,回路,),的问题。如果该图为欧拉图，则能够一笔画完该图，并且笔又回到出发点；如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点；如果该图中不存在欧拉通路，则不能一笔画完该图。,2,例,11.2.3,图中的三个图能否一笔画？为什么？,v,1,v,2,v,3,v,4,v,5,(b),v,1,v,2,v,3,v,4,(c),v,1,v,2,v,3,v,4,v,5a),解,因为图,(a),和,(b),中分别有,0,个和,2,个奇度数结点，所以它们分别是欧拉图和存在欧拉通路，因此能够一笔画，并且在,(a),中笔能回到出发点，而,(b),中笔不能回到出发点。图,c,中有,4,个度数为,3,的结点，所以不存在欧拉通路，因此不能一笔画。,2,2,、蚂蚁比赛问题,例,11.2.4,甲、乙两只蚂蚁分别位于图的结点,A,、,B,处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中所有边最后到达结点,C,处。如果它们的速度相同，问谁先到达目的地？,A(,甲,),B,(,乙,),C,解,图中仅有两个度数为奇数的结点,B,、,C,，因而存在从,B,到,C,的欧拉通路，蚂蚁乙走到,C,只要走一条欧拉通路，边数为,9,条，而蚂蚁甲要想走完所有的边到达,C,，至少要先走一条边到达,B,，再走一条欧拉通路，因而它至少要走,10,条边才能到达,C,，所以乙必胜。,2,3,、计算机鼓轮设计,假设一个旋转鼓的表面被等分为,24,个部分，如图所示，其中每一部分分别由导体或绝缘体构成，图中阴影部分表示导体，空白部分表示绝缘体，导体部分给出信号,1,，绝缘体部分给出信号,0,。根据鼓轮转动时所处的位置，,四个触头,A,、,B,、,C,、,D,将获得一定的信息。因此，鼓轮的位置可用二进制信号表示。试问如何选取鼓轮,16,个部分的材料才能使鼓轮每转过一个部分得到一个不同的二进制信号，即每转一周，能得到,0000,到,1111,的,16,个数。,2,问题的等价描述与解决方法,问题的等价描述：,把,16,个二进制数排成一个圆圈，使得四个依次相连的数字所组成的,16,个四位二进制数互不相同。,问题的解决思想：,设,a,i,0,1(i=1,2,3,16),，鼓轮每转一个部分，信号就从,a,1,a,2,a,3,a,4,变为,a,2,a,3,a,4,a,5,，前者的右三位决定了后者的左三位。,我们可把所有三位二进制数作为结点，从每个结点,a,1,a,2,a,3,到,a,2,a,3,a,4,连一条有向边表示,a,1,a,2,a,3,a,4,这个四位二进制数，作出的所有可能的码变换的有向图。,2,所有可能的码变换的有向图,e,0,0000,e,8,1000,e,1,0001,e,9,1001,e,2,0010,e,10,1010,e,3,0011,e,11,1011,e,4,0100,e,12,1100,e,5,0101,e,13,1101,e,6,0110,e,14,1110,e,7,0111,e,15,1111,000,001,100,101,111,010,011,110,e,0,e,1,e,2,e,3,e,7,e,14,e,12,e,8,e,9,e,4,e,5,e,10,e,11,e,13,e,6,e,15,2,问题的求解,问题转化为在这个有向图中找一条欧拉回路。,这个有向图中,8,个结点的出度和入度都是,2,，因此存在欧拉回路。,例如,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,就是一条欧拉回路。根据邻接边的标号记法，这,16,个二进制数的可写成对应的二进制序列,0000100110101111,，把这个序列排成一个圆圈，与所求的鼓轮相对应，就得到鼓轮的设计。,2,推广,存在一个,2,n,个二进制数的循环序列，其中,2,n,个由,n,位二进制数组成的子序列全不相同。,将上述,2,n,个二进制数的循环序列称为,布鲁因,(De Brujin),序列。,2,11.3,哈密顿图,11.2.1,哈密顿的引入与定义,1,2,3,4,5,6,7,20,8,9,10,11,12,13,14,15,16,17,18,19,2,哈密顿图,定义,11.3.1,经过图中,每个结点一次且仅一次,的通路,(,回路,),称为,哈密顿通路,(,回路,)(Hamiltonian Entry/circuit),。存在,哈密顿回路,的图称为,哈密顿图,(Hamiltonian Graph),。,规定：,平凡图为哈密顿图,。,以上定义既适合无向图，又适合有向图。,2,哈密顿通路和哈密顿回路的特征,哈密顿通路是经过图中所有结点的通路中长度最短的通路，即为通过图中所有结点的基本通路；,哈密顿回路是经过图中所有结点的回路中长度最短的回路，即为通过图中所有结点的基本回路。,如果我们仅用结点来描述的话,哈密顿通路就是图中所有结点的一种全排列,哈密顿回路就是图中所有结点的一种全排列再加上该排列中第一个结点的一种排列。,2,例,11.3.1,判断下面的,6,个图中，是否是哈密顿图？是否存在哈密顿通路？,v,3,v,1,v,2,v,4,(a),v,3,v,1,v,2,v,4,(d),v,3,v,1,v,2,v,4,(b),v,5,v,6,v,7,v,2,v,4,v,1,v,5,(c),v,3,v,3,v,1,v,2,v,4,(e),v,3,v,1,v,2,v,4,(f),哈密,顿图,不存在哈密顿通路,不是哈密顿图，但存在哈密顿通路,哈密,顿图,不是哈密顿图，但存在哈密顿通路,不存在哈密顿通路,2,11.3.2,哈密顿图的判定,定理,11.3.1,设无向图,G=,是哈密顿图，,V,1,是,V,的任意非空子集，则,p(G-V,1,)|V,1,|,其中,p(G-V,1,),是从,G,中删除,V,1,后所得到图的连通分支数。,分析,考察,G,的一条哈密顿回路,C,，显然,C,是,G,的生成子图，从而,C-V,1,也是,G-V,1,的生成子图，且有,p(G-V,1,)p(C-V,1,),，故只需要证明,p(C-V,1,)|V,1,|,即可。,2,定理,11.3.1,证明,设,C,是,G,中的一条哈密顿回路，,V,1,是,V,的任意非空子集。下面分两种情况讨论：,（,1,）,V,1,中结点在,C,中均相邻，删除,C,上,V,1,中各结点及关联的边后，,C-V,1,仍是连通的，但已非回路，因此,p(C-V,1,)=1|V,1,|,。,（,2,）,V,1,中结点在,C,上存在,r(2 r|V1|),个互不相邻，删除,C,上,V,1,中各结点及关联的边后，将,C,分为互不相连的,r,段，即,p(C-V,1,)=r|V,1,|,。,一般情况下，,V1,中的结点在,C,中即有相邻的，又有不相邻的，因此总有,p(C-V,1,)|V,1,|,。,又因,C,是,G,的生成子图，从而,C-V1,也是,G-V1,的生成子图，故有,p(G-V,1,)p(C-V,1,)|V,1,|,2,推论,11.3.1,设无向图,G=,中存在哈密顿通路，则对,V,的任意非空子集,V,1,，都有,p(G-V,1,)|V,1,|+1,注意：,定理,11.3.1,给出的是哈密顿图的必要条件，而不是充分条件。,定理,11.3.1,在应用中它本身用处不大，但它的逆否命题却非常有用。我们经常利用定理,11.3.1,的逆否命题来判断某些图不是哈密顿图，即：若存在,V,的某个非空子集,V,1,使得,p(G-V,1,),|V,1,|,，则,G,不是哈密顿图。,v,3,v,1,v,2,v,4,v,5,v,6,v,7,v,2,v,4,v,1,v,5,v,3,2,例,11.3.2,证明图中不存在哈密顿回路。,a,b,c,g,i,h,分析,利用定理,11.3.1,的逆否命题，寻找,V,的某个非空子集,V,1,使得,p(G-V,1,),|V,1,|,，则,G,不是哈密顿图。找到,V,1,=,d,e,f,满足要求。,证明,在图中，删除结点子集,d,e,f,，得新图，它的连通分支为,4,个，由定理,11.3.1,知，该图不是哈密顿图，因而不会存在哈密顿回路。,d,f,e,a,b,c,g,i,h,2,定理,11.3.2,设,G=,是具有,n,个结点的简单无向图。如果对任意两个不相邻的结点,u,vV,，均有,deg(u)+deg(v)n-1,则,G,中存在哈密顿通路。,证明,首先证明满足上述条件的,G,是连通图。用反证法：假设,G,有两个或更多连通分支。设一个连通分支有,n,1,个结点，另一个连通分支有,n,2,个结点。这二个连通分支中分别有两个结点,v,1,、,v,2,。显然，,deg(v,1,)n,1,-1,，,deg(v,2,)n,2,-1,。从而,deg(v,1,)+deg(v,2,)n,1,+n,2,-2 n-2,与已知矛盾，故,G,是连通的。,2,定理,11.3.2,证明,(,续,),其次，证明,G,中存在哈密顿通路。,设,P=v,1,v,2,v,k,为,G,中用,“,延长通路法,得到的,“,极大基本通路,”,，即,P,的始点,v,1,与终点,v,k,不与,P,外的结点相邻，显然,k n,。,（,1,）若,k=n,，则,P,为,G,中经过所有结点的通路，即为哈密顿通路。,（,2,）若,k,n,，说明,G,中还有在,P,外的结点，但此时可以证明存在仅经过,P,上所有结点的基本回路，证明如下：,（,a,）若在,P,上,v,1,与,v,k,相邻，则,v,1,v,2,v,k,v,1,为仅经过,P,上所有结点的基本回路。,2,定理,11.3.2,证明,(,续,),（,b,）若在,P,上,v,1,与,v,k,不相邻，假设,v,1,在,P,上与,v,i,1,=v,2,v,i,2,v,i,3,v,i,j,相邻,(j,必定大于等于,2,，否则,deg(v,1,)+deg(v,k,)1+k-2,n-1),，此时,v,k,必与,v,i,2,v,i,3,v,i,j,相邻的结点,v,i,2,-1,v,i,3,-1,v,i,j,-1,至少之一相邻,(,否则,deg(v,1,)+deg(v,k,)j+k-2-(j-1)=k-1,n-1),。设,v,k,与,v,i,r,-1,(2rj),相邻，如图所示。在,P,中添加边,(v,1,v,i,r,),、,(v,k,v,i,r,-1,),，删除边,(v,i,r,-1,v,i,r,),得基本回路,C=v,1,v,2,v,i,r,-1,v,k,vk-1,v,i,r,v,1,。,v,1,v,i,r,-1,v,i,r,v,k,(a),v,1,v,k,(b),v,k+1,v,t,2,定理,11.3.2,证明,(,续,),（,3,）证明存在比,P,更长的通路。,因为,k,n,，所以,V,中还有一些结点不在,C,中，由,G,的连通性知，存在,C,外的结点与,C,上的结点相邻，不妨设,v,k+1,V-V(C),且与,C,上结点,v,t,相邻，在,C,中删除边,(v,t-1,v,t,),而添加边,(v,t,v,k+1,),得到通路,P,=v,t-1,v,1,v,i,r,v,k,v,i,r,-1,v,t,v,k+1,。显然，,P,比,P,长,1,，且,P,上有,k+1,个不同的结点。,对,P,重复,(1),(3),，得到,G,中的哈密顿通路或比,P,更长的基本通路，由于,G,中结点数目有限，故在有限步内一定得到,G,中的一条哈密顿通路。,2,推论,推论,11.3.2,设,G=,是具有,n,个结点的简单无向图。如果对任意两个不相邻的结点,u,vV,，均有,deg(u)+deg(v)n,则,G,中存在哈密顿回路。,推论,11.3.3,设,G=,是具有,n,个结点的简单无向图，,n3,。如果对任意,vV,，均有,deg(v)n/2,，则,G,是哈密顿图。,需要注意，定理,11.3.2,给出的是哈密顿图的充分条件，而不是必要条件。在六边形中，任两个不相邻的结点的度数之和都是,4,6,，但六边形是哈密顿图。,2,例,11.3.3,某地有,5,个风景点，若每个风景点均有,2,条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这,5,处？,解,将,5,个风景点看成是有,5,个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为,2,，从而任意两个不相邻的结点的度数之和等于,4,，正好为总结点数减,1,。故此图中存在一条哈密顿通路，因此游人可以经过每个风景点恰好一次而游完这,5,处。,2,例,11.3.4,判断下图是否存在哈密顿回路。,5,e,4,1,a,2,b,3,c,d,f,gh,i,j,k,m,n,o,p,5,4,1,2,3,f,g,h,i,j,k,m,n,o,p,5,e,4,1,a,2,b,3,c,d,f,g,h,i,j,k,m,n,o,p,解,方法一,：在图中，删除结点子集,a,b,c,d,e,，得到的图有,7,个连通分支，由定理,11.2.1,知，该图不是哈密顿图，因而不会存在哈密顿回路。,方法二,：若图中存在哈密顿回路，则该回路组成的图中任何结点的度数均为,2,。因而结点,1,、,2,、,3,、,4,、,5,所关联的边均在回路中，于是在结点,a,、,b,、,c,、,d,、,e,处均应将不与,1,、,2,、,3,、,4,、,5,关联的边删除，而要删除与结点a,、,b,、,c,、,d,、,e,关联的其它边，得到右上图，它不是连通图，因而图中不存在哈密顿回路。,2,例,11.3.5,证明下图没有哈密顿通路。,1(A),2(B),8(B),3(A),4(B),5(B),6(B),7(A),证明,任取一结点如,1,用,A,标记，所有与它邻接的结点用,B,标记。继续不断地用,A,标记所有邻接于,B,的结点，用,B,标记所有邻接于,A,的结点，直到所有结点都标记完毕。,如果图中有一条哈密顿通路，那么它必交替通过结点,A,和,B,，故而标记,A,的结点与标记,B,的结点数目或者相同，或者相差,1,个。然而图中有,3,个结点标记为,A,，,5,个结点标记为,B,，它们相差两个，所以该图不存在哈密顿通路。,2,定理,11.3.3,设,G=,是有,n(n2),个结点的一些简单有向图。如果忽略,G,中边的方向所得的无向图中含生成子图,Kn,，则有向图,G,中存在哈密顿通路。,v,2,v,3,v,1,v,4,v,5,在右图中，它所对应的无向图中含完全图,K,5,，由定理,11.3.3,知，图中含有哈密顿通路。事实上，通路,v,3,v,5,v,4,v,2,v,1,为一条哈密顿通路。,2,11.3.3,哈密顿图的难点,仅有哈密顿通路而无哈密顿回路的图不是哈密顿图；,还没有判断图中是否存在欧拉通路、欧拉回路图的简单判定定理，我们只能对结点较少的图凭经验去判定；在哈密顿图中有定理仅是必要条件，此必要条件正方面的叙述无法用来判断一个图是否是哈密顿图，此时该定理是毫无用处的，但必要条件的等价逆叙述却非常的重要，用此逆叙述可以判断一个图不是哈密尔图。,2,11.3.4,哈密顿图的应用,1,、巡回售货员问题,G=,是,n,个结点的赋权完全图，这里,V=v,1,v,2,v,n,是城市的集合，,E,是连接城市的道路的集合，,W,是从,E,到正实数集合的一个函数,(,即,W(v,i,v,j,),是城市,v,i,与,v,j,之间的距离,),，显然对,V,中任意三个城市,v,i,v,j,v,k,，显然它们之间的距离应满足三角不等式：,W(v,i,v,j,)+W(v,j,v,k,)W(v,i,v,k,),，,试求出该赋权图上的最短哈密顿回路。,2,算法,11.3.1,最邻近算法：,以,v,i,为始点，在其余,n-1,个结点中，找出与始点最邻近的结点,v,j,(,如果与,v,i,最邻近的结点不唯一，则任选其中的一个作为,v,j,),，形成具有一条边的通路,v,i,v,j,；,假设,x,是最新加入到这条通路中的结点，从不在通路上的结点中选取一个与,x,最邻近的结点，把连接,x,与此结点的边加到这条通路中。重复这一步，直到,G,中所有结点都包含在通路中；,把始点和最后加入的结点之间的边放入，就得到一条回路。,2,a,b,c,d,e,8,16,7,12,4,例,11.3.6,用最邻近算法计算下图的以,a,为始点的一条近似最短哈密顿回路。,回路的总距离为,47,a,b,c,d,e,5,5,8,8,9,9,16,7,12,4,2,其它结点为始点的哈密顿回路,以,b,为始点的哈密顿回路为：,badecb,，总距离为：,42,。,以,c,为始点的哈密顿回路为：,cbadec,，总距离为：,42,；或,cdaebc,，总距离为：,35,；或,cdabec,，总距离为：,42,。,以,d,为始点的哈密顿回路为：,dabecd,，总距离为：,42,；或,daebcd,，总距离为：,35,。,以,e,为始点的哈密顿回路为：,eadbce,，总距离为：,41,。,2,分析及结论,图中最短哈密顿回路的长度为,35,最长哈密顿回路的长度为,48,。,若以,a,为始点，用最邻近算法求得的哈密顿回路的长度为,47,，几乎达到了最长哈密顿回路的长度。,最邻近算法不是好的算法。可以证明这个算法的误差可以很大。,2,算法,11.3.2,抄近路算法：,求,G,中的一棵最小生成树,T,；,将,T,中各边均加一条与原边权值相同的平行边，设所得图为,G,，显然,G,是欧拉图；,求,G,中的一条欧拉回路,E,；,在,E,中按如下方法求从结点,v,出发的一个哈密顿回路,H,：从,v,出发，沿,E,访问,G,中各个结点，在没有访问完所有结点之前，一旦出现重复出现的结点，就跳过它走到下一个结点，称这种走法为抄近路走法。,W(H),作为最短哈密顿回路的长度,(,设为,d,0,),的近似值。,2,例,11.3.7,用抄近路算法计算下图的以,a,为始点的一条近似最短哈密顿回路。,求一棵最小生成树,T,；,将,T,中各边均加平行边；,求从结点,a,出发的欧拉回路,Ea=aeadabcba,；,求从结点,a,出发按抄近路走法的哈密顿回路,Ha=aedbca,；,W(Ha)=41,。,a,b,c,d,e,5,5,8,8,9,9,16,7,12,4,a,b,c,d,e,5,5,9,4,9,5,5,4,a,b,c,d,e,5,5,9,4,a,b,c,d,e,5,8,9,7,12,2,其它结点为始点的哈密顿回路,求图的一棵最小生成树,T,；,将,T,中各边均加平行边,；,从结点,c,出发的欧拉回路为,E,c,=cbaeadabc,；,从结点,c,出发按抄近路走法的哈密顿回路为,H,c,=cbaedc,；,W(H,c,)=36,。,a,b,c,d,e,5,5,9,4,9,5,5,4,a,b,c,d,e,5,5,9,4,a,b,c,d,e,5,5,8,9,9,2,定理,11.3.4,设赋权完全图,K,n,(n3),满足三角不等式，,d,0,是,K,n,中最短哈密顿回路的长度，,H,是用抄近路算法求出的,K,n,中的哈密顿回路，则,W(H),2d,0,。,2,定理,11.3.4,证明,设T,是,K,n,中的最小生成树，,E,是将,T,中每边加平行边后的图中的欧拉回路，则,W(E)=2W(T),。由欧拉回路,E,产生哈密顿回路,H,时，因为,K,n,满足三角不等式，所以,H,的长度不会比,E,的权大，即,W(H)W(E)=2W(T),。,K,n,中的最短哈密顿回路,H,0,去掉任意一条边就产生的一棵生成树,T,，从而有,W(T)W(T,),d0,因此,2W(T),2d,0,故,W(H),2d,0,2,2,、中国邮路问题,一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢？,如果将这个问题抽象成图论的语言，就是给定一个连通图连通图的每条边的权值为对应的街道的长度,(,距离,),，要在图中求一回路，使得回路的总权值最小。,2,中国邮路问题,若图为欧拉图，只要求出图中的一条欧拉回路即可。否则，邮递员要完成任务就得在某些街道上重复走若干次。,如果重复走一次，就加一条平行边，于是原来对应的图就变成了多重图。只是要求加进的平行边的总权值最小就行了。,问题就转化为：在一个有奇度数结点的赋权连通图中，增加一些平行边，使得新图不含奇度数结点，并且增加的边的总权值最小。,2,解决问题的步骤,要解决上述问题，应分下面两个大步骤。,首先，增加一些边，使得新图无奇度数结点，我们称这一步为,可行方案,(Feasible Scheme),其次，调整可行方案，使其达到增加的边的总权值最小，称这个最后的方案为,最佳方案,(Optimal Scheme),。,2,例,11.3.8,在下图中，确定一条,v,1,从,v,1,到的回路，使它的权值最小。事实上，所确定的回路从任何一个结点出发都可以。,v,1,v,2,v,3,v,4,v,5,v,6,v,7,1,2,1,3,4,1,2,2,3,3,2,第一个可行方案的确定,由于图中奇度数结点为偶数个，所以图中奇度数结点可以配对。又由于图的连通性，每对奇度数结点之间均存在基本通路，在配好对的奇度数结点之间各确定一条基本通路，然后将通路中的所有边均加一条平行边，这样产生的新图中无奇度数结点，因而存在欧拉回路。,图中奇度数结点有,4,个：,v,1,v,3,v,4,v,6,。任意将它们配,2,对：,v,1,与,v,4,配对，,v,3,与,v,6,配对。选,v,1,与,v,4,之间的基本通路为,v,1,v,6,v,5,v,4,，,v,3,与,v,6,之间的基本通路为,v,3,v,7,v,1,v,6,。,每条通路中所含的边均加一条平行边。,2,增加平行边的图如下图所示，它无奇度数结点，因而是欧拉图。,增加的边的总权值为,W(v,3,v,7,)+W(v,7,v,1,)+2,W(v,1,v,6,)+W(v,6,v,5,)+W(v,5,v,4,),=13,。,v,1,v,2,v,3,v,4,v,5,v,6,v,7,1,2,1,3,4,1,2,2,3,3,2,3,3,1,2,2,2,调整可行方案，使增加的边的总数减少,图中边,(v,1,v,6,),的重数为,3,，若去掉两条边，既不影响,v,1,v,6,度数的奇偶性，也不影响图的连通性，因而可去掉两条边。一般情况下，若边的重数大于等于,3,，就去掉偶数条边。于是，有下面结论：,I,）在最优方案中，图中每条边的重数小于等于,2,如果将某条基本回路中的平行边均去掉，而给原来没有平行边的边加上平行边，也不影响图中结点度数的奇偶性。因而，如果在某条基本回路中，平行边的总权值大于该回路的权值的一半，就作上述调整。,2,在图中，回路,v,1,v,2v,3,v,7,v,1,的权值为,6,，而平行边的总权值为,4,，大于,3,，因而应给予调整，调整后的图如右图所示。,我们又有下面的结论：,II,）在最优方案中，图中每个基本回路上平行边的总权值不大于该回路的权值的一半,经过以上调整的图，平行边的总权值为：,W(v,1,v,2,)+W(v,2,v,3,)+W(v,4,v,5,)+W(v,5,v,6,)=5,v,1,v,2,v,3,v,4,v,5,v,6,v,7,1,2,1,3,4,1,2,2,3,3,2,1,2,1,2,判断最佳方案的标准,一个最佳方案是满足,(1),、,(2),的可行方案，反之，一个可行方案若满足,(1),、,(2),两条，它也一定是最佳方案。,因而,I),、,II),是最佳方案的充分必要条件。,右图满足,I),、,II),两条，从而是最佳方案，即图中的任意一条欧拉回路均为邮递员的最佳送信路线。,v,1,v,2,v,3,v,4,v,5,v,6,v,7,1,2,1,3,4,1,2,2,3,3,2,1,2,1,2,11.4,偶图,11.4.1,偶图的定义,定义,11.4.1,若无向图,G=,的结点集,V,能够,划分,为,两个子集,V,1,V,2,，满足,V,1,V,2,=,，且,V,1,V,2,=V,，使得,G,中,任意一条边的两个端点,，,一个属于,V,1,，另一个属于,V,2,，则称,G,为,偶图,(Bipartite Graph),或,二分图,(Bigraph),。,V,1,和,V,2,称为,互补结点子集,，偶图通常记为,G=,。,偶图没有自回路。,平凡图和零图可看成特殊的偶图,。,2,定义,11.4.2,在偶图,G=,中，若,V,1,中的每个结点与,V,2,中的每个结点,都,有且仅有一条边相关联,，则称偶图,G,为,完全偶图,(Complete Bipartite Graph),或,完全二分图,(Complete Bigraph),，记为,K,i,j,，其中，,i=|V,1,|,，,j=|V,2,|,。,2,例,11.4.1,判断图中的几个图，那些是偶图？那些是完全偶图？,v,1,v,2,v,3,v,4,v,5,v,6,v,7,(a),v,6,v,1,v,4,v,3,v,5,v,2,(d),(b),v,1,v,2,v,3,v,4,v,5,(c),v,1,v,2,v,3,v,4,v,5,v,6,v,1,v,4,v,2,v,3,(e),偶图,偶图,偶图,偶图,不是,偶图,完全偶图,K,2,3,完全偶图,K,3,3,完全偶图,K,3,3,2,11.4.2,偶图的判定,定理,11.4.1,无向图,G=,为偶图的充分必要条件是,G,的所有回路的长度均为偶数。,证明,必要性：,设图,G,是偶图,G=,，令,C=v,0,v,1,v,2,v,k,v,0,是,G,的一条回路，其长度为,k+1,。,不失一般性，假设,v,0,V,1,，由偶图的定义知，,v,1,V,2,，,v,2,V,1,。由此可知，,v,2i,V,1,且,v,2i+1,V,2,。,又因为,v,0,V,1,，所以,v,k,V,2,，因而,k,为奇数，故,C,的长度为偶数。,2,充分性：,设,G,中每条回路的长度均为偶数，若,G,是连通图，任选,v,0,V,，定义,V,的两个子集如下：,V,1,=v,i,|d(v,0,v,i,),为偶数,，,V,2,=V-V,1,。,现证明,V,1,中任两结点间无边存在。,假若存在一条边,(v,i,v,j,)E,，其中,v,i,v,j,V,1,，则由,v,0,到,v,i,间的短程线,(,长度为偶数),以及边,(v,i,v,j,),，再加上,v,j,到,v,0,间的短程线,(,长度为偶数,),所组成的回路的长度为奇数，与假设矛盾。,2,充分性：,同理可证,V,2,中任两结点间无边存在。,故,G,中每条边,(v,i,v,j,),，必有,v,i,V,1,，,v,j,V,2,或,v,i,V,2,，,v,j,V,1,，因此,G,是具有互补结点子集,V,1,和,V,2,的偶图。,若,G,中每条回路的长度均为偶数，但,G,不是连通图，则可对,G,的每个连通分支重复上述论证，并可得到同样的结论。,2,定理,11.4.1,的用途,在实际应用中，定理,11.4.1,本身使用不多，我们常使用它的逆否命题来判断一个图不是偶图：,无向图,G,不是偶图的充分必要条件是,G,中存在长度为奇数的回路。,例如下图中存在长度为,3,的回路,v,1,v,2,v,4,v,1,，所以它不是偶图。,v,1,v,4,v,2,v,3,2,11.4.3,匹配,定义,11.4.2,在偶图,G=,中，,V,1,=v,1,v,2,v,q,，若存在,E,的子集,E,=(v,1,v,1,),，,(v,2,v,2,),，,，,(v,q,v,q,),，其中,v,1,v,2,v,q,是,V,2,中的,q,个,不同的结点,，则称,G,的子图,G,=,为从,V,1,到,V,2,的一个,完全匹配,(Complete Matching),，简称