欧拉图与哈密顿图

单击此处编辑母版标题样式,*,第十五章 欧拉图与哈密顿图,主要内容,欧拉图,哈密顿图,带权图与货郎担问题,1,15.1,欧拉图,历史背景：哥尼斯堡七桥问题与欧拉图,2,欧拉图定义,定义15.1,(1),欧拉通路,经过图中每条边一次且仅一次行遍所有顶点的通路.,(2),欧拉回,路经过图中每条边一次且仅一次行遍所有顶点的回路.,(3),欧拉图,具有欧拉回路的图.,(4),半欧拉图,具有欧拉通路而无欧拉回路的图.,几点说明：,规定平凡图为欧拉图.,欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.,环不影响图的欧拉性.,3,上图中，(1),(4)为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图.在(3),(6)中各至少加几条边才能成为欧拉图？,欧拉图实例,4,无向欧拉图的判别法,定理15.1,无向图,G,是欧拉图当且仅当,G,连通且无奇度数顶点.,证 若,G,为平凡图无问题.下设,G,为,n,阶,m,条边的无向图.,必要性 设,C,为,G,中一条欧拉回路.,(1),G,连通显然.,(2),v,i,V,(,G,)，,v,i,在,C,上每出现一次获2度，所以,v,i,为偶度顶点.,由,v,i,的任意性，结论为真.,充分性 对边数,m,做归纳法（第二数学归纳法）.,(1),m,=1时，,G,为一个环，则,G,为欧拉图.,(2)设,m,k,（,k,1）时结论为真，,m,=,k,+1时如下证明：,5,PLAY,从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图3.,6,欧拉图的判别法,定理15.2,无向图,G,是半欧拉图当且仅当,G,连通且恰有两个奇,度顶点.,证 必要性简单.,充分性（利用定理15.1）,设,u,v,为,G,中的两个奇度顶点，令,G,=,G,(,u,v,),则,G,连通且无奇度顶点，由定理15.1知,G,为欧拉图，因而,存在欧拉回路,C,，令,=,C,(,u,v,),则,为,G,中欧拉通路.,7,有向欧拉图的判别法,定理15.3,有向图,D,是欧拉图当且仅当,D,是强连通的且每个顶,点的入度都等于出度.,本定理的证明类似于定理15.1.,定理15.4,有向图,D,是半欧拉图当且仅当,D,是单向连通的，且,D,中恰有两个奇度顶点，其中一个的入度比出度大1，另一个,的出度比入度大1，而其余顶点的入度都等于出度.,本定理的证明类似于定理15.1.,定理15.5,G,是非平凡的欧拉图当且仅当,G,是连通的且为若干,个边不重的圈之并.,可用归纳法证定理15.5.,8,例题,例1,设,G,是欧拉图，但,G,不是平凡图，也不是一个环，则,(,G,),2.,证 只需证明,G,中不可能有桥（如何证明？）,上图中，,(1),(2)两,图都是欧拉图，均从,A,点出发，如何一次成功地走出一条欧拉回路来？,(1)(2),9,Fleury算法,算法：,(1)任取,v,0,V,(,G,)，令,P,0,=,v,0,.,(2)设,P,i,=,v,0,e,1,v,1,e,2,e,i,v,i,已经行遍，按下面方法从,E,(,G,),e,1,e,2,e,i,中选取,e,i,+1,：,(a),e,i,+1,与,v,i,相关联；,(b)除非无别的边可供行遍，否则,e,i,+1,不应该为,G,i,=,G,e,1,e,2,e,i,中的桥.,(3)当(2)不能再进行时，算法停止.,可以证明算法停止时所得简单通路,P,m,=,v,0,e,1,v,1,e,2,e,m,v,m,(,v,m,=,v,0,)为,G,中一条欧拉回路.,用Fleury算法走出上一页图(1),(2)从,A,出发（其实从任何一点,出发都可以）的欧拉回路各一条.,10,15.2,哈密顿图,历史背景：哈密顿周游世界问题与哈密顿图,(1)(2),11,哈密顿图与半哈密顿图,定义15.2,(1),哈密顿通路,经过图中所有顶点一次仅一次的通路.,(2),哈密顿回路,经过图中所有顶点一次仅一次的回路.,(3),哈密顿图,具有哈密顿回路的图.,(4),半哈密顿图,具有哈密顿通路且无哈密顿回路的图.,几点说明：,平凡图是哈密顿图.,哈密顿通路是初级通路，哈密顿回路是初级回路.,环与平行边不影响哈密顿性.,哈密顿图的实质是能将图中的所有顶点排在同一个圈上,12,实例,在上图中，,(1),(2)是哈密顿图;,(3)是半哈密顿图;,(4)既不是哈密顿图，也不是半哈密顿图，为什么？,13,无向哈密顿图的一个必要条件,定理15.6,设无向图,G,=是哈密顿图，对于任意,V,1,V,且,V,1,，均有,p,(,G,V,1,),|,V,1,|,证 设,C,为,G,中一条哈密顿回路,(1),p,(,C,V,1,),|,V,1,|,(2),p,(,G,V,1,),p,(,C,V,1,),|,V,1,|（因为,C,G,）,推论,设无向图,G,=是半哈密顿图，对于任意的,V,1,V,且,V,1,均有,p,(,G,V,1,),|,V,1,|+1,证 令,uv,为,G,中哈密顿通路，令,G,=,G,(,u,v,)，则,G,为哈密顿图.于是,p,(,G,V,1,)=,p,(,G,V,1,(,u,v,),|,V,1,|+1,14,几点说明,定理,15.6,中的条件是哈密顿图的必要条件，但不是充分条件（彼得松图）,由定理,15.6,立刻可知，,Kr,s,当,s,r,+1,时不是哈密顿图,.,易知,Kr,r,（,r,2,）时都是哈密顿图，,Kr,r,+1,都是半哈密顿图,.,常利用定理,15.6,判断某些图不是哈密顿图,.,例,2,设,G,为,n,阶无向连通简单图，若,G,中有割点或桥，则,G,不,是哈密顿图,.,证 设,v,为割点，则,p,(,G,v,),2|,v,|=1.,K,2,有桥，它显然不是哈密顿图,.,除,K,2,外，其他有桥的图（连通的）均有割点,.,其实，本例对非简单连通图也对,.,15,无向哈密顿图的一个充分条件,定理15.7,设,G,是,n,阶无向简单图，若对于任意不相邻的顶点,v,i,v,j,，均有,d,(,v,i,)+,d,(,v,j,),n,1 (,),则,G,中存在哈密顿通路.,证明线索：,(1)由(,)证,G,连通,(2),=,v,1,v,2,v,l,为,G,中极大路径.若,l,=,n,证毕.,(3)否则，证,G,中存在过,上所有顶点的圈,C,，由(1)知,C,外顶,点存在与,C,上某顶点相邻顶点，从而得比,更长的路径，重,复(2)(3)，最后得,G,中哈密顿通路.,16,证明,证（着重关键步骤）,(1)由(,)及简单图的性质，用反证法证明,G,连通.,(2),=,v,1,v,2,v,l,为极大路径，,l,n,若,l,=,n,（结束）.,下面讨论,ln,的情况，即要证,G,中存在过,上所有顶点的圈.,若(,v,1,v,l,)在,G,中，则,(,u,v,)为,G,中圈,否则，设,v,1,与,上 相邻，则,k,2(,否则由极大路径端点性质及(,),，会得到,d,(,v,1,)+,d,(,v,l,),1+,l,24，由定理15.6可知图中无哈密顿回路.,在国际象棋盘上跳马有解，试试看.,24,设,G,G,，,称,为,G,的权，并记作,W,(,G,),，即,定义15.3,给定图,G,=，(,G,为无向图或有向图)，设,W,:,E,R,(R为实数集)，对,G,中任意边,e,=(,v,i,v,j,),(,G,为有向图,时，,e,=)，设,W,(,e,)=,w,ij,，称实数,w,ij,为边,e,上的,权,，并将,w,ij,标注在边,e,上，称,G,为,带权图,，此时常将带权图,G,记作,.,15.3 最短路问题,与货郎担问题,25,货郎担问题,设,G,=为一个,n,阶完全带权图,K,n,，各边的权非负，且,有的边的权可能为,.求,G,中的一条最短的哈密顿回路，这就,是货郎担问题的数学模型.,完全带权图,K,n,（,n,3）中不同的哈密顿回路数,(1),K,n,中有(,n,1)!条不同的哈密顿回路（定义意义下）,(2)完全带权图中有(,n,1)!条不同的哈密顿回路,(3)用穷举法解货郎担问题算法的复杂度为(,n,1)！，当,n,较大时，计算量惊人地大,26,解,C,1,=,a,b,c,d,a,W,(,C,1,)=10,C,2,=,a,b,d,c,a,W,(,C,2,)=11,C,3,=,a,c,b,d,a,W,(,C,3,)=9,可见,C,3,(见图中(2)是最短的，其权为9.,例6,求图中(1)所示带权图,K,4,中最短哈密顿回路.,(1)(2),27,第十五章 习题课,主要内容,欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法,哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图,带权图、货郎担问题,基本要求,深刻理解欧拉图、半欧拉图的定义及判别定理,深刻理解哈密顿图、半哈密顿图的定义,.,会用哈密顿图的必要条件判断某些图不是哈密顿图,.,会用充分条件判断某些图是哈密顿图,.,要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件,.,28,1.设,G,为,n,（,n,2,）阶无向欧拉图，证明,G,中无桥(见例1思考题),方法二：反证法.利用欧拉图无奇度顶点及握手定理的推论.否则，设,e,=(,u,v,)为,G,中桥，则,G,e,产生两个连通分支,G,1,G,2,，不妨设,u,在,G,1,中，,v,在,G,2,中.由于从,G,中删除,e,时，只改变,u,v,的度数(各减1)，因而,G,1,与,G,2,中均只含一个奇度顶点，这与握手定理推论矛盾.,练习,1,方法一：直接证明法.,命题(*),：设,C,为任意简单回路，,e,为,C,上任意一条边，则,C,e,连通.,证 设,C,为,G,中一条欧拉回路，任意的,e,E,(,C,)，,可知,C,e,是,G,e,的子图，由()知,C,e,连通，所以,e,不为桥.,29,2.,证明下图不是哈密顿图,.(破坏必要条件),方法一.利用定理15.6，,取,V,1,=,a,c,e,h,j,l,，则,p,(,G,V,1,)=7|,V,1,|=6,练习,2,方法二.,G,为二部图，互补顶点子集,V,1,=,a,c,e,h,j,l,V,2,=,b,d,f,g,i,k,m,，,|,V,1,|=6,7=|,V,2,|.,方法三.利用可能出现在哈密顿回路上的边至少有,n,(,n,为阶数),条这也是哈密顿图的一个必要条件，记为（,）.,此图中，,n,=13，,m,=21.由于,h,l,j,均为4度顶点，,a,c,e,为3,度顶点，且它们关联边互不相同.而在哈密顿回路上，,每个顶点准确地关联两条边，于是可能用的边至多有21,(3,2+3,1)=12.这达不到（,）的要求.,30,3某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？,解 图是描述事物之间关系的最好的手段之一.,做无向图,G,=,其中,V,=,v,|,v,为与会者，,E,=(,u,v,)|,u,v,V,且,u,与,v,有共同语言，且,u,v,.,易知,G,为简单图且,v,V,d,(,v,),4,，于是，,u,v,V,有,d,(,u,)+,d,(,v,),8,，由定理15.7 的推论可知,G,为哈密顿图.服务员在,G,中找一条哈密顿回路,C,，按,C,中相邻关系安排座位即可.,练习,3,由本题想到的：哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.,31,4.距离(公里)如图所示.他如何走行程最短？,练习,4,最短的路为,ABCDA,，距离为36公里，其余两条各为多少？,32,