欧拉图及哈密顿图=.ppt

欧拉图 定义1 给定无孤立结点的无向图G,经过图G的 每边一次且仅一次的迹为一条欧拉路.经过图 G的每边一次且仅一次的回为一条欧拉回路. 说明:(1)由定义,含有欧拉路(回)的图显然是 连通的; (2)欧拉路是迹(边互不重复),但不是严格意 义上的路. 定理1 连通图G具有欧拉回路当且仅当其每个 顶点的度数为偶数. 欧拉路 证明:必要性:不妨设C是从顶点x1开始的无向图G 的一条欧拉回路.对该回路中的任何一个内部点xi 而言,每出现一次,其度数必增加2,对x1来讲,回路 最后在该点结束,当然其度数也为偶数. 充分性:若G是连通无向图,作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 连通图G具有欧拉路而无欧拉回路,当且仅当G恰有两个奇数度顶点. 证:必要性:设连通图G从顶点a到顶点b有欧拉路C,但不是欧拉回路.在欧拉路C中,除第一边和最后一边外,每经过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 具有弱连通性的有向图G具有有向欧拉 回路,当且仅当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 以vi为起点) (b)除非没有别的边可选择, ei+1不是 Gi=G- {e1,e2,…,ei}的割边. (3)当(2)不能执行时,停止.否则让i+1 i,转 (2). 哈密顿图 定理4 若G是Euler图,则Fleury算法终止时得到的迹是Euler回路。 哈密顿图 定义3 具有哈密顿回路的无向图与具有哈密顿有向回路的有向图,统称为哈密顿图. 例1对于完全图Kn(n?3),由于Kn中任意两个顶点之间都有边,从Kn的某一顶点开始,总可以遍历其余节点后,再回到该结点,因而Kn(n?3)是哈密顿图. 说明:判断一个给定的图是否为哈密顿图,是图论 中尚未解决的难题之一,下面介绍若干必要条件 和充分条件. 哈密顿图 定理1 设任意n(n?3)阶图G,对所有不同非邻接顶 点x和y,若deg(x)+deg(y) ?n,则G是哈密顿图. 证明:仅就G是无向图加以证明.假设定理不成立. 则存在一个阶为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中存在一 条u-v路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的一个哈密顿回路,故 对{u2,u3,…,un-1}中每一个邻接到u1的顶点存在一 个{u1,u3,…,un-1}中与un不邻接的顶点,故 deg(un) ?n-1-deg(u1),所以deg(u)+deg(v) ?n-1 矛盾. 定理2 设u和v是n阶图G的不同非邻接点,且deg(u) +deg(v)?n,则G+边{u,v}是哈密顿图当且仅当G是哈密顿图. 定义4 给定n阶图G,若将图G度数之和至少是n的非 邻接点用一条边连接起来得图G’,对