《欧拉图与哈密顿图课件》由会员分享,可在线阅读,更多相关《欧拉图与哈密顿图课件(40页珍藏版)》请在金锄头文库上搜索。
1、第15章 欧拉图与哈密顿图,离 散 数 学,本章内容,15.1 欧拉图 15.2 哈密顿图 15.3 带权图与货郎担问题,15.1 欧拉图,历史背景哥尼斯堡七桥问题,欧拉图是一笔画出的边不重复的回路。,欧拉图,定义15.1 通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路,通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图,具有欧拉通路而无欧拉回路的图称为半欧拉图。 说明 欧拉通路是图中经过所有边的简单的生成通路(经过所有顶点的通路称为生成通路)。欧拉回路是经过所有边的简单的生成回路。 规定:平凡图是欧拉图,举例,欧拉图,半欧拉
2、图,无欧拉通路,欧拉图,无欧拉通路,无欧拉通路,无向欧拉图的判定定理,定理15.1 无向图G是欧拉图当且仅当G是连通图,且G中没有奇度顶点。 证明 若G是平凡图,结论显然成立。下面设G为非平凡图,设G是m条边的n阶无向图,并设G的顶点集Vv1,v2,vn。必要性。因为G为欧拉图,所以G中存在欧拉回路,设C为G中任意一条欧拉回路,vi,vjV,vi,vj都在C上,因而vi,vj连通,所以G为连通图。又viV,vi在C上每出现一次获得2度,若出现k次就获得2k度,即d(vi)2k,所以G中无奇度顶点。,定理15.1的证明,充分性。由于G为非平凡的连通图可知,G中边数m1。 对m作归纳法。 (1)m
3、1时,由G的连通性及无奇度顶点可知,G只能是一个环,因而G为欧拉图。 (2)设mk(k1)时结论成立,要证明mk+1时,结论也成立。由G的连通性及无奇度顶点可知,(G)2。无论G是否为简单图,都可以用扩大路径法证明G中必含圈。,定理15.1的证明,设C为G中一个圈,删除C上的全部边,得G的生成子图G , 设G 有s个连通分支G 1,G 2,G s, 每个连通分支至多有k条边,且无奇度顶点, 并且设G i与C的公共顶点为v*ji,i1,2,s, 由归纳假设可知,G 1,G 2,G s都是欧拉图, 因而都存在欧拉回路C i,i1,2,s。 最后将C还原(即将删除的边重新加上), 并从C上的某顶点v
4、r开始行遍,每遇到v*ji,就行遍G i中的欧拉回路C i,i1,2,s,最后回到vr, 得回路vrv*j1v*j1v*j2v*j2v*jsv*jsvr, 此回路经过G中每条边一次且仅一次并行遍G中所有顶点, 因而它是G中的欧拉回路, 故G为欧拉图。,欧拉图的判定定理,定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。,定理15.2 无向图G是半欧拉图当且仅当G是连通的,且G中恰有两个奇度顶点。 证明 必要性。设G是m条边的n阶无向图,因为G为半欧拉图,因而G中存在欧拉通路(但不存在欧拉回路),设vi0ej1vi1vim-1ejmvim为G中一条欧拉通路,vi0vim
5、。vV(G),若v不在的端点出现,显然d(v)为偶数,若v在端点出现过,则d(v)为奇数,因为只有两个端点且不同,因而G中只有两个奇数顶点。另外,G的连通性是显然的。,半欧拉图的判定定理,定理15.2 无向图G是半欧拉图当且仅当G是连通的,且G中恰有两个奇度顶点。 证明 充分性。设G的两个奇度顶点分别为u0和v0,对G加新边(u0,v0),得G G(u0,v0),则G 是连通且无奇度顶点的图,由定理15.1可知,G 为欧拉图,因而存在欧拉回路C ,而CC -(u0,v0)为G中一条欧拉通路,所以G为半欧拉图。,半欧拉图的判定定理,有向欧拉图的判定定理,定理15.3 有向图D是欧拉图当且仅当D是
6、强连通的且每个顶点的入度都等于出度。 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的,且D中恰有两个奇度顶点,其中一个的入度比出度大1,另一个的出度比入度大1,而其余顶点的入度都等于出度。,例15.1,例15.1 设G是非平凡的且非环的欧拉图,证明:(1)(G)2。(2)对于G中任意两个不同顶点u,v,都存在简单回路C含u和v。 证明 (1)由定理15.5可知,eE(G),存在圈C,e在C中,因而p(G-e)p(G),故e不是桥。由e的任意性(G)2,即G是2边-连通图。 (2)u,vV(G),uv,由G的连通性可知,u,v之间必存在路径1,设G G-E(1),则在G 中u与v还必连通
7、,否则,u与v必处于G 的不同的连通分支中,这说明在1上存在G中的桥,这与(1)矛盾。于是在G 中存在u到v的路径2,显然1与2边不重,这说明u,v处于12形成的简单回路上。,求欧拉图中欧拉回路的算法,Fleury算法,能不走桥就不走桥 (1) 任取v0V(G),令P0v0。 (2) 设Piv0e1v1e2eivi已经行遍,按下面方法来从 E(G)-e1,e2,ei中选取ei+1:(a) ei+1与vi相关联;(b) 除非无别的边可供行遍,否则ei+1不应该为 GiG-e1,e2,ei中的桥。 (3)当(2)不能再进行时,算法停止。 说明 可以证明,当算法停止时所得简单回路Pmv0e1v1e2
8、emvm(vmv0)为G中一条欧拉回路。,Fleury算法示例,例15.2,下图是给定的欧拉图G。某人用Fleury算法求G中的欧拉回路时,走了简单回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后(观看他的错误走法),无法行遍了,试分析在哪步他犯了错误?,解答 此人行遍v8时犯了能不走桥就不走桥的错误,因而他没行遍出欧拉回路。当他走到v8时,G-e2,e3,e14,e10,e1,e8为下图所示。,此时e9为该图中的桥,而e7,e11均不是桥,他不应该走e9,而应该走e7或e11,他没有走,所以犯了错误。注意,此人在行遍中,在v3遇到过桥e3,v1处遇到过桥e8,但当时除
9、桥外他无别的边可走,所以当时均走了桥,这是不会犯错误的。,15.2 哈密顿图,历史背景:哈密顿周游世界问题与哈密顿图,哈密顿图,定义15.2 经过图(有向图或无向图)中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图,具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。 说明 哈密顿通路是图中生成的初级通路,哈密顿回路是生成的初级回路。判断一个图是否为哈密顿图,就是判断能否将图中所有顶点都放置在一个初级回路(圈)上,但这不是一件易事。与判断一个图是否为欧拉图不一样,到目前为止,人们还没有找到哈密顿图简单
10、的充分必要条件。,例题,(1)(2)是哈密顿图。 (3)是半哈密顿图。 (4)既不是哈密顿图,也不是半哈密顿图。,定理15.6,定理15.6 设无向图G是哈密顿图,对于任意V1V,且V1,均有p(G-V1)|V1| 其中,p(G-V1)为G-V1的连通分支数。 证明 设C为G中任意一条哈密顿回路,易知,当V1中顶点在C上均不相邻时,p(C-V1)达到最大值|V1|,而当V1中顶点在C上有彼此相邻的情况时,均有p(C-V1)|V1|,所以有 p(C-V1)|V1|。而C是G的生成子图,所以,有p(G-V1)p(C-V1)|V1|。 说明 本定理的条件是哈密顿图的必要条件,但不是充分条件。可以验证
11、彼得松图满足定理中的条件,但不是哈密顿图。若一个图不满足定理中的条件,它一定不是哈密顿图。,推论,推论 设无向图G是半哈密顿图,对于任意的V1V且V1,均有 p(G-V1)|V1|+1 证明 设P是G中起于u终于v的哈密顿通路,令G G(u,v)(在G的顶点u,v之间加新边),易知G 为哈密顿图,由定理15.6可知,p(G -V1)|V1|。因此,p(G-V1) p(G -V1-(u,v) p(G -V1)+1 |V1|+1,例15.3,例15.3 在下图中给出的三个图都是二部图。它们中的哪些是哈密顿图?哪些是半哈密顿图?为什么?,易知互补顶点子集V1a,fV2b,c,d,e 设此二部图为G1
12、,则G1。 p(G1-V1)4|V1|2, 由定理15.6及其推论可知,G1不是哈密顿图,也不是半哈密顿图。,例15.3,设图为G2,则G2,其中 V1a,g,h,i,c,V2b,e,f,j,k,d, 易知,p(G2-V1)|V2|6|V1|5, 由定理15.6可知,G2不是哈密顿图, 但G2是半哈密顿图。 baegjckhfid为G2中一条哈密顿通路。,设图为G3。G3,其中 V1a,c,g,h,e,V2b,d,i,j,f, G3中存在哈密顿回路。 如 abcdgihjefa, 所以G3是哈密顿图。,例15.3的说明,哈密顿通路是经过图中所有顶点的一条初级通路。 哈密顿回路是经过图中所有顶点
13、的初级回路。 对于二部图还能得出下面结论: 一般情况下,设二部图G,|V1|V2|,且|V1|2,|V2|2,由定理15.6及其推论可以得出下面结论:(1) 若G是哈密顿图,则|V1|V2|。(2) 若G是半哈密顿图,则|V2|V1|+1。(3) 若|V2|V1|+2,则G不是哈密顿图,也不是半哈密顿图。,例15.4,例15.4 设G是n阶无向连通图。证明:若G中有割点或桥,则G不是哈密顿图。 证明 (1)证明若G中有割点,则G不是哈密顿图。设v为连通图G中一个割点,则V v为G中的点割集,而p(G-V )21|V |由定理15.6可知G不是哈密顿图。(2)证明若G中有桥,则G不是哈密顿图。设
14、G中有桥,e(u,v)为其中的一个桥。若u,v都是悬挂点,则G为K2,K2不是哈密顿图。若u,v中至少有一个,比如u,d(u)2,由于e与u关联,e为桥,所以G-u至少产生两个连通分支,于是u为G中割点。由(1)的讨论可知,G不是哈密顿图。,定理15.7,定理15.7 设G是n阶无向简单图,若对于G中任意不相邻的顶点vi,vj,均有d(vi)+d(vj)n-1 (15.1)则G中存在哈密顿通路。 证明 首先证明G是连通图。否则G至少有两个连通分支,设G1,G2是阶数为n1,n2的两个连通分支,设v1V(G1),v2V(G2),因为G是简单图,所以dG(v1)+dG(v2)dG1(v1)+dG2
15、(v2)n1-1+n2-1n-2这与(15.1)矛盾,所以G必为连通图。,定理15.7,下面证G中存在哈密顿通路。 设v1v2vl为G中用“扩大路径法”得到的“极大路径”, 即的始点v1与终点vl不与外的顶点相邻。显然有ln。 (1)若ln,则为G中哈密顿通路。 (2)若ln,这说明不是哈密顿通路,即G中还存在着外的顶点。但可以证明G中存在经过上所有顶点的圈。(a) 若v1与vl相邻,即(v1,vl)E(G),则(v1,vl)为满足要求的圈。,定理15.7,(b)若v1与vl不相邻,设v1与上的vi1v2,vi2,vik相邻(k2)(否则 d(v1)+d(vl)1+l-2=l-1n-1,这与(
16、15.1)矛盾)此时,vl至少与vi2,vik相邻的顶点vi2-1,vik-1之一相邻(否则 d(v1)+d(vl)k+l-2-(k-1)l-1n-1)设vl与vir -1相邻(2rk),见下图所示。,于是,回路Cv1v2vir -1vlvlr -1vivirv1 过上的所有顶点。,定理15.7,(c)下面证明存在比更长的路径。因为ln,所以C外还有顶点,由G的连通性可知,存在vl+1V(G)-V(C)与C上某顶点vt相邻,见下图所示。,删除边(vt-1,vt)得路径vt-1v1virvlvir-1vtvl+1比长度大1, 对上的顶点重新排序,使其成为v1v2vlvl+1, 对重复(a)(c),在有限步内一定得到G的哈密顿通路。,