第15章欧拉图与哈密顿图.

第十五章欧拉图与哈密顿图第十五章欧拉图与哈密顿图欧拉图哈密顿图最短路问题与货郎担问题知识点：欧拉图、汉密尔顿图、Fleury算法、Dijkstra算法、货郎担问题。教学要求：深刻理解和掌握欧拉图与汉密尔顿图的性质。教学重点：欧拉图与汉密尔顿图的性质。学时:2§15.1欧拉图两个与可行遍问题有关的问题一个要求行遍图的每条边恰好一次,这就是欧拉回路问题,对应的图称为欧拉图一个要求行遍图的每个顶点恰好一次,这就是哈密顿圈问题,对应的图称为哈密顿图ABCD哥尼斯堡七桥问题周游世界问题®§15.1欧拉图定义15.1通过图(无向图或有向图)中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路.通过图(无向图或有向图)中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路.具有欧拉回路的图称为欧拉图具有欧拉通路而无欧拉回路的图称为半欧拉图规定平凡图是欧拉图欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性.®上图中，(1),(4)为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图.欧拉图实例(1)(2)(3)(4)(5)(6)§15.1欧拉图定理15.1无向图G是欧拉图当且仅当G是连通图且没有奇度顶点证若G为平凡图无问题.下设G为n阶m条边的无向图.必要性设C为G中一条欧拉回路.(1)G连通显然.(2)viV(G)，vi在C上每出现一次获2度，所以vi为偶度顶点.由vi的任意性，结论为真.充分性对边数m做归纳法(1)m=1时，G为一个环，则G为欧拉图.(2)设mk（k1）时结论为真，m=k+1时如下证明：®(a)制造满足归纳假设的若干个小欧拉图.由连通及无奇度定点可知，(G)≥2，用扩大路径法可得G中长度≥3的圈C1.删除C1上所有边（不破坏G中顶点度数的奇偶性）得G，则G无奇度顶点，设它有s≥1个连通分支G1,G2,…,Gs，它们的边数均≤k，因而它们都是小欧拉图.(b)将C1上被删除的边还原，从C1上某点出发走出G的一条欧拉回路C.PLAY从以上证明不难看出：欧拉图是若干个边不重的圈之并，见下图.§15.1欧拉图定理15.2无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点证必要性简单.充分性（利用定理15.1）设u,v为G中的两个奇度顶点，令G=G(u,v)则G连通且无奇度顶点，由定理15.1知G为欧拉图，因而存在欧拉回路C，令=C(u,v)则为G中欧拉通路.®§15.1欧拉图定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度等于出度定理15.4有向图D是半欧拉图当且仅当D是单向连通的且恰有两个奇度顶点,其中一个顶点的入度比出度大1,另一个顶点出度比入度大1,而其余顶点入度等于出度定理15.5G是非平凡的欧拉图当且仅当G是连通的且是若干个边不重的圈的并彼德森图K3,3K5®§15.1欧拉图Fleury(弗罗莱)算法⑴任取v0∈V(G),令P0=v0,i=0⑵设Pi=v0e1v1e2…eivi,如果E(G)-{e1,e2,…,ei}中没有与vi关联的边,则计算停止。否则按下述条件从E(G)-{e1,e2,…,ei}中任取一条边ei+1(a)ei+1和vi相关联;(b)除非没有别的边可选择,否则ei+1不是Gi=G–{e1,e2,…,ei}中的割边(桥)设ei+1=(vi,vi+1),把ei+1vi加入Pi得到Pi+1⑶令i=i+1,返回(2)®§15.1欧拉图例应用Fleury算法求图G的一个欧拉回路v6v5v4v3v2v1e7e5e4e3e2e1e6e8Gv6v5v4v3v2v1e7e5e4e3e2e1e8G1v6v5v4v3v2v1e5e4e3e1e8e2G2v6v5v4v3v2v1e5e4e3e1e2G3v6v5v4v3v2v1e4e3e1e2G4v6v5v4v3v2v1e4e1e2G5v6v5v4v3v2v1e1e2G6v6v5v4v3v2v1e1G7W0=v0W1=v0e6v5W2=v0e6v5e7v6W3=v0e6v5e7v6e8v1W4=v0e6v5e7v6e8v1e5v3W5=v0e6v5e7v6e8v1e5v3e3v4W6=v0e6v5e7v6e8v1e5v3e3v4e4v3W8=v0e6v5e7v6e8v1e5v3e3v4e4v3e2v2e1v1W7=v0e6v5e7v6e8v1e5v3e3v4e4v3e2v2®背景1857年，哈密尔顿发明了一个游戏(IcosianGame).它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。游戏目的是“环球旅行”。为了容易记住被旅游过的城市，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示。十二面体§15.2哈密顿图哈密尔顿(1805---1865),爱尔兰数学家。个人生活很不幸，但兴趣广泛：诗歌、光学、天文学和数学无所不能。他的主要贡献是在代数领域，发现了四元数(第一个非交换代数)，他认为数学是最美丽的花朵。哈密尔顿把该游戏以25英镑的价格买给了J.JacquesandSons公司(该公司如今以制造国际象棋设备而著名)，1859年获得专利权。但商业运作失败了。该游戏促使人们思考点线连接的图的结构特征。这就是图论历史上著名的哈密尔顿问题。§15.2哈密顿图定义15.2通过图(无向图或有向图)中所有顶点一次且仅一次的通路称为哈密顿通路.通过图(无向图或有向图)中所有顶点一次且仅一次的回路称为哈密顿回路(哈密顿圈).具有哈密顿回路的图称为哈密顿图具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图规定平凡图是哈密顿图环与平行边不影响哈密顿性.®实例在上图中，(1),(2)是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图，也不是半哈密顿图，为什么？(1)(2)(3)(4)与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件。定理15.6设无向图G＝V,E是哈密顿图，对于任意V1V，且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|。说明本定理的条件是哈密顿图的必要条件，但不是充分条件。可以验证彼得松图满足定理中的条件，但不是哈密顿图。若一个图不满足定理中的条件，它一定不是哈密顿图。§15.2哈密顿图推论设无向图G＝V,E是半哈密顿图，对于任意的V1V且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.2哈密顿图§15.2哈密顿图可用来判别图G不是哈密顿图,但是这个方法并不总是有效删去三个黑点后得到的图具有四个连通分支，所以原图不是哈密顿图右图不是哈密顿图,但任意删去V的非空真子集S,都有p(G–S)|S|所以用定理15.6判别一个图不是哈密顿图并不总是有效®例15.3在下图中给出的三个图都是二部图。它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？易知互补顶点子集V1＝{a,f}V2＝{b,c,d,e}设此二部图为G1，则G1＝V1,V2,E。p(G1-V1)＝4|V1|＝2，由定理15.6及其推论可知，G1不是哈密顿图，也不是半哈密顿图。§15.2哈密顿图设图为G2，则G2＝V1,V2,E，其中V1＝{a,g,h,i,c}，V2＝{b,e,f,j,k,d}，易知，p(G2-V1)＝|V2|＝6|V1|＝5，由定理15.6可知，G2不是哈密顿图，但G2是半哈密顿图。baegjckhfid为G2中一条哈密顿通路。设图为G3。G3＝V1,V2,E，其中V1＝{a,c,g,h,e}，V2＝{b,d,i,j,f}，G3中存在哈密顿回路。如abcdgihjefa，所以G3是哈密顿图。§15.2哈密顿图例15.3的说明哈密顿通路是经过图中所有顶点的一条初级通路。哈密顿回路是经过图中所有顶点的初级回路。对于二部图还能得出下面结论：一般情况下，设二部图G＝V1,V2,E，|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)≥2＞1＝|V|由定理15.6可知G不是哈密顿图。(2)证明若G中有桥，则G不是哈密顿图。设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的两个连通分支，设v1∈V(G1)，v2∈V(G2)，因为G是简单图，所以dG(v1)+dG(v2)＝dG1(v1)+dG2(v2)≤n1-1+n2-1≤n-2这与(15.1)矛盾，所以G必为连通图。定理15.7下面证G中存在哈密顿通路。设Г＝v1v2…vl为G中用“扩大路径法”得到的“极大路径”，即Г的始点v1与终点vl不与Г外的顶点相邻。显然有l≤n。(1)若l＝n，则Г为G中哈密顿通路。(2)若l＜n，这说明Г不是哈密顿通路，即G中还存在着Г外的顶点。但可以证明G中存在经过Г上所有顶点的圈。(a)若v1与vl相邻，即(v1,vl)∈E(G)，则Г∪(v1,vl)为满足要求的圈。定理15.7(b)若v1与vl不相邻，设v1与Г上的vi1＝v2,vi2,…,vik相邻(k≥2)(否则d(v1)+d(vl)≤1+l-2=l-1n-1，这与(15.1)矛盾)此时，vl至少与vi2,…,vik相邻的顶点vi2-1,…,vik-1之一相邻(否则d(v1)+d(vl)≤k+l-2-(k-1)＝l-1n-1)设vl与vir-1相邻（2≤r≤k），见下图所示。于是，回路C＝v1v2…vir-1vlvlr-1…vi…virv1过Г上的所有顶点。定理15.7的推论推论设G为n(n≥3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)≥n(15.2)则G中存在哈密顿回路，从而G为哈密顿图。证明由定理15.7可知，G中存在哈密顿通路，设Г＝v1v2…vn为G中一条哈密顿通路，若v1与vn相邻，设边e＝(v1,vn)，则Г∪{e}为G中哈密顿回路。若v1与vn不相邻，应用(15.2)，同定理15.7证明中的(2)类似，可证明存在过Г上各顶点的圈，此圈即为G中的哈密顿回路。定理15.8定理15.8设u,v为n阶无向图G中两个不相邻的顶点，且d(u)+d(v)≥n，则G为哈密顿图当且仅当G∪(u,v)为哈密顿图((u,v)是加的新边)。证明(略)。例15.5例15.5在某次国际会议的预备会议中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人