chap10 E图和H图.pptx

第十章E图和H图,1,10.1七桥问题与E图,历史上的哥尼斯堡七桥问题是著名的图论问题。问题是这样的：18世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥，它们把河的两岸和两个岛连接起来。每逢假日，城中居民进行环城游玩，人们对此提出了一个“遍游”问题，即能否有这样一种走法，使得从某地出发通过且只通过每座桥一次后又回到原地呢？,2,A,B,C,D,用顶点表示陆地，边表示陆地之间的桥。则问题等价于“能否一笔画出右图？”，即找经过每条边一次且仅一次的回路。,Euler证明了，七桥问题是无解的。,E图,定义10.1.1：设G是一个图，经过G的每一条边的链称为E链；闭的E链称为E闭链。如果G中存在E链，称G为半E图；如果G中存在E闭链，称G为E图（欧拉图）。,3,问题：对于一个图G，如何判定它是否为E图、半E图呢？还记得我们第一次课的手机解锁图吗？,手机解锁图,下面的讨论中设G是非平凡的连通图。,E图,半E图,都不是,无奇点的连通图是E图,引理10.1.1：连通图G中无奇点，则G是E图。证明：（反证法）设G是无奇点的连通图且G不是E图。（构造反例：G中有闭链，且是E链）在所有连通无奇点的非E图中，选一个边最少的图G。因G的每个顶点的度至少是2，从而G必含闭链。,5,若G不含回路，则G是树。我们知道树中至少有两个悬挂点（奇点），矛盾。所以G中一定含有回路。而回路就是闭链。所以G中必含闭链。,设C是G中最长的闭链，由假设C不是E闭链。（下面推出矛盾）。,为什么？,6,C,C,G,v,CC是一条闭链图示,因G连通，C和C必有公共点v，,假设C不是E闭链，于是GE(C)中必含非平凡连通分支G且G中无奇点。于是G中也有一条闭链C。,以v作为CC的起、终点，于是CC是G的一条闭链且长度大于C的长度，这与C的假设矛盾。故G是E图。,E图是无奇点的连通图,引理10.1.1：E图是无奇点的连通图。证明：设G是E图，C是G的一条E闭链。由于G连通且C是含G的每边恰一次的闭链，因此，C中的每个点都既是起点也是终点。于是，从C上的任一点u出发，每经过一个顶点v，就有两条与v关联的边出现(一进一出)。这样，C上的每个顶点，也即G的每个顶点的度均为偶数，故G中无奇点。,7,由引理10.1.1和10.1.1，我们有：定理10.1.1：连通图G是E图当且仅当G中无奇点。,半E图中最多有两个奇点,推论10.1.1G是半E图当且仅当G中最多有两个奇点。证明：(充分性)设G是半E图，C是G的一条E链。除起点与终点外，C中每个顶点的度均为偶数。又因G连通，故G最多有两个奇点。(必要性)设G最多只有两个奇点。若G无奇点，则由定理10.1.1知，G为E图，亦为半E图；若G有两个奇点，设为u和v,则在G中加入e=uv的边，使G中无奇点。由定理10.1.1知，G+e为E图，即G+e含E闭链C，于是Ce构成G的一条E链，所以G是半E图。,8,为什么不要证明G中只有一个奇点的情况？,因为任何一个图的奇点个数必为偶数。,练一练,哥尼斯城堡桥不是E图,10,“一笔画”游戏攻略,我国民间很早就流传一种“一笔画”游戏，由刚才所学的定理，你能给出游戏攻略吗？如何判定，如何画？如果图中所有结点是偶点，则可以任选一点作为始点一笔画完；如果图中只有两个奇点，则可以选择其中一个奇点作为始点也可一笔画完。其余情况则不能一笔画完。,应用题,例：下图是一幢房子的平面图形，前门进入一个客厅，由客厅通向4个房间。如果要求每扇门只能进出一次，现在你由前门进去，能否通过所有的门走遍所有的房间和客厅，然后从后门走出？,10.2周游世界问题与H图,周游世界问题:用一个正十二面体的二十个顶点来代表二十个城市，要求从其中任一顶点出发，沿着这个正十二面体的棱走遍这二十个顶点，且每个城市只经过一次，最后回到起点。该问题等价于“能否从下图找一条含所有顶点的回路？”,13,H图,定义10.2.1：设G是一个图，含G的每个顶点的通路称为H通路；起点与终点重合的H通路称为H回路；如果G中存在H回路，称G为H图（汉密尔顿图）；若G中存在H通路，称G为半H图。显然，H图必是半H图，反之不然。,14,Herschel图,该图是半H图。,15,因为它是一个具有奇数个顶点的二分图。所以不可能有H回路。,因为二分图中的回路一定是偶数条边。(定理7.5.2),为什么？,H图的判定,问题：对于一个图G，如何判定它是否为H图、半H图呢？,尽管H回路与E回路问题在形式上极为相似，但是到目前为止还不知道一个图为H图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。,H图的一个必要条件,定理10.2.1如果G是一个H图，则对V(G)的任何非空真子集S，均成立：(GS)|S|证明：设C是G的H回路(G的所有顶点都在C上)，S是V(G)的任一非空子集。则显然在GS中，C最多被分为|S|段，所以W（GS）|S|,17,定理10.2.1证明图示,18,G(H图),C(H回路）,一个非H图的判定,取S为红色点集。|S|=5。,(GS)=6|S|,根据定理10.2.1，此图不是H图。,试一试,你能判别下图是否为H图吗？,必要条件仅可判定非H图,注意定理10.2.1只是判断H图的必要条件，有的图虽然满足条件，却不是H图。(满足的不一定是，不满足的一定不是）。,21,Peterson图,Peterson图是半H图而不是H图。,如下面的Peterson图不是H图。可是它却满足定理10.2.1的条件。,H图的充分条件,问题：满足什么条件的图一定为H图、半H图呢？判断H图、半图的充分条件很多，我们逐一介绍。,H图的一个充分条件,定理10.2.2设G是p(3)阶简单图。如果G中任何两个不邻接的顶点u和v均满足：d(u)+d(v)p，则G是H图；d(u)+d(v)p-1，则G是半H图。证明略。,23,练一练,例：某地有个风景点。若每个景点均有两条道路与其他景点相通，问是否可经过每个景点恰好一次而游完这处？,解：将景点作为顶点，道路作为边，则得到一个有个顶点的无向图。由题意，对每个顶点vi，有d(vi)2（i5）。则对任两点vi，vj（i，j5）均有d(vi)d(vj)=2+2=4=5-1可知此图一定有一条H通路，本题有解。,充分非必要条件,例如右图是H图，但任意两顶点度之和为4，而p=5。,25,注意定理10.2.2只是判断H图的充分条件，有的图虽然是H图，但却不满足该条件。(满足的一定是，不满足的不一定不是）。,H图的又一个充分条件,推论10.2.1设G是p(3)阶简单图，如果(G)p/2,则G是H图。证明：任取u,vV(G),由题设均有d(u)+d(v)p/2+p/2=p因此，由定理10.2.2知，G是H图。,26,图的闭包,定义10.2.2设A是p阶图，对A中满足：d(u)+d(v)p(1)的顶点u,v,若uvE(A),则将边uv加入到A中，得到A+uv.如此反复加边，直到所有满足(1)的点都邻接，最后所得的图称为A的闭包，记为。,27,由于一个图的闭包是唯一的，所以求闭包时加边的顺序可以任意。,求一个图的闭包,例：求右图的闭包。,28,v1,v2,v3,v4,v5,v6,d(v1)+d(v4)6,连接v1和v4。,d(v3)+d(v5)6,连接v3和v5。,d(v3)+d(v6)6,连接v3和v6。,d(v4)+d(v6)6,连接v4和v6。,d(v4)+d(v2)6,连接v4和v2。,d(v5)+d(v2)6,连接v5和v2。,d(v6)+d(v2)6,连接v6和v2。,存在A=的情形：A=Kp,A中无满足条件的边可加，如图G。,G,H图的充要条件,引理10.2.1设G是p阶简单图，u与v是G中两个不邻接的顶点且满足：d(u)+d(v)p于是，G是H图当且仅当G+uv是H图。定理10.2.3p阶简单图A是H图当且仅当是H图。,29,10.3应用,推销员问题设有n个城市C1,Cn,某推销员从C1出发推销产品，每个城市都要到达且仅到达一次，最后回到C1。已知每两个城市之间的距离，问怎样安排行程才能使总路程最短？等价的图论语言描述在赋权完全图中求权最小的H回路，简称为最优回路。,30,求最优回路,研究最优回路问题是十分有趣且有实用价值的。但很可惜，至今没有找到一个很有效的算法。最简单的方法穷举法即找出KP的所有H回路，然后从中选出最小者。可是对n(4)个顶点的完全图，所有权可能不等的H回路共有(n1)!种，其时间复杂度为O(n!)。所以当N较大时，用穷举法求解在计算机上也很难实现。如何用较快的算法来求最优回路，是人们正在研究且尚未最终解决的问题。,31,求最优回路的近似解,人们开始转而求其次，即寻找一种算法能较快地求出一种较优的但不一定是最优的解，即近似最优解。最邻近法任意选择一个顶点u作为起点；选择离当前顶点u最近且尚未到达的顶点v作为下一个顶点，把边(u,v)加入到路线中，并把v作为新的当前顶点；重复这样的选择直到所有顶点均已达到；将最后到达的顶点与起点相连。,用最邻近法求最优回路,1,3,2,4,5,1,2,7,3,1,2,4,4,5,3,从顶点1出发：Path=;cost=14;,不难看出，从节点2出发：Path=;cost=10;且此为最优解！,这是最优解吗？,改进的最邻近法：分别从顶点i出发（i=1,2,.n）用最邻近法求最优回路，然后通过结果比较，取其中最小代价回路，可以求得更接近于最佳解的近似解。,逐次改进法,逐次改进法先找赋权完全图G的一条H回路，记为C=v1v2vnv1；如果w(vi1vj1)+w(vivj)w(vi1vi)+w(vj1vj)则用H回路Cij=v1v2vi1vj1vj2vi+1vivjvj+1vnv1代替C。反复替代，直到找不出满足条件的Cij为止。,34,图示：逐次改进法,任意一条H回路C如图所示。,35,v1,vj1,vj2,vi,vi+1,vi1,vj,vj+1,v2,vn,现在找到w(vi1vj1)+w(vivj)w(vi1vi)+w(vj1vj),于是将C改进为Cij.,显然改进后的回路仍然是H回路且权值较低。,用C14=v1v4v3v2v5v6v1代替C.(绕过v1v2和v4v5),用逐次改进法求最优回路,首先选C=v1v2v3v4v5v6v1w(C)=14+15+8+13+1+5=56,36,v5,v6,v1,v2,v3,v4,13,8,15,14,5,1,7,6,5,11,9,13,8,12,10,w(v2v5)+w(v1v4)w(v1v2)+w(v4v5),w(v2v4)+w(v1v3)|S|,v1,v2,v3,v5G,v6,v7,v8,v4,策略：选择度数大的顶点,G不是H图,解答二,任取一结点如v1，用A标记，所有与它相邻的结点标B。继续不断地用A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直到图中所有结点全部标记完毕。,v1,v2,v3,v5G,v6,v7,v8,v4,G中有3个A点，五个B点，相差2个，所以不含哈密尔顿回路。故G不是H图。,如果图中有一条汉密尔顿路，则必交替通过结点A和B。因此或者结点A和B数目一样，或者两者相差个。,课堂练习（2）,某博物馆的一层布置如下图，其中边代表走廊，结点e是入口，结点g是礼品店，通过g我们可以离开博物馆。请找出从博物馆e进入，经过每个走廊恰好一次，最后从g处离开的路线。,a,b,c,e,g,h,j,f,i,d,e,c,e,b,g,a,d,f,i,j,b,g,a,d,f,h,h,g,课堂练习（3）,考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程考试不排在连续的两天中。试问如果没有教师担任多于四门的课程，符合上述要求的考试安排是否可能？请说明理由。,解答：可能。设G为具有七个顶点的图，每个顶点对应