收藏 分销(赏)

离散数学第十五章 欧拉图与哈密顿图.ppt

上传人:s4****5z 文档编号:13835175 上传时间:2026-04-22 格式:PPT 页数:32 大小:7.67MB 下载积分:10 金币
下载 相关
离散数学第十五章 欧拉图与哈密顿图.ppt_第1页
第1页 / 共32页
离散数学第十五章 欧拉图与哈密顿图.ppt_第2页
第2页 / 共32页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,*,第十五章 欧拉图与哈密顿图,主要内容,欧拉图,哈密顿图,带权图与货郎担问题,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,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服