定理5.14若G是n（≥3）个顶点的简单图,对于每一对不相邻的.ppt

《定理5.14若G是n（≥3）个顶点的简单图,对于每一对不相邻的.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、定理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,v1v1,v2,v3,…vn,哈密顿路半哈密顿图不一定是哈密顿图证明:(1)证明对每一对不相邻的顶点u,v,若d(u)+d(v)≥n-1,则G有哈密顿路。1)先证明G是连通的2)再证G有哈密顿路。采用反证法.若G中无哈

2、密顿路，令P(v1,v2,…vl+1)为G中的最长路，长度l

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的完全图是哈密顿图。定理5.15：若G是n个顶点的简单图,对于每一对不相邻的顶点u,v,d(u)+d(v)≥n-1,则G是半哈密顿图。三、欧拉有向图下面介绍欧拉有向图。定义5.23：若连通有向图G中具有一条包含G中所有弧的有向闭链,则称该闭链为欧拉有向链,称G为欧拉有向图。若连通有向图G中具有一条

4、包含G中所有弧的有向开链,则称该开链为欧拉有向开链,称G为半欧拉有向图。注意：连通有向图就是指单向连通图。若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路。定理5.11：设G是连通有向图,则G是欧拉有向图当且仅当G中每个顶点v有d+(v)=d-(v)。定理5.12：设G是连通有向图,则G是半欧拉有向图当且仅当G中恰有两个奇顶点,其中一个入度比出度大1,另一个出度比入

5、度大1,而其它顶点的出度等于入度。例:求由16个二进制数排成的循环序列,使每4位接连数字组成的16个4位二进制子序列全不相同.四、竞赛图与哈密顿有向图定义5.25：若有向图G中每两个顶点之间恰有一条弧,则称G竞赛图。定义5.26：若有向图G中存在一条包含G中所有顶点的有向回路,则称该有向回路为哈密顿有向回路,称G为哈密顿有向图。若有向图G中存在一条包含G中所有顶点的有向路,则称该有向路为哈密顿有向路},称G为半哈密顿有向图。显然哈密顿有向图必定是强连通图。定理5.16：任何一个竞赛图是半哈密顿有向图。证明:采用归纳法例如n个选手进行网球循环赛,每两个人都要进行比赛,而且不发生平局现象。由定理5

6、.16可知这n个选手一定能依次排出一个优胜次序,然而由于可能存在几条不同的哈密顿路，所以这种次序可能有几种。作业:P11535,36,39,40