定理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是半哈密顿图
三、欧拉有向图 下面介绍欧拉有向图。 定义5,23:若连通有向图G中具有一条包 含G中所有弧的有向闭链,则称该闭链为 欧拉有向链称G为欧拉有向图。若连通 有向图G中具有一条包含G中所有弧的有 向开链则称该开链为欧拉有向开链称G 为半欧拉有向图
三、欧拉有向图 下面介绍欧拉有向图。 定义5.23：若连通有向图G中具有一条包 含G中所有弧的有向闭链,则称该闭链为 欧拉有向链,称G为欧拉有向图。若连通 有向图G中具有一条包含G中所有弧的有 向开链,则称该开链为欧拉有向开链,称G 为半欧拉有向图
注意:连通有向图就是指单向连通图。 若G是欧拉有向图则G是强连通的。 Why? 单向连通图则对G中任意两点uy,或者 u到v有有向路,或者v到u有有向路,强 连通就是要证明u和v互相可达。 不妨设u到v有有向路,因为G是欧拉有 向图,所以有u…,u(经过G中所有边的 闭链。 对于v.u的v到u的链,可以证明一定存 在v到u路
注意：连通有向图就是指单向连通图。 若G是欧拉有向图,则G是强连通的。 Why? 单向连通图:则对G中任意两点u,v，或者 u到v有有向路，或者v到u有有向路，强 连通就是要证明u和v互相可达。 不妨设u到v有有向路，因为G是欧拉有 向图,所以有u…v…u(经过G中所有边的 闭链。 对于v…u的v到u的链，可以证明一定存 在v到u路
定理511:设G是连通有向图则G是欧拉 有向图当且仅当G中每个顶点v有d(v=d 定理5.12:设G是连通有向图,则G是半欧 拉有向图当且仅当G中恰有两个奇顶点, 其中一个入度比出度大1,另一个出度比 入度大1,而其它顶点的出度等于入度。 例求由16个二进制数排成的循环序列使 每4位接连数字组成的16个4位二进制子 序列全不相同
定理5.11：设G是连通有向图,则G是欧拉 有向图当且仅当G中每个顶点v有d + (v)=d- (v)。 定理5.12：设G是连通有向图,则G是半欧 拉有向图当且仅当G中恰有两个奇顶点, 其中一个入度比出度大 1,另一个出度比 入度大1,而其它顶点的出度等于入度。 例:求由16个二进制数排成的循环序列,使 每4位接连数字组成的16个4位二进制子 序列全不相同
四、竞赛图与哈密顿有向图 定义525:若有向图G中每两个顶点之间 恰有一条弧,则称G竞赛图。 定义526:若有向图G中存在一条包含G 中所有顶点的有向回路,则称该有向回路 为哈密顿有向回路,称G为哈密顿有向图。 若有向图G中存在一条包含G中所有顶点 的有向路则称该有向路为哈密顿有向路}, 称G为半哈密顿有向图。 显然哈密顿有向图必定是强连通图
四、竞赛图与哈密顿有向图 定义5.25：若有向图G中每两个顶点之间 恰有一条弧, 则称G竞赛图。 定义 5.26：若有向图G中存在一条包含G 中所有顶点的有向回路,则称该有向回路 为哈密顿有向回路,称G为哈密顿有向图。 若有向图G中存在一条包含G中所有顶点 的有向路,则称该有向路为哈密顿有向路}, 称G为半哈密顿有向图。 显然哈密顿有向图必定是强连通图
定理5.16:任何一个竞赛图是半哈密顿 有向图。 证明:采用归纳法 例如n个选手进行网球循环赛,每两个人 都要进行比赛,而且不发生平局现象。由 定理5.16可知这n个选手一定能依次排 出一个优胜次序,然而由于可能存在几条 不同的哈密顿路,所以这种次序可能有 几种
定理 5.16：任何一个竞赛图是半哈密顿 有向图。 证明:采用归纳法 例如n个选手进行网球循环赛, 每两个人 都要进行比赛, 而且不发生平局现象。由 定理 5.16 可知这n个选手一定能依次排 出一个优胜次序, 然而由于可能存在几条 不同的哈密顿路，所以这种次序可能有 几种