《欧拉图及哈密顿》PPT课件

《《欧拉图及哈密顿》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章第一节欧拉图(1)定义1给定无孤立结点的无向图G,经过图G的每边一次且仅一次的迹为一条欧拉路.经过图G的每边一次且仅一次的回为一条欧拉回路.说明:(1)由定义,含有欧拉路(回)的图显然是连通的;(2)欧拉路是迹(边互不重复),但不是严格意义上的路.定理1连通图G具有欧拉回路当且仅当其每个顶点的度数为偶数.欧拉路(2)证明:必要性:不妨设C是从顶点x1开始的无向图G的一条欧拉回路.对该回路中的任何一个内部点xi而言,每出现一次,其度数必增加2,对x1来讲,回路最后在该点结束,当然其度数也为偶数.充分性:若G是连通无向图,

2、作G的一条最长回C,并假设C不是欧拉回路.这样,在C中必存在xk∈V(C)及关联xk的边e={xk,x1’}C;又deg(x1’)为偶数,所以存在e1={x1’,x2’},e2={x2’,x3’},…,en={xn’,xk’},这样在G中又找到一条回C’,若G=CUC’,则结论成立,反之,继续寻找,总可以找到符合条件的回.第二章欧拉图与哈密顿图(2)定理2连通图G具有欧拉路而无欧拉回路,当且仅当G恰有两个奇数度顶点.证:必要性:设连通图G从顶点a到顶点b有欧拉路C,但不是欧拉回路.在欧拉路C中,除第一边和最后一边外,,每经

3、过G中顶点xi(包括a和b),都为顶点xi贡献2度,而C的第一边为a贡献1度,C的最后一条边为b贡献1度.因此,a和b的度数均为奇数,其余结点度数均为偶数.充分性:设连通图G恰有两个奇数度结点,不妨设为a和b,在图G中添加一条边e={a,b}得G’,则G’的每个结点的度数均为偶数,因而G’中存在欧拉回路,故G中必存在欧拉路.定义2给定有向图D,经过D中每边一次且仅一次的有向迹称为D的有向欧拉路.经过D中每边一次且仅一次的有向闭迹(回),称为有向欧拉回路.第二章欧拉图与哈密顿图(3)定理3具有弱连通性的有向图G具有有向欧拉回路

4、,当且仅当G的每个结点的入度等于出度.具有弱连通性的有向图G具有有向欧拉路,当且仅当在G中,一个结点的入度比出度大1,另一个结点的入度比出度小1,而其余每个结点的入度等于出度.定义3含有欧拉回路的无向连通图与含有向欧拉回路的弱连通有向图,统称为欧拉图.求Euler图的Euler回路的Fleury算法.(1)任意选取一个顶点v0,置W0=v0;(2)假定迹(若是有向图,则是有迹)Wi=v0e1v1…eivi已经选出,则用下列方法从E(G)-{e1,e2,…,ei}中取ei+1;(a)ei+1与vi关联(若是有向图,ei+1以v

5、i为起点)(b)除非没有别的边可选择,ei+1不是Gi=G-{e1,e2,…,ei}的割边.(3)当(2)不能执行时,停止.否则让i+1i,转(2).定理4若G是Euler图,则Fleury算法终止时得到的迹是Euler回路。定义1给定无向图G,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿路.若存在一条闭路经过图G的每个结点一次且仅一次,这条闭路称为哈密顿回路.定义2给定有向图D,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿有向路.若存在一条闭路经过图G的每个结点一次且仅一次,这条有向闭路称为

6、哈密顿有向回路.第二节哈密顿图(1)第二节哈密顿图(1)定义3具有哈密顿回路的无向图与具有哈密顿有向回路的有向图,统称为哈密顿图.例1对于完全图Kn(n3),由于Kn中任意两个顶点之间都有边,从Kn的某一顶点开始,总可以遍历其余节点后,再回到该结点,因而Kn(n3)是哈密顿图.说明:判断一个给定的图是否为哈密顿图,是图论中尚未解决的难题之一,下面介绍若干必要条件和充分条件.第二节哈密顿图(2)定理1设任意n(n3)阶图G,对所有不同非邻接顶点x和y,若deg(x)+deg(y)n,则G是哈密顿图.证明:仅就G是无向图

7、加以证明.假设定理不成立.则存在一个阶为n(n3),满足定理条件且边数最多的非哈密顿图,即G是一个非哈密顿图且对G的任何两个非邻接点x1和x2,图G+边{x1,x2}是哈密顿图.因为n3,所以G不是完全图.设u和v是G的两个顶点.因此G+边{u,v}是哈密顿图.且G+边{u,v}是哈密顿回路一定包含边{u,v}.故在G中存在一条uv路T=u1u2…un(u=u1,v=un)包含G中每个顶点.若{u1,ui}E(G)(2in),则{ui-1,un}E(G).否则u1uiui+1…unui-1ui-2…u1是G的一个

8、哈密顿回路,故对{u2,u3,…,un-1}中每一个邻接到u1的顶点存在一个{u1,u3,…,un-1}中与un不邻接的顶点,故deg(un)n-1-deg(u1),所以deg(u)+deg(v)n-1矛盾.第二节(3)定理2设u和v是n阶图G的不同非邻接点,且deg(u)+deg(v