定理5.14:若G是n(≥3)个顶点的简单图 对于每一对不相邻的顶点u,V,满足 d(u)+d(v)≥n,则G是哈密顿图 这里n=8,d(u)=d(V)=3,不相邻,且 d(u)+d(v)=68不满足充分条件, 但却存在哈密顿回路,是哈密顿图 满足定理条件的一定是哈密顿图, 不满足定理条件的也可能是哈密顿 图。 还有要说明的是: 哈密顿图一定是半哈密顿图 哈密顿回路: 1925V3 1 v1V2,V3… vn,哈密顿路 半哈密顿图不一定是哈密顿图
定理5.14：若G是n(≥3)个顶点的简单图, 对于每一对不相邻的顶点 u,v, 满 足 d(u)+d(v)≥n,则G是哈密顿图。 这里n=8,d(u)=d(v)=3,不相邻，且 d(u)+d(v)=6<8,不满足充分条件， 但却存在哈密顿回路，是哈密顿图 满足定理条件的一定是哈密顿图， 不满足定理条件的也可能是哈密顿 图。 还有要说明的是： 哈密顿图一定是半哈密顿图 哈密顿回路：v1 ,v2 ,v3 ,…vn ,v1 v1 ,v2 ,v3 ,…vn , 哈密顿路 半哈密顿图不一定是哈密顿图
证明:(1)证明对每一对不相邻的顶点u,v, 若d(u)+d(v)n-1,则G有哈密顿路。 1)先证明G是连通的 2)再证G有哈密顿路。 采用反证法 若G中无哈密顿路,令P(V1,V2V1)为 G中的最长路,长度kn-1 ①证明G中存在长度为H+1的回路 分v1与vn1相邻和v与v不相邻两种情况 讨论
证明:(1)证明对每一对不相邻的顶点u,v, 若d(u)+d(v)≥n-1,则G有哈密顿路。 1)先证明G是连通的 2)再证G有哈密顿路。 采用反证法. 若G中无哈密顿路，令P(v1 ,v2 ,… vl+1 )为 G中的最长路，长度l<n-1 ① 证明G中存在长度为l+1的回路 分v1与vl+1相邻和v1与vl+1不相邻两种情况 讨论
(iyv1与v1相邻→存在长度为1的回路 (i)v1与v不相邻→存在长度为H1的回路 (a)先证明G中与v相邻的顶点都在路P中, G中与v种相邻的顶点也都在路P中, (b)必存在点v使得在G中v1与v相邻,v;1与 v1相邻 故v1与v不相邻→存在长度为+1的回路 ②若G中存在长度为H1的回路,利用连通性 证明G中必存在长度为H+1的路,矛盾 (2)证明对每一对不相邻的顶点u,w,若 d(u)+d(v)≥n,则G有哈密顿回路
(i)v1与vl+1相邻存在长度为l+1的回路 (ii)v1与vl+1不相邻存在长度为l+1的回路 (a)先证明G中与v1相邻的顶点都在路P中， G中与vl+1相邻的顶点也都在路P中， (b)必存在点vi ,使得在G中v1与vi相邻, vi-1与 vl+1相邻 故v1与vl+1不相邻存在长度为l+1的回路 ②若 G中存在长度为l+1的回路，利用连通性 证明G中必存在长度为l+1的路，矛盾 (2) 证明对每一对不相邻的顶点 u,v, 若 d(u)+d(v)≥n,则G有哈密顿回路
推论:若G是有n(≥3个顶点的简单图, 对于每一个顶点v满足d(v)≥n/2,则G是 哈密顿图。 证明:若G中任意两点都相邻,则有一条 哈密顿回路: 1V2:V3 若G中存在不相邻的点,则对于任意两个 都不相邻的点u,v, 有d(u)+d(V)≥n,由定理5.14知G是哈密 顿图。 显然≥3的完全图是哈密顿图
推论：若G是有n(≥3)个顶点的简单图, 对于每一个顶点v满足d(v)≥n/2,则G是 哈密顿图。 证明：若G中任意两点都相邻，则有一条 哈密顿回路： v1,v2,v3,…vn,v1。 若G中存在不相邻的点，则对于任意两个 都不相邻的点u,v， 有d(u)+d(v)≥n,由定理 5.14知G是哈密 顿图。 显然≥3的完全图是哈密顿图
定理515:若G是n个顶点的简单图对于 每一对不相邻的顶点u,v,d()+d(v)≥n-1,则 G是半哈密顿图
定理5.15：若G是n个顶点的简单图,对于 每一对不相邻的顶点u,v,d(u)+d(v)≥n-1,则 G是半哈密顿图