代数结构与图论15章.ppt

1,第十五章 欧拉图与哈密顿图,主要内容欧拉图哈密顿图带权图与货郎担问题,2,15.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时如下证明：,6,PLAY,从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图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.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.可用归纳法证定理15.5.,9,例题,例1 设G是欧拉图，但G不是平凡图，也不是一个环，则(G)2.证 只需证明G中不可能有桥（如何证明？）,上图中，(1),(2)两图都是欧拉图，均从A点出发，如何一次成功地走出一条欧拉回路来？,(1)(2),10,Fleury算法,算法：(1)任取v0V(G)，令P0=v0.(2)设Pi=v0e1v1e2eivi 已经行遍，按下面方法从 E(G)e1,e2,ei 中选取ei+1：(a)ei+1与vi 相关联；(b)除非无别的边可供行遍，否则ei+1不应该为 Gi=Ge1,e2,ei 中的桥.(3)当(2)不能再进行时，算法停止.可以证明算法停止时所得简单通路 Pm=v0e1v1e2emvm(vm=v0)为G 中一条欧拉回路.用Fleury算法走出上一页图(1),(2)从A出发（其实从任何一点出发都可以）的欧拉回路各一条.,11,15.2 哈密顿图,历史背景：哈密顿周游世界问题与哈密顿图,(1)(2),12,哈密顿图与半哈密顿图,定义15.2(1)哈密顿通路经过图中所有顶点一次仅一次的通路.(2)哈密顿回路经过图中所有顶点一次仅一次的回路.(3)哈密顿图具有哈密顿回路的图.(4)半哈密顿图具有哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上,13,实例,在上图中，(1),(2)是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图，也不是半哈密顿图，为什么？,14,无向哈密顿图的一个必要条件,定理15.6 设无向图G=是哈密顿图，对于任意V1V且V1，均有 p(GV1)|V1|,证 设C为G中一条哈密顿回路(1)p(CV1)|V1|(2)p(GV1)p(CV1)|V1|（因为CG）,推论 设无向图G=是半哈密顿图，对于任意的V1V且V1均有 p(GV1)|V1|+1,证 令 uv为G中哈密顿通路，令G=G(u,v)，则G为哈密顿图.于是 p(GV1)=p(GV1(u,v)|V1|+1,15,几点说明,定理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)=v1v2vl 为G中极大路径.若l=n,证毕.(3)否则，证G 中存在过上所有顶点的圈C，由(1)知C外顶点存在与C上某顶点相邻顶点，从而得比更长的路径，重复(2)(3)，最后得G中哈密顿通路.,17,证明,证（着重关键步骤）(1)由()及简单图的性质，用反证法证明G连通.(2)=v1v2vl 为极大路径，l n,若l=n（结束）.下面讨论ln的情况，即要证G中存在过上所有顶点的圈.若(v1,vl)在G中，则(u,v)为G中圈,否则，设v1与上 相邻，则k2(否则由极大路径端点性质及()，会得到d(v1)+d(vl)1+l2n1)，又vl 至少与 左边相邻顶点之一相邻(写出理由)，设 与vl相邻，见图中(1)，于是得G中回路C(1)中图去掉边(),18,证明,图(1),图(2),(3)由连通性，可得比 更长的路径（如图(2)所示），对它再扩大路径，重复(2)，最后得哈密顿通路.,19,推论,推论 设G为n(n3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有 d(vi)+d(vj)n（）则G中存在哈密顿回路，从而G为哈密顿图.证明线索：由定理15.7得=v1v2vn 为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）均为哈密顿图.,21,n（n2）阶竞赛图中存在哈密顿通路定理15.9 若D为n（n2）阶竞赛图，则D中具有哈密顿通路证明思路：注意，竞赛图的基图是无向完全图.对n（n2）做归纳.只需观察下面两个图.,无向哈密顿图的充分条件,22,判断某图是否为哈密顿图方法,判断某图是否为哈密顿图至今还是一个难题.总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.1.观察出哈密顿回路.例3 下图(周游世界问题)是哈密顿图易知a b c d e f g h i j k l m n p q r s t a为图中的一条哈密顿回路.注意，此图不满足定理15.7推论条件.,23,2满足定理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)=6 4，由定理15.6可知图中无哈密顿回路.在国际象棋盘上跳马有解，试试看.,25,设GG，称 为G的权，并记作W(G)，即,定义15.3 给定图G=，(G为无向图或有向图)，设W:ER(R为实数集)，对G中任意边e=(vi,vj)(G为有向图时，e=)，设W(e)=wij，称实数wij 为边e上的权，并将wij标注在边e上，称G为带权图，此时常将带权图G记作.,15.3 最短路问题与货郎担问题,26,货郎担问题,设G=为一个n阶完全带权图Kn，各边的权非负，且有的边的权可能为.求G中的一条最短的哈密顿回路，这就是货郎担问题的数学模型.完全带权图Kn（n3）中不同的哈密顿回路数(1)Kn中有(n1)!条不同的哈密顿回路（定义意义下）(2)完全带权图中有(n1)!条不同的哈密顿回路(3)用穷举法解货郎担问题算法的复杂度为(n1)！，当n较大时，计算量惊人地大,27,解 C1=a b c d a,W(C1)=10 C2=a b d c a,W(C2)=11 C3=a c b d a,W(C3)=9可见C3(见图中(2)是最短的，其权为9.,例6 求图中(1)所示带权图K4中最短哈密顿回路.,(1)(2),28,第十五章 习题课,主要内容欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图带权图、货郎担问题基本要求深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解哈密顿图、半哈密顿图的定义.会用哈密顿图的必要条件判断某些图不是哈密顿图.会用充分条件判断某些图是哈密顿图.要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件.,29,1.设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不为桥.,30,2.证明下图不是哈密顿图.(破坏必要条件),方法一.利用定理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|=6 7=|V2|.,方法三.利用可能出现在哈密顿回路上的边至少有n(n为阶数)条这也是哈密顿图的一个必要条件，记为（）.此图中，n=13，m=21.由于h,l,j 均为4度顶点，a,c,e为3度顶点，且它们关联边互不相同.而在哈密顿回路上，每个顶点准确地关联两条边，于是可能用的边至多有21(32+31)=12.这达不到（）的要求.,31,3某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？,解 图是描述事物之间关系的最好的手段之一.做无向图G=,其中 V=v|v为与会者，E=(u,v)|u,vV且u与v有共同语言，且u v.易知G为简单图且vV,d(v)4，于是，u,vV,有d(u)+d(v)8，由定理15.7 的推论可知G为哈密顿图.服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可.,练习 3,由本题想到的：哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.,32,4.距离(公里)如图所示.他如何走行程最短？,练习 4,最短的路为ABCDA，距离为36公里，其余两条各为多少？,