您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 离散数学(高教版)第15章.
1第十五章欧拉图与哈密顿图主要内容欧拉图哈密顿图带权图与货郎担问题215.1欧拉图历史背景:哥尼斯堡七桥问题与欧拉图3欧拉图定义定义15.1(1)欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路.(2)欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路.(3)欧拉图——具有欧拉回路的图.(4)半欧拉图——具有欧拉通路而无欧拉回路的图.几点说明:规定平凡图为欧拉图.欧拉通路是生成的简单通路,欧拉回路是生成的简单回路.环不影响图的欧拉性.4上图中,(1),(4)为欧拉图,(2),(5)为半欧拉图,(3),(6)既不是欧拉图,也不是半欧拉图.在(3),(6)中各至少加几条边才能成为欧拉图?欧拉图实例5无向欧拉图的判别法定理15.1无向图G是欧拉图当且仅当G连通且无奇度数顶点.证若G为平凡图无问题.下设G为n阶m条边的无向图.必要性设C为G中一条欧拉回路.(1)G连通显然.(2)viV(G),vi在C上每出现一次获2度,所以vi为偶度顶点.由vi的任意性,结论为真.充分性对边数m做归纳法(第二数学归纳法).(1)m=1时,G为一个环,则G为欧拉图.(2)设mk(k1)时结论为真,m=k+1时如下证明:6PLAY从以上证明不难看出:欧拉图是若干个边不重的圈之并,见示意图3.7欧拉图的判别法定理15.2无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.证必要性简单.充分性(利用定理15.1)设u,v为G中的两个奇度顶点,令G=G(u,v)则G连通且无奇度顶点,由定理15.1知G为欧拉图,因而存在欧拉回路C,令=C(u,v)则为G中欧拉通路.8有向欧拉图的判别法定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.4有向图D是半欧拉图当且仅当D是单向连通的,且D中恰有两个奇度顶点,其中一个的入度比出度大1,另一个的出度比入度大1,而其余顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.5G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.可用归纳法证定理15.5.9例题例1设G是欧拉图,但G不是平凡图,也不是一个环,则(G)2.证只需证明G中不可能有桥(如何证明?)上图中,(1),(2)两图都是欧拉图,均从A点出发,如何一次成功地走出一条欧拉回路来?(1)(2)10Fleury算法算法:(1)任取v0V(G),令P0=v0.(2)设Pi=v0e1v1e2…eivi已经行遍,按下面方法从E(G){e1,e2,…,ei}中选取ei+1:(a)ei+1与vi相关联;(b)除非无别的边可供行遍,否则ei+1不应该为Gi=G{e1,e2,…,ei}中的桥.(3)当(2)不能再进行时,算法停止.可以证明算法停止时所得简单通路Pm=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路.用Fleury算法走出上一页图(1),(2)从A出发(其实从任何一点出发都可以)的欧拉回路各一条.1115.2哈密顿图历史背景:哈密顿周游世界问题与哈密顿图(1)(2)12哈密顿图与半哈密顿图定义15.2(1)哈密顿通路——经过图中所有顶点一次仅一次的通路.(2)哈密顿回路——经过图中所有顶点一次仅一次的回路.(3)哈密顿图——具有哈密顿回路的图.(4)半哈密顿图——具有哈密顿通路且无哈密顿回路的图.几点说明:平凡图是哈密顿图.哈密顿通路是初级通路,哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上13实例在上图中,(1),(2)是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图,也不是半哈密顿图,为什么?14无向哈密顿图的一个必要条件定理15.6设无向图G=V,E是哈密顿图,对于任意V1V且V1,均有p(GV1)|V1|证设C为G中一条哈密顿回路(1)p(CV1)|V1|(2)p(GV1)p(CV1)|V1|(因为CG)推论设无向图G=V,E是半哈密顿图,对于任意的V1V且V1均有p(GV1)|V1|+1证令uv为G中哈密顿通路,令G=G(u,v),则G为哈密顿图.于是p(GV1)=p(GV1(u,v))|V1|+115几点说明定理15.6中的条件是哈密顿图的必要条件,但不是充分条件(彼得松图)由定理15.6立刻可知,Kr,s当sr+1时不是哈密顿图.易知Kr,r(r2)时都是哈密顿图,Kr,r+1都是半哈密顿图.常利用定理15.6判断某些图不是哈密顿图.例2设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证设v为割点,则p(Gv)2|{v}|=1.K2有桥,它显然不是哈密顿图.除K2外,其他有桥的图(连通的)均有割点.其实,本例对非简单连通图也对.16无向哈密顿图的一个充分条件定理15.7设G是n阶无向简单图,若对于任意不相邻的顶点vi,vj,均有d(vi)+d(vj)n1()则G中存在哈密顿通路.证明线索:(1)由()证G连通(2)=v1v2…vl为G中极大路径.若l=n,证毕.(3)否则,证G中存在过上所有顶点的圈C,由(1)知C外顶点存在与C上某顶点相邻顶点,从而得比更长的路径,重复(2)–(3),最后得G中哈密顿通路.17证明证(着重关键步骤)(1)由()及简单图的性质,用反证法证明G连通.(2)=v1v2…vl为极大路径,ln,若l=n(结束).下面讨论ln的情况,即要证G中存在过上所有顶点的圈.①若(v1,vl)在G中,则(u,v)为G中圈②否则,设v1与上相邻,则k2(否则由极大路径端点性质及(),会得到d(v1)+d(vl)1+l2n1),又vl至少与左边相邻顶点之一相邻(写出理由),设与vl相邻,见图中(1),于是得G中回路C((1)中图去掉边())kiiivvv,...,32kiiivvvv,...,,2121rivrriivv,118证明图(1)图(2)(3)由连通性,可得比更长的路径(如图(2)所示),对它再扩大路径,重复(2),最后得哈密顿通路.19推论推论设G为n(n3)阶无向简单图,若对于G中任意两个不相邻的顶点vi,vj,均有d(vi)+d(vj)n()则G中存在哈密顿回路,从而G为哈密顿图.证明线索:由定理15.7得=v1v2…vn为G中哈密顿通路.若(v1,vn)E(G),得证.否则利用()证明存在过v1,v2,…,vn的圈(哈密顿回路).定理15.8设u,v为n阶无向简单图G中两个不相邻的顶点,且d(u)+d(v)n,则G为哈密顿图当且仅当G(u,v)为哈密顿图.20几点说明定理15.7是半哈密顿图的充分条件,但不是必要条件.长度为n1(n4)的路径构成的图不满足()条件,但它显然是半哈密顿图.定理15.7的推论同样不是哈密顿图的必要条件,G为长为n的圈,不满足()条件,但它当然是哈密顿图.由定理15.7的推论可知,Kn(n3)均为哈密顿图.21n(n2)阶竞赛图中存在哈密顿通路定理15.9若D为n(n2)阶竞赛图,则D中具有哈密顿通路证明思路:注意,竞赛图的基图是无向完全图.对n(n2)做归纳.只需观察下面两个图.无向哈密顿图的充分条件22判断某图是否为哈密顿图方法判断某图是否为哈密顿图至今还是一个难题.总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.1.观察出哈密顿回路.例3下图(周游世界问题)是哈密顿图易知abcdefghijklmnpqrsta为图中的一条哈密顿回路.注意,此图不满足定理15.7推论条件.232.满足定理15.7推论的条件().例4完全图Kn(n3)中任何两个顶点u,v,均有d(u)+d(v)=2(n1)n(n3),所以Kn为哈密顿图.3.破坏定理15.6的条件的图不是哈密顿图.例5在四分之一国际象棋盘(44方格组成)上跳马无解.在国际象棋盘上跳马有解.判断某图是否为哈密顿图方法24令V1={a,b,c,d},则p(GV1)=64,由定理15.6可知图中无哈密顿回路.在国际象棋盘上跳马有解,试试看.25设GG,称为G的权,并记作W(G),即)'()(GEeeW)'()()'(GEeewGW定义15.3给定图G=V,E,(G为无向图或有向图),设W:ER(R为实数集),对G中任意边e=(vi,vj)(G为有向图时,e=vi,vj),设W(e)=wij,称实数wij为边e上的权,并将wij标注在边e上,称G为带权图,此时常将带权图G记作V,E,W.15.3最短路问题与货郎担问题26货郎担问题设G=V,E,W为一个n阶完全带权图Kn,各边的权非负,且有的边的权可能为.求G中的一条最短的哈密顿回路,这就是货郎担问题的数学模型.完全带权图Kn(n3)中不同的哈密顿回路数(1)Kn中有(n1)!条不同的哈密顿回路(定义意义下)(2)完全带权图中有(n1)!条不同的哈密顿回路(3)用穷举法解货郎担问题算法的复杂度为(n1)!,当n较大时,计算量惊人地大27解C1=abcda,W(C1)=10C2=abdca,W(C2)=11C3=acbda,W(C3)=9可见C3(见图中(2))是最短的,其权为9.例6求图中(1)所示带权图K4中最短哈密顿回路.(1)(2)28第十五章习题课主要内容欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图带权图、货郎担问题基本要求深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解哈密顿图、半哈密顿图的定义.会用哈密顿图的必要条件判断某些图不是哈密顿图.会用充分条件判断某些图是哈密顿图.要特别注意的是,不能将必要条件当作充分条件,也不要将充分条件当必要条件.291.设G为n(n2)阶无向欧拉图,证明G中无桥(见例1思考题)方法二:反证法.利用欧拉图无奇度顶点及握手定理的推论.否则,设e=(u,v)为G中桥,则Ge产生两个连通分支G1,G2,不妨设u在G1中,v在G2中.由于从G中删除e时,只改变u,v的度数(各减1),因而G1与G2中均只含一个奇度顶点,这与握手定理推论矛盾.练习1方法一:直接证明法.命题(*):设C为任意简单回路,e为C上任意一条边,则Ce连通.证设C为G中一条欧拉回路,任意的eE(C),可知Ce是Ge的子图,由()知Ce连通,所以e不为桥.302.证明下图不是哈密顿图.(破坏必要条件)方法一.利用定理15.6,取V1={a,c,e,h,j,l},则p(GV1)=7|V1|=6练习2方法二.G为二部图,互补顶点子集V1={a,c,e,h,j,l},V2={b,d,f,g,i,k,m},|V1|=67=|V2|.方法三.利用可能出现在哈密顿回路上的边至少有n(n为阶数)条——这也是哈密顿图的一个必要条件,记为().此图中,n=13,m=21.由于h,l,j均为4度顶点,a,c,e为3度顶点,且它们关联边互不相同.而在哈密顿回路上,每个顶点准确地关联两条边,于是可能用的边至多有21(32+31)=12.这达不到()的要求.313.某次国际会议8人参加,已知每人至少与其余7人中的4人有共同语言,问服务员能否将他们安排在同一张圆桌就座,使得每个人都与两边的人交谈?解图是描述事物之间关系的最好的手段之一.做无向图G=V,E,其中V={v|v为与会者},E={(u,v)|u,vV且u与v有共同语言,且uv}.易知G为简单图且vV,d(v)4,于是,u,vV,有d(u)+d(v)8,由定理15.7的推论可知G为哈密顿图.服务员在G中找一条哈密顿回路C,按C中相邻关系安排座位即可.练习3由本题想到的:哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.324.距离(公里)如图所示.他如何走行程最短?练习4最短的路为ABCDA,距离为36公里
本文标题:离散数学(高教版)第15章.
链接地址:https://www.777doc.com/doc-2149240 .html