图论及其应用ppt13.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Email:,yc517922,图论及其应用,任课教师：杨春,数学科学学院,1,第四章 欧拉图与哈密尔顿图,主要内容,一、欧拉图与中国邮路问题,二、哈密尔顿图,三、度极大非哈密尔顿图与,TSP,问题,教学时数,安排,8,学时讲授本章内容,四、超哈密尔顿图问题,2,本次课主要内容,(,一,),、欧拉图及其性质,(,二,),、,Fleury,算法,(,三,),、中国邮路问题,欧拉图与中国邮路问题,3,1,、欧拉图的概念,(,一,),、欧拉图及其性质,(1),、问题背景,-,欧拉与哥尼斯堡七桥问题,问题：对于图,G,，它在什么条件下满足从某点出发，经过每条边一次且仅一次，可以回到出发点？,4,哥尼斯堡城,(,位于德国北部,),在欧拉的生活与图论历史中扮演着非常重要角色。因为它，产生了著名的欧拉图定理，因为它，产生了图论。,注：,一笔画,-,中国,古老的,民间游戏,要求：对于一个图,G,笔不离纸,一笔画成,.,(2),、欧拉图概念,定义,1,对于连通图,G,，如果,G,中存在经过每条边的闭迹，则称,G,为欧拉图，简称,G,为,E,图。欧拉闭迹又称为欧拉环游，或欧拉回路。,欧拉图,4,1,3,2,4,1,3,2,非欧拉图有欧拉迹,非欧拉图无欧拉迹,1,2,3,4,5,2,、欧拉图的性质,定理,1,下列陈述对于非平凡连通图,G,是等价的：,(1),G,是欧拉图；,(2),G,的顶点度数为偶数；,(3),G,的边集合能划分为圈。,证明,:(1),(2),由,(1),，设,C,是欧拉图,G,的任一欧拉环游，,v,是,G,中任意顶点，,v,在环游中每出现一次，意味在,G,中有两条不同边与,v,关联，所以，在,G,中与,v,关联的边数为偶数，即,v,的度数为偶数，由,v,的任意性，即证明,(2),。,(2),(3),由于,G,是连通非平凡的且每个顶点度数为偶数，所以,G,中至少存在圈,C,1,从,G,中去掉,C,1,中的边，得到,G,的生成,6,子图,G,1,若,G,1,没有边，则,(3),成立否则，,G,1,的每个非平凡分支是度数为偶数的连通图，于是又可以抽取一个圈。反复这样抽取，,E(G),最终划分为若干圈。,(3),(1),设,C,1,是,G,的边划分中的一个圈。若,G,仅由此圈组成，则,G,显然是欧拉图。,否则，由于,G,连通，所以，必然存在圈,C,2,它和,C,1,有公共顶点。于是，,C,1,C,2,是一条含有,C,1,与,C,2,的边的欧拉闭迹，如此拼接下去，得到包含,G,的所有边的一条欧拉闭迹。即证,G,是欧拉图。,推论,1,连通图,G,是欧拉图当且仅当,G,的顶点度数为偶。,推论,2,连通非欧拉图,G,存在欧拉迹当且仅当,G,中只有两个顶点度数为奇数。,7,例,1,下面图中谁是欧拉图？谁是非欧拉图但存在欧拉迹？谁是非欧拉图且不存在欧拉迹？,G,1,G,2,G,3,解：,G,1,是欧拉图；,G,2,是非欧拉图，但存在欧拉迹；,G,3,中不存在欧拉迹。,例,2,证明：若,G,和,H,是欧拉图，则 是欧拉图。,8,证明：首先证明：对任意,u V(G),v V(H),有：,事实上，设,z,是,u,的任意一个邻点，一定有,(u,v),的一个邻点,(z,v),反之亦然。同理，对于,v,的任意一个邻点,w,，一定有,(u,v),的一个邻点,(u,w),反之亦然。即,:(u,v),在乘积图中邻点个数等于,u,在,G,中邻点个数与,v,在,H,中邻点个数之和。,所以，,GH,是欧拉图，那么 顶点度数为偶数。,其次证明：是连通的。,由于,G,H,都是欧拉图，所以都连通。设最短的,(u,1,u,2,),路,9,最短的,(v,1,v,2,),路分别为：,那么，由乘积图的定义：在乘积图中有路：,这样，我们证明了 是连通的且每个顶点度数为偶数。即它是欧拉图。,(,二,),、,Fleury,(,弗勒里,),算法,该算法解决了在欧拉图中求出一条具体欧拉环游的方法。方法是尽可能避割边行走。,算法,:,(1),、任意选择一个顶点,v,0,置,w,0,=v,0,;,10,(2),、假设迹,w,i,=v,0,e,1,v,1,e,i,v,i,已经选定，那么按下述方法从,E-,e,1e,2,e,i,中选取边,e,i+1,:,1),、,e,i+1,与,v,i,相关联；,2),、除非没有别的边可选择，否则,e,i+1,不能是,G,i,=G-,e,1,e,2,e,i,的割边。,(3),、当,(2),不能执行时，算法停止。,例,3,在下面欧拉图,G,中求一条欧拉回路。,d,c,b,a,f,e,g,图,G,h,j,i,11,解：,d,c,b,a,f,e,g,图,G,h,j,i,例,4,某博物馆的一层布置如下图，其中边代表走廊，结点,e,是入口，结点,g,是礼品店，通过,g,我们可以离开博物馆。请找出从博物馆,e,进入，经过每个走廊恰好一次，最后从,g,处离开的路线。,a,f,e,d,c,b,i,h,g,j,12,解：图中只有两个奇度顶点,e,和,g,因此存在起点为,e,终点为,g,的欧拉迹。,为了在,G,中求出一条起点为,e,终点为,g,的欧拉迹，在,e,和,g,间添加一条平行边,m,a,f,e,d,c,b,i,h,g,j,m,用,Fleury,算法求出欧拉环游为：,emgcfabchbdhgdjiejge,所以：解为：,egjeijdghdbhcbafcg,13,例,4,证明：若,G,有,2k0,个奇数顶点，则存在,k,条边不重的迹,Q,1,Q,2,Q,k,，使得：,证明：不失一般性，只就,G,是连通图进行证明。,14,设,G=(n,m),是连通图。令,v,l,，,v,2,，,v,k,v,k+1,v,2k,是,G,的所有奇度点。,在,v,i,与,v,i+k,间连新边,e,i,得图,G*,（,1,ik).,则,G*,是欧拉图，因此，由,Fleury,算法得欧拉环游,C.,在,C,中删去,e,i,（,1ik).,得,k,条边不重的迹,Q,i,（,1ik):,例,5,设,G,是非平凡的欧拉图，且,v V(G),。证明：,G,的每条具有起点,v,的迹都能扩展成,G,的欧拉环游当且仅当,G-v,是森林。,证明：“必要性”,若不然，则,G-v,有圈,C,。,15,考虑,G,1,=G-E(C),的含有顶点,v,的分支,H,。,由于,G,是非平凡欧拉图，所以,G,1,的每个顶点度数为偶数，从而，,H,是欧拉图。,H,是欧拉图，所以存在欧拉环游,T.,对于,T,，把它看成,v,为起点和终点的一条欧拉迹，显然不能扩充为,G,的欧拉环游。这与条件矛盾！,“充分性”,若不然，设,Q=(v,w),是,G,的一条不能扩充为,G,的欧拉环游的最长迹，显然,v=w,且,Q,包含了与,v,关联的所有边。即,Q,是一条闭迹。,于是，,G-v,包含,G-Q,且,G-Q,的每个顶点度数为偶数,.,于是，,G-Q,的非平凡分支是欧拉图，说明有圈，即,G-v,有圈，这与条件矛盾,.,16,(,三,),、中国邮路问题,1962,年，中国数学家管梅谷提出并解决了“中国邮路问题”,1,、问题邮递员派信的街道是边赋权连通图。从邮局出发，每条街道至少行走一次，再回邮局。如何行走，使其行走的环游路程最短？,如果邮路图本身是欧拉图，那么由,Fleury,算法，可得到他的行走路线。,如果邮路图本身是非欧拉图，如何重复行走街道才能使行走总路程最短？,17,2,、管梅谷的结论,定理,2,若,W,是包含图,G,的每条边至少一次的闭途径，则,W,具有最小权值当且仅当下列两个条件被满足：,(1)G,的每条边在,W,中最多重复一次；,(2),对于,G,的每个圈上的边来说，在,W,中重复的边的总权值不超过该圈非重复边总权值。,证明：“必要性”,首先，设,G,是连通非欧拉图，,u,与,v,是,G,的两个奇度顶点，把连接,u,与,v,的路上的边改为,2,重边，则路中的点的度数奇偶性没有改变，仍然为偶数，但,u,与,v,的度数由奇数变成了偶数。如果对,G,中每对奇度点都如此处理，则最终得到的图为欧拉图。设该图为,G,1,.,18,其次，对,G,1,作修改：,如果在,G,1,中，边,e,重复数大于,2,，,则在,G,1,中删掉,2,条重复的,e,边后，所得之图仍然是包含,G,的欧拉图。,在,G,1,中，对每组平行边都做上面的处理，最后得到一个重复边数最多为,1,的包含,G,的欧拉图,G,2,。,这说明，若,W,是包含,G,的所有边的欧拉环游，则,G,中每条边至多在,W,里出现两次。这就证明了,(1).,又设,C,是,G,2,中任意一个圈，在该圈中，如果重复边的总权值超过该圈中非重复边总权值，那么可以把该圈中平行边改为非平行边，而把非平行边改为平行边，如此修改，得到的图仍然是包含,G,的欧拉图，但对应的欧拉环游长度减小了。,19,这就是说，只要对,G,2,的每个圈都作上面的修改，最后得到的图仍然为包含,G,的欧拉图，而最后的图正好满足,(2).,“充分性”,只需证明：任何两条包含,G,中所有边的闭途径,W,1,与,W,2,如果满足定理,2,的两个条件，则它们有相同的总权值。,设,Y,1,与,Y,2,分别表示,W,1,与,W,2,中重复出现的边集合。,我们先证明：对于任意一个圈,C,*,如果满足：,有：,20,断言,1,：,GY,的每个顶点度数必然为偶数。,令：,Y=(,Y,1,-Y,2,),(,Y,2,-Y,1,),首先：对于,G,中任意点,v,如果,d,G,(v),是奇数，那么,Y,1,与,Y,2,中与,v,关联的边数均为奇数；,如果,d,G,(v),是偶数，那么,Y,1,与,Y,2,中与,v,关联的边数均为偶数。,其次，设,Y,1,与,Y,2,中与,v,关联的边数分别为,y,1,与,y,2,其中相同的边数为,y,0,，那么，,Y,中与,v,关联的边数为：,所以，,Y,中与,v,关联的边数为偶数，说明,GY,的每个顶点度数必然为偶数。,21,断言,2,：,由于,GY,的每个顶点度数为偶数。所以，它的每个分支是欧拉图。因此，,GY,可以作不重圈分解。,设,事实上，因为：,22,又因为：,所以：,由断言,2,很容易得到：,所以：,23,又因为：,注,:,定理,2,的证明过程实际上给出了求中国邮路问题的方法,.,下面看一个例题。,例,5,求包含下图,G,的一个最优欧拉环游。,所以：,v,1,v,2,v,3,v,4,v,5,v,6,v,7,1,3,2,2,5,2,3,3,3,5,4,G,24,解：由定理,2,：,v,1,v,2,v,3,v,4,v,5,v,6,v,7,1,3,2,2,5,2,3,3,3,5,4,G,v,1,v,2,v,3,v,4,v,5,v,6,v,7,1,3,2,2,5,2,3,3,3,5,4,v,2,v,3,v,4,v,5,v,6,v,7,1,3,2,2,5,2,3,3,3,5,4,v,1,v,2,v,3,v,4,v,5,v,6,v,7,1,3,2,2,5,2,3,3,3,5,4,v,1,25,例,6,如果一个非负权的边赋权图,G,中只有两个奇度顶点,u,与,v,设计一个求其最优欧拉环游的算法。,解：,1,、算法,(1),、在,u,与,v,间求出一条最短路,P;(,最短路算法,),(2),、在最短路,P,上，给每条边添加一条平行边得,G,的欧拉母图,G*;,(3),、在,G,的欧拉母图,G*,中用,Fleury,算法求出一条欧拉环游。,2算法证明,26,定理：用上面方法求出的欧拉环游是最优欧拉环游。,证明：设,u,与,v,是,G,的两个奇度顶点,G*,是,G,的任意一个欧拉母图。,考虑,G*E*-E,显然它只有两个奇数顶点,u,与,v,当然它们必须在,G*E*-E,的同一个分支中，因此，存在,(u,v),路,P*.,所以，,即证明定理。,例如：求出下图的一条最优欧拉环游。,27,解：,y,2,2,2,2,1,1,u,4,3,3,6,5,w,x,v,G,z,y,2,2,2,2,1,1,u,4,3,3,6,5,w,x,v,G,z,最优欧拉环游：,x u y w v z w y x u w v x z y x,28,作业,P97-99,习题,4,：,1,2,3,7,8,9,29,5,班,632484109,6,班,290292196,七班,137105792,8,班,2570088903,30,