当前位置:文档之家› 第11章-参考资料:无向哈密顿图的一个充分条件的证明

第11章-参考资料:无向哈密顿图的一个充分条件的证明

广东工业大学计算机学院
实例
(1) (2)(3)(4)由某条路径扩大出的极大路径不惟一,极大路径不一定是 图中最长的路径
上图中,(1)中实线边所示的长为2的初始路径,(2), (3), (4) 中实线边所示的都是由(1)扩展成的极大路径.
还能找到另外的极大路径吗?
2
广东工业大学计算机学院
扩大路径法的应用
4
广东工业大学计算机学院
无向哈密顿图的一个充分条件2(续)
定理15.7 设G是n阶无向简单图,若对于任意不相邻的顶点vi, vj,均有 d(vi) + d(vj) n 1 () 则G 中存在哈密顿通路. 证明: (2)证明G中存在哈密顿通路。 ① 设 = v1v2…vl 为G中极大路径. 若l = n, 证毕. ② 否则要证G 中存在过上所有顶点的圈C。由G是连通图知 C外顶点存在与C上某顶点相邻顶点,从而得比 更长的 路径. 重复① – ② ,直至最后得一条哈密顿通路.
扩大路径法
设G = <V, E>为 n 阶无向图,E . 设 l 为G中一条路径. 若此路径的始点或终点与通路外的顶点相邻,就将它们扩到 通路中,继续这一过程,直到最后得到的通路的两个端 点不与通路外的顶点相邻为止. 设最后得到的路径为l+k(长度为 l 的路径扩大成了长度为 l+k 的路径),称l+k为“极大路径”. 称使用此种方法证明问题的方法为“扩大路径法”. 有向图中类似讨论,只需注意,在每步扩大中保证有向边方 向的一致性. 1
对它再扩大路径,重复②,最后得到哈密顿通路.
l+1
t-1
t
图(2)
广东工业大学计算机学院
7
推论
推论 设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)为哈密顿图.
6
广东工业大学计算机学院
证明详解2
(3) 由于G是连通的,可得比 更长的路径。 如图(2) 所示,由 l < n可知,存在vl+1V(G) - V(C)与C上某一 点vt相邻。当t < ir – 1时,删除(vt-1, vt),得到路径 ‘= vt1…v1vir…vlvir-1…vtvl+1比 的长度大1. 对于t > ir – 1和t = ir 的情况也可以构造类似的 ‘
5
广东工业大学计算机学院
证明详解1
证明:讨论l < n的情况,即要证G中存在过上所有顶点的圈C. ① 若(v1, vl)在G中,则 (v1, vl)为G中满足要求的圈。 ② 否则,设v1与上 vi1 v2 , vi2 ,...,vik相邻,则k 2 否则由极大路径端点性质及G的连通性,会得到 d(v1) + d(vl) 1 + l 2 < n 1, v 又vl 至少与 vi2 , vi3 ,... ik 的相邻顶点之一相邻 否则 d(v1) + d(vl) k + l 2 – (k – 1) < n 1 设 vir 1与vl相邻,见图 (1) ,于是得G中回路C. (1)中图去掉边 ( vir 1 , vir ),得到一条更长的路径。 图(1)
3
广东工业大学计算机学院
无向哈密顿图的一个充分条件1
定理15.7 设G是n阶无向简单图,若对于任意不相邻的顶点vi, vj,均有 d(vi) + d(vj) n 1 则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是连通图
例4 设 G 为 n(n3)阶无向简单图, 2,证明G 中存在 长度 +1 的圈.
证明:设 = v0v1…vl 是由初始路径 0 用扩大路径法的得到 的极大路径,则 l .
因为v0 不与 外的顶点相邻,又 d(v0) ,因而在 上除 v1 外,至少还存在 1个顶点与 v0 相邻. 设 vx 是离 v0 最远的顶点,于是 v0v1…vxv0 为 G 中长度 +1 的圈.
9
广东工业大学计算机学院
8
广东工业大学计算机学院
几点说明
定理15.7 d(vi) + d(vj) n - 1是半哈密顿图的充分条件,但 不是必要条件.
例如:长度为n1(n4)的路径构成的图不满足d(vi) + d(vj) n 1条件,但它显然是半哈密顿图.
定理15.7的推论d(vi) + d(vj) n同样不是哈密顿图的必要条 件。 例如:G为长为n的圈,不满足d(vi) + d(vj) n条件,但它 当然是哈密顿图. 由定理15.7的推论可知,Kn(n3)均为哈密顿图.
相关主题