您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 第11章-参考资料:无向哈密顿图的一个充分条件的证明
广东工业大学计算机学院1扩大路径法设G=V,E为n阶无向图,E.设l为G中一条路径.若此路径的始点或终点与通路外的顶点相邻,就将它们扩到通路中,继续这一过程,直到最后得到的通路的两个端点不与通路外的顶点相邻为止.设最后得到的路径为l+k(长度为l的路径扩大成了长度为l+k的路径),称l+k为“极大路径”.称使用此种方法证明问题的方法为“扩大路径法”.有向图中类似讨论,只需注意,在每步扩大中保证有向边方向的一致性.广东工业大学计算机学院2实例由某条路径扩大出的极大路径不惟一,极大路径不一定是图中最长的路径上图中,(1)中实线边所示的长为2的初始路径,(2),(3),(4)中实线边所示的都是由(1)扩展成的极大路径.还能找到另外的极大路径吗?(1)(2)(4)(3)广东工业大学计算机学院3扩大路径法的应用例4设G为n(n3)阶无向简单图,2,证明G中存在长度+1的圈.证明:设=v0v1…vl是由初始路径0用扩大路径法的得到的极大路径,则l.因为v0不与外的顶点相邻,又d(v0),因而在上除v1外,至少还存在1个顶点与v0相邻.设vx是离v0最远的顶点,于是v0v1…vxv0为G中长度+1的圈.广东工业大学计算机学院4无向哈密顿图的一个充分条件1定理15.7设G是n阶无向简单图,若对于任意不相邻的顶点vi,vj,均有d(vi)+d(vj)n1()则G中存在哈密顿通路.证明:(1)首先证明G是连通图反证法。假设G不连通,则G至少有两个连通分支。设G1和G2为阶数是n1和n2的两个连通分支,对uV(G1),vV(G2),有dG(vi)+dG(vj)=dG1(vi)+dG2(vj)≤n1–1+n2–1≤n–2与题设矛盾,所以G是连通图广东工业大学计算机学院5无向哈密顿图的一个充分条件2(续)定理15.7设G是n阶无向简单图,若对于任意不相邻的顶点vi,vj,均有d(vi)+d(vj)n1()则G中存在哈密顿通路.证明:(2)证明G中存在哈密顿通路。①设=v1v2…vl为G中极大路径.若l=n,证毕.②否则要证G中存在过上所有顶点的圈C。由G是连通图知C外顶点存在与C上某顶点相邻顶点,从而得比更长的路径.重复①–②,直至最后得一条哈密顿通路.广东工业大学计算机学院6图(1)证明详解1证明:讨论ln的情况,即要证G中存在过上所有顶点的圈C.①若(v1,vl)在G中,则(v1,vl)为G中满足要求的圈。②否则,设v1与上相邻,则k2否则由极大路径端点性质及G的连通性,会得到d(v1)+d(vl)1+l2n1,又vl至少与的相邻顶点之一相邻否则d(v1)+d(vl)k+l2–(k–1)n1设与vl相邻,见图(1),于是得G中回路C.(1)中图去掉边(),得到一条更长的路径。kiiivvv,...,32kiiivvvv,...,,2121rivrriivv,1广东工业大学计算机学院7证明详解2(3)由于G是连通的,可得比更长的路径。如图(2)所示,由ln可知,存在vl+1V(G)-V(C)与C上某一点vt相邻。当tir–1时,删除(vt-1,vt),得到路径‘=vt-1…v1vir…vlvir-1…vtvl+1比的长度大1.对于tir–1和t=ir的情况也可以构造类似的‘对它再扩大路径,重复②,最后得到哈密顿通路.图(2)l+1t-1t广东工业大学计算机学院8推论推论设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)为哈密顿图.广东工业大学计算机学院9几点说明定理15.7d(vi)+d(vj)n-1是半哈密顿图的充分条件,但不是必要条件.例如:长度为n1(n4)的路径构成的图不满足d(vi)+d(vj)n1条件,但它显然是半哈密顿图.定理15.7的推论d(vi)+d(vj)n同样不是哈密顿图的必要条件。例如:G为长为n的圈,不满足d(vi)+d(vj)n条件,但它当然是哈密顿图.由定理15.7的推论可知,Kn(n3)均为哈密顿图.
本文标题:第11章-参考资料:无向哈密顿图的一个充分条件的证明
链接地址:https://www.777doc.com/doc-1888788 .html