第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条边的无向图.必要性因G是欧拉图，所以G中存在欧拉回路，设C为G中一条欧拉回路.(1)G连通显然.(2)viV(G)，vi在C上每出现一次获2度，所以vi为偶度顶点.由vi的任意性，结论为真.充分性对边数m做归纳法（第二数学归纳法）.(1)m=1时，G为一个环，则G为欧拉图.(2)设mk（k1）时结论为真，m=k+1时如下证明：6无向欧拉图的判别法（a）制造满足归纳假设的若干个小欧拉图.由连通及无奇度数顶点可知，(G)2，用扩大路径法可得G中长度3的圈C1.删除C1上所有的边（不破坏G中顶点度数的奇偶性）得G的生成子图G，则G无奇度顶点，设它有s（s1）个连通分支G1,G2,…,Gs,它们的边数均k，且无奇度数顶点，由归纳法假设，因而它们都是小欧拉图.设C1,C2,…,Cs是G1,G2,…,Gs的欧拉回路.（b）将C1上被删除的边还原，从C1上某一顶点出发走出G的一条欧拉回路C.例1哥尼斯堡七桥问题4个奇度顶点,不存在欧拉通路,更不存在欧拉回路。7PLAY从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图3.8欧拉图的判别法定理15.2无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.证必要性简单.设G是m条边的n阶无向图，因G是半欧拉图，存在欧拉通回(但不存在欧拉回路)，设为，(1)若v不是的端点，设它在中出现k次，每次获得2度，故d(v)=2k,(2)若v是的端点，由于2个端点是不同的且不相邻，v作为端点只能出现一次，获得1度，它还可能作为非端点出现若干次，每次获得2度，故d(v)为奇数。充分性（利用定理15.1）设u,v为G中的两个奇度顶点，令G=G(u,v)则G连通且无奇度顶点，由定理15.1知G为欧拉图，因而存在欧拉回路C，令=C(u,v)，则为G中欧拉通路.9有向欧拉图的判别法定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.4有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.5G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.可用归纳法证定理15.5.10例题例15.1设G是欧拉图，但G不是平凡图，也不是一个环，则(G)2.证只需证明G中不可能有桥（如何证明？）上图中，(1),(2)两图都是欧拉图，均从A点出发，如何一次成功地走出一条欧拉回路来？(1)(2)11Fleury算法算法：(1)任取v0V(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出发（其实从任何一点出发都可以）的欧拉回路各一条.1215.2哈密顿图历史背景：哈密顿周游世界问题与哈密顿图(1)(2)每个顶点是一个城市,有20个城市,要求从一个城市出发,恰好经过每一个城市一次,回到出发点.13哈密顿图与半哈密顿图定义15.2(1)哈密顿通路——经过图中所有顶点一次仅一次的通路.(2)哈密顿回路——经过图中所有顶点一次仅一次的回路.(3)哈密顿图——具有哈密顿回路的图.(4)半哈密顿图——具有哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上14实例在上图中，(1),(2)是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图，也不是半哈密顿图，为什么？15无向哈密顿图的一个必要条件定理15.6设无向图G=V,E是哈密顿图，对于任意V1V且V1，均有p(GV1)|V1|证设C为G中一条哈密顿回路，当V1中顶点在C上均不相邻时，p(CV1)达到最大值|V1|，而当V1中顶点在C上有彼此相邻的情况时，均有p(CV1)|V1|，从而(1)p(CV1)|V1|而C是G的生成子图，所以(2)p(GV1)p(CV1)|V1|（因为CG）定理15.6中的条件是哈密顿图的必要条件，但不是充分条件（彼得松图）16无向哈密顿图的一个必要条件推论设无向图G=V,E是半哈密顿图，对于任意的V1V且V1均有p(GV1)|V1|+1证令uv为G中哈密顿通路，令G=G(u,v)，则G为哈密顿图.于是p(GV1)=p(GV1(u,v))|V1|+117几点说明由定理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.K2有桥，它显然不是哈密顿图.除K2外，其他有桥的图（连通的）均有割点.其实，本例对非简单连通图也对.18例15.3，为了应用定理15.6及推论，问顶点V1是如何得到的呢？一般地：设二部图G=V1,V2,E,|V1|≤|V2|,且|V1|≥2,|V2|≥2,由定理15.6及其他推论可以得出下面结论：(1)若G是哈密顿图,则|V1|=|V2|,(2)若G半哈密顿图,则|V2|=|V1|+1(3)若|V2|≥|V1|+2,则G不是哈密顿图,也不是半哈密顿图19无向哈密顿图的一个充分条件定理15.7设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有d(vi)+d(vj)n1()则G中存在哈密顿通路.证明线索：(1)由()证G连通(2)=v1v2…vl为G中极大路径.若l=n,证毕.(3)否则，证G中存在过上所有顶点的圈C，由(1)知C外顶点存在与C上某顶点相邻顶点，从而得比更长的路径，重复(2)–(3)，最后得G中哈密顿通路.20证明证（着重关键步骤）(1)由()及简单图的性质，用反证法证明G连通.(2)=v1v2…vl为极大路径，ln,若l=n（结束）.下面讨论ln的情况，即要证G中存在过上所有顶点的圈.①若(v1,vl)在G中，则(u,v)为G中圈②否则，设v1与上相邻，则k2(否则由极大路径端点性质及()，会得到d(v1)+d(vl)1+l2n1)，又vl至少与左边相邻顶点之一相邻(写出理由)，设与vl相邻，见图中(1)，于是得G中回路C((1)中图去掉边())kiiivvv,...,32kiiivvvv,...,,2121rivrriivv,121证明图(1)图(2)(3)由连通性，可得比更长的路径（如图(2)所示），对它再扩大路径，重复(2)，最后得哈密顿通路.22推论推论设G为n(n3)阶无向简单图，若对于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)为哈密顿图.23几点说明定理15.7是半哈密顿图的充分条件，但不是必要条件.长度为n1（n4）的路径构成的图不满足（）条件，但它显然是半哈密顿图.定理15.7的推论同样不是哈密顿图的必要条件，G为长为n的圈，不满足（）条件，但它当然是哈密顿图.由定理15.7的推论可知，Kn（n3）均为哈密顿图.24应用实例例15.4某次国际会议8人参加，他们来自不同的国家。已知他们中任何两人无共同语言的人，与其余有共同语言的人数之和大于或等于8，试证明：能将这8人排在同一张圆桌就座，使得每个人都能与两边的人交谈？解作无向图G=V,E,其中V={v|v为与会者}，E={(u,v)|u,vV,u与v有共同语言,且uv}.G为8阶无向简单图.d(v)为与v有共同语言的人数.根据已知条件,u,vV,有d(u)+d(v)8.由定理15.7的推论，可知G中存在哈密顿回路.服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可.25竞赛图竞赛图:任意两个顶点之间恰好有一条有向边.在循环赛中,n个参赛队中的任意两个队比赛一次,假设没有平局,用有向图描述比赛结果:顶点表示参赛队,A到B有一条边当且仅当A队胜B队.25ABCD26竞赛图(续)定理在n(n≥2)阶有向图D中,如果所有有向边均用无向边代替,所得无向图中含生成子图Kn,则有向图D中存在哈密顿通路.根据定理,竞赛图中一定有哈密顿通路,当然也可能有哈密顿回路.当没有哈密顿回路时,通常只有一条哈密顿通路,这条通路给出参赛队的惟一名次.例如,DABC是一条哈密顿通路,它没有哈密顿回路,比赛结果是D第一,A第二,B第三,C第四.26ABCD27n（n2）阶竞赛图中存在哈密顿通路定理15.9若D为n（n2）阶竞赛图，则D中具有哈密顿通路证明思路：注意，竞赛图的基图是无向完全图.对n（n2）做归纳.只需观察下面两个图.无向哈密顿图的充分条件28证明：设D为n阶竞赛图，当n=2时，D的基图为K2，结论成立。设n=k时成立，现设n=k+1，设V(D)={v1,v2,…,vk,vk+1}.令D1=D-vk+1，易知D1为k阶竞赛图，由归纳法假设，D1存在哈密顿通路1=v'1v'2…v'k,下面证明可以扩到1中去。若存在v'r(1rk)使得v'r,v'k+1E(D),i=1,2,...,r-1.且v'k+1,v'rE(D)，如图(a)所示，则=v'1v'2…vk+1v'r…v'k,为D中哈密顿通路.否则，对任意i{1,2,...,k}，均有v'i,vk+1E(D)，如图(b)所示，则=v'1v'2…v'kv'k+1,为D中哈密顿通路.无向哈密顿图的充分条件29判断某图是否为哈密顿图方法判断某图是否为哈密顿图至今还是一个NP难题.总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.1.观察出哈密顿回路.例15.5下图(周游世界问题)是哈密顿图易知abcdefghijklmnpqrsta为图中的一条哈密顿回路.注意，此图不满足定理15.7推论条件.302．满足定理15.7推论的条件（）.例4完全图Kn(n3)中任何两个顶点u,v，均有d(u)+d(v)=2(n1)n（n3），所以Kn为哈密顿图.3．破坏定理15.6的条件的图不是哈密顿图.例5在四分之一国际象棋盘（4