图论第四章欧拉图与哈密尔顿图精品文稿.ppt

图论课件第四章欧拉图与哈密尔顿图1第1页，本讲稿共33页第四章 欧拉图与哈密尔顿图主要内容一、欧拉图与中国邮路问题二、哈密尔顿图三、度极大非哈密尔顿图与TSP问题教学时数安排8学时讲授本章内容四、超哈密尔顿图问题2第2页，本讲稿共33页本次课主要内容(一)、欧拉图及其性质(二)、Fleury算法(三)、中国邮路问题欧拉图与中国邮路问题3第3页，本讲稿共33页 1、欧拉图的概念、欧拉图的概念(一一)、欧拉图及其性质、欧拉图及其性质 (1)、问题背景、问题背景-欧拉与哥尼斯堡七桥问题欧拉与哥尼斯堡七桥问题 结论：在一个点线连接的图形中，如果每个顶点关联结论：在一个点线连接的图形中，如果每个顶点关联偶数条边，并且点与点之间有路可行，则从某点出发，偶数条边，并且点与点之间有路可行，则从某点出发，经过每条边一次且仅一次，可以回到出发点。经过每条边一次且仅一次，可以回到出发点。4第4页，本讲稿共33页 哥尼斯堡城哥尼斯堡城(位于德国北部位于德国北部),在欧拉的生活与图论历在欧拉的生活与图论历史中扮演着非常重要角色。因为它，产生了著名的欧拉史中扮演着非常重要角色。因为它，产生了著名的欧拉图定理，因为它，产生了图论。图定理，因为它，产生了图论。注：注：一笔画一笔画-中国中国古老的古老的民间游戏民间游戏 要求：对于一个图要求：对于一个图G,G,笔不离纸笔不离纸,一笔画成一笔画成.(2)、欧拉图概念、欧拉图概念 定义定义1 对于连通图对于连通图G，如果，如果G中存在经过每条边的闭中存在经过每条边的闭迹，则称迹，则称G为欧拉图，简称为欧拉图，简称G为为E图。欧拉闭迹又称为图。欧拉闭迹又称为欧拉环游，或欧拉回路。欧拉环游，或欧拉回路。欧拉图41324132非欧拉图有欧拉迹非欧拉图无欧拉迹12345第5页，本讲稿共33页 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中至少存在圈中至少存在圈C1,从从G中去掉中去掉C1中的边，得到中的边，得到G的生成的生成6第6页，本讲稿共33页子图子图G1,若若G1没有边，则没有边，则(3)成立。否则，成立。否则，G1的每个非平的每个非平凡分支是度数为偶数的连通图，于是又可以抽取一个圈。凡分支是度数为偶数的连通图，于是又可以抽取一个圈。反复这样抽取，反复这样抽取，E(G)最终划分为若干圈。最终划分为若干圈。(3)(1)设设C1是是G的边划分中的一个圈。若的边划分中的一个圈。若G仅由此圈组成，仅由此圈组成，则则G显然是欧拉图。显然是欧拉图。否则，由于否则，由于G连通，所以，必然存在圈连通，所以，必然存在圈C2,它和它和C1有公有公共顶点。于是，共顶点。于是，C1CC2 2是一条含有是一条含有C C1 1与与C C2 2的边的欧拉闭的边的欧拉闭迹，如此拼接下去，得到包含迹，如此拼接下去，得到包含G G的所有边的一条欧拉闭的所有边的一条欧拉闭迹。即证迹。即证G G是欧拉图。是欧拉图。推论推论1 连通图连通图G是欧拉图当且仅当是欧拉图当且仅当G的顶点度数为偶。的顶点度数为偶。推论推论2 连通非欧拉图连通非欧拉图G存在欧拉迹当且仅当存在欧拉迹当且仅当G中只有两中只有两个顶点度数为奇数。个顶点度数为奇数。7第7页，本讲稿共33页 例例1 下面图中谁是欧拉图？谁是非欧拉图但存在欧拉下面图中谁是欧拉图？谁是非欧拉图但存在欧拉迹？谁是非欧拉图且不存在欧拉迹？迹？谁是非欧拉图且不存在欧拉迹？G1G2G3 解：解：G1是欧拉图；是欧拉图；G2是非欧拉图，但存在欧拉迹；是非欧拉图，但存在欧拉迹；G3中中不存在欧拉迹。不存在欧拉迹。例例2 证明：若证明：若G和和H是欧拉图，则是欧拉图，则 是欧拉图。是欧拉图。8第8页，本讲稿共33页 证明：首先证明：对任意证明：首先证明：对任意u V(G),v V(H),有：有：事实上，设事实上，设z是是u的任意一个邻点，一定有的任意一个邻点，一定有(u,v)的一个的一个邻点邻点(z,v),反之亦然。同理，对于反之亦然。同理，对于v的任意一个邻点的任意一个邻点w，一，一定有定有(u,v)的一个邻点的一个邻点(u,w),反之亦然。即反之亦然。即:(u,v)在乘积在乘积图中邻点个数等于图中邻点个数等于u在在G中邻点个数与中邻点个数与v在在H中邻点个数之中邻点个数之和。和。所以，所以，G,H是欧拉图，那么是欧拉图，那么 顶点度数为偶数。顶点度数为偶数。其次证明：其次证明：是连通的。是连通的。由于由于G,H都是欧拉图，所以都连通。设最短的都是欧拉图，所以都连通。设最短的(u1,u2)路路9第9页，本讲稿共33页最短的最短的(v1,v2)路分别为：路分别为：那么，由乘积图的定义：在乘积图中有路：那么，由乘积图的定义：在乘积图中有路：这样，我们证明了这样，我们证明了 是连通的且每个顶点度数为偶是连通的且每个顶点度数为偶数。即它是欧拉图。数。即它是欧拉图。(二二)、Fleury算法算法 该算法解决了在欧拉图中求出一条具体欧拉环游的方该算法解决了在欧拉图中求出一条具体欧拉环游的方法。方法是尽可能避割边行走。法。方法是尽可能避割边行走。1、算法算法 (1)、任意选择一个顶点任意选择一个顶点v0,置置w0=v0;10第10页，本讲稿共33页 (2)、假设迹假设迹wi=v0e1v1eivi已经选定，那么按下述方已经选定，那么按下述方法从法从E-e1,e2,ei中选取边中选取边ei+1:1)、ei+1与与vi+1相关联；相关联；2)、除非没有别的边可选择，否则、除非没有别的边可选择，否则 ei+1不能是不能是 Gi=G-e1,e2,ei的割边。的割边。(3)、当当(2)不能执行时，算法停止。不能执行时，算法停止。例例3 在下面欧拉图在下面欧拉图G中求一条欧拉回路。中求一条欧拉回路。dcbafeg图Ghji11第11页，本讲稿共33页 解：解：dcbafeg图Ghji 例例4 某博物馆的一层布置如下图，其中边代表走廊，某博物馆的一层布置如下图，其中边代表走廊，结点结点e是入口，结点是入口，结点g是礼品店，通过是礼品店，通过g我们可以离开博物我们可以离开博物馆。请找出从博物馆馆。请找出从博物馆e进入，经过每个走廊恰好一次，最进入，经过每个走廊恰好一次，最后从后从g处离开的路线。处离开的路线。afedcbihgj12第12页，本讲稿共33页 解：图中只有两个奇度顶点解：图中只有两个奇度顶点e和和g,因此存在起点为因此存在起点为e,终终点为点为g的欧拉迹。的欧拉迹。为了在为了在G中求出一条起点为中求出一条起点为e,终点为终点为g的欧拉迹，在的欧拉迹，在e和和g间添加一条平行边间添加一条平行边mafedcbihgjm 用用Fleury算法求出欧拉环游为：算法求出欧拉环游为：emgcfabchbdhgdjiejge 所以：解为：所以：解为：egjeijdghdbhcbafcg13第13页，本讲稿共33页 证明：令证明：令Wn=v0e1v1envn为由为由Fleury算法得到的一条算法得到的一条G中迹。中迹。定理定理1 若若G是欧拉图，则是欧拉图，则G中任意用中任意用Fleury算法作出的算法作出的迹都是迹都是G的欧拉环游。的欧拉环游。2、算法证明、算法证明 由由Fleury算法，算法，dGn(vn)=0,所以，所以，vn=v0，否则否则，dGn(vn)为奇为奇 设设Wn 不是不是G的欧拉环游，于是可令：的欧拉环游，于是可令：容易知道：容易知道：14第14页，本讲稿共33页 令令vm是是Wn在在S中的最后一个顶点。中的最后一个顶点。vmvm+1vn 首先，首先，中边一定都是中边一定都是Wn中边。若不然，设中边。若不然，设 设设e=uv,u S,那么，那么，dGn(v)0,矛盾！矛盾！其次，由其次，由vm是是Wn在在S中的最后一个顶点，知：中的最后一个顶点，知：15第15页，本讲稿共33页 即即em+1是是Gm的割边。的割边。设设e是是Gm中与中与vm关联的另外一条边。那么，由关联的另外一条边。那么，由F算法，它算法，它必然为必然为GmS的割边。的割边。但是，但是，GmS=GnS,所以，所以，GmS中每个点为偶数，从中每个点为偶数，从而没有割边，矛盾！而没有割边，矛盾！vmvm+1vne 3、算法复杂性分析、算法复杂性分析16第16页，本讲稿共33页 设设G=(n,m)是欧拉图是欧拉图 由由Fleury算法知：算法需要算法知：算法需要m次循环；次循环；算法中主要运算是判断：算法中主要运算是判断：，该判，该判断的时间复杂性是断的时间复杂性是n2数量级的。数量级的。所以所以Fleury算法时间复杂性是：算法时间复杂性是：O(n2m),是好算法。是好算法。例例4 证明：若证明：若G有有2k0个奇数顶点，则存在个奇数顶点，则存在k条边不重条边不重的迹的迹Q1,Q2,Qk，使得：，使得：证明：不失一般性，只就证明：不失一般性，只就G是连通图进行证明。是连通图进行证明。17第17页，本讲稿共33页 设设G=(n,m)是连通图。令是连通图。令vl，v2，,vk,vk+1,v2k是是G的所的所有奇度点。有奇度点。在在vi与与vi+k间连新边间连新边ei得图得图G*（1ik).ik).则则G*G*是欧拉图，是欧拉图，因此，由因此，由FleuryFleury算法得欧拉环游算法得欧拉环游C.C.在在C中删去中删去ei（1ik).得得k条边不重的迹条边不重的迹Qi（1ik):例例5 设设G是非平凡的欧拉图，且是非平凡的欧拉图，且v V(G)。证明：。证明：G的每条具有起点的每条具有起点v的迹都能扩展成的迹都能扩展成G的欧拉环游当且仅当的欧拉环游当且仅当G-v是森林。是森林。证明：证明：“必要性必要性”若不然，则若不然，则G-v有圈有圈C。18第18页，本讲稿共33页 考虑考虑G1=G-E(G)的含有顶点的含有顶点v的分支的分支H。由于由于G是非平凡欧拉图，所以是非平凡欧拉图，所以G1的每个顶点度数为偶数，的每个顶点度数为偶数，从而，从而，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有有圈，这与条件矛盾圈，这与条件矛盾.19第19页，本讲稿共33页(三三)、中国邮路问题、中国邮路问题 1962年，中国数学家管梅谷提出并解决了年，中国数学家管梅谷提出并解决了“中国邮路问题中国邮路问题”1、问题、问题 邮递员派信的街道是边赋权连通图。从邮局出发，每条街道邮递员派信的街道是边赋权连通图。从邮局出发，每条街道至少行走一次，再回邮局。如何行走，使其行走的环游路程最至少行走一次，再回邮局。如何行走，使其行走的环游路程最小？小？如果邮路图本身是欧拉图，那么由如果邮路图本身是欧拉图，那么由Fleury算法，可得到他的算法，可得到他的行走路线。行走路线。如果邮路图本身是非欧拉图，那么为得到行走环游，必须重如果邮路图本身是非欧拉图，那么为得到行走环游，必须重复行走一些街道。于是问题转化为如何重复行走街道？复行走一些街道。于是问题转化为如何重复行走街道？20第20页，本讲稿共33页 2、管梅谷的结论、管梅谷的结论 定理定理2 若若W是图是图G中一条包含所有边的闭途径，则中一条包含所有边的闭途径，则W在在这样的闭途径中具有最短的长度当且仅当下列两个条件被这样的闭途径中具有最短的长度当且仅当下列两个条件被满足：满足：(1)每一条边最多重复经过一次；每一条边最多重复经过一次；(2)在在G的每一个圈上，重复经过的边的条数不超过圈长的每一个圈上，重复经过的边的条数不超过圈长的一半。的一半。证明：证明：“必要性必要性”首先，设首先，设G是连通非欧拉图，是连通非欧拉图，u与与v是是G的两个奇度顶点，的两个奇度顶点，把连接把连接u与与v的路上的边改为的路上的边改为2重边，则路中的点的度数奇偶性重边，则路中的点的度数奇偶性没有改变，仍然为偶数，但没有改变，仍然为偶数，但u与与v的度数由奇数变成了偶数。的度数由奇数变成了偶数。如果对如果对G中每对奇度点都如此处理，则最终得到的图为欧拉中每对奇度点都如此处理，则最终得到的图为欧拉图。设该图为图。设该图为G1.21第21页，本讲稿共33页 其次，对其次，对G1作修改：作修改：如果在如果在G1中，边中，边e重复数大于重复数大于2，则在则在G G1 1中删掉中删掉2 2条重复的条重复的e e边后，所得之图仍然是包含边后，所得之图仍然是包含G G的欧拉图。的欧拉图。在在G1中，对每组平行边都做上面的处理，最后得到一个重中，对每组平行边都做上面的处理，最后得到一个重复边数最多为复边数最多为1的包含的包含G的欧拉图的欧拉图G2。这说明，若这说明，若W是包含是包含G的所有边的欧拉环游，则的所有边的欧拉环游，则G中每条中每条边至多在边至多在W里出现两次。这就证明了里出现两次。这就证明了(1).又设又设C是是G2中任意一个圈，在该圈中，如果有平行边条数中任意一个圈，在该圈中，如果有平行边条数超过该圈长度的一半，那么可以把该圈中平行边改为非平行超过该圈长度的一半，那么可以把该圈中平行边改为非平行边，而把非平行边改为平行边，如此修改，得到的图仍然是边，而把非平行边改为平行边，如此修改，得到的图仍然是包含包含G的欧拉图，但对应的欧拉环游长度减小了。的欧拉图，但对应的欧拉环游长度减小了。22第22页，本讲稿共33页 这就是说，只要对这就是说，只要对G2的每个圈都作上面的修改，最后得到的每个圈都作上面的修改，最后得到的图仍然为包含的图仍然为包含G的欧拉图，而最后的图正好满足的欧拉图，而最后的图正好满足(2).“充分性充分性”我们证明：任何两条包含我们证明：任何两条包含G中所有边的闭途径中所有边的闭途径W1与与W2,如果满足定理如果满足定理2的两个条件，则它们有相同的长度。的两个条件，则它们有相同的长度。设设Y1与与Y2分别表示分别表示W1与与W2中重复出现的边集合。中重复出现的边集合。如果能够证明：如果能够证明：|Y1-Y2|=|Y2-Y1|,那么那么d(W1)=d(W2).断言断言1：GY的每个顶点度数必然为偶数。的每个顶点度数必然为偶数。令：令：Y=(Y1-Y2)(Y2-Y1)首先：对于首先：对于G中任意点中任意点v,如果如果d G(v)是奇数，那么是奇数，那么Y1与与Y2中与中与v关联的边数均为奇数；关联的边数均为奇数；23第23页，本讲稿共33页 如果如果d G(v)是偶数，那么是偶数，那么Y1与与Y2中与中与v关联的边数均为偶关联的边数均为偶数。数。所以所以Y1与与Y2中与中与G中任意点关联的边数奇偶性相同。中任意点关联的边数奇偶性相同。其次，设其次，设Y1与与Y2中与中与v关联的边数分别为关联的边数分别为y1与与y2,其中相其中相同的边数为同的边数为y0，那么，那么，Y中与中与v关联的边数为：关联的边数为：所以，所以，Y中与中与v关联的边数为偶数，说明关联的边数为偶数，说明 GY的每个顶点的每个顶点度数必然为偶数。度数必然为偶数。断言断言2：|Y1-Y2|=|Y2-Y1|由于由于GY的每个顶点度数为偶数。所以，它的每个分支的每个顶点度数为偶数。所以，它的每个分支是欧拉图。因此，是欧拉图。因此，GY可以作不重圈分解。可以作不重圈分解。24第24页，本讲稿共33页 由定理由定理2的条件的条件(2),Y1与与Y2在圈中的边数不能超过圈长的在圈中的边数不能超过圈长的一半，但圈中边不是属于一半，但圈中边不是属于Y1就是属于就是属于Y2,所以，在每个圈中，所以，在每个圈中，Y1-Y2与与Y2-Y1中边各占一半，即：中边各占一半，即：由此，证明了定理的充分性。由此，证明了定理的充分性。注注:(1)定理定理2的必要性证明过程实际上给出了求中国邮路的必要性证明过程实际上给出了求中国邮路问题的方法问题的方法.下面看一个例题。下面看一个例题。例例5 求包含下图求包含下图G的一个最优欧拉环游。的一个最优欧拉环游。25第25页，本讲稿共33页 解：由定理解：由定理2：v8v7v6v5v4v3v2v1v12v11v10v9Gv15v14v13v8v7v6v5v4v3v2v1v12v11v10v9Gv15v14v1326第26页，本讲稿共33页 修改后得：修改后得：v8v7v6v5v4v3v2v1v12v11v10v9Gv15v14v13 由由Fleury算法得可得到具体的最优欧拉环游。算法得可得到具体的最优欧拉环游。3、非负权值的赋权图的最优欧拉环游、非负权值的赋权图的最优欧拉环游27第27页，本讲稿共33页 对于一般的具有非负权值的赋权图对于一般的具有非负权值的赋权图G来说，如何求一条来说，如何求一条包含包含G的边的最优欧拉环游？的边的最优欧拉环游？其实，可以证明：一般问题和中国邮路问题的特殊情况其实，可以证明：一般问题和中国邮路问题的特殊情况是等价的是等价的(定理定理2).也就是说：可以通过定理也就是说：可以通过定理2的求最优欧拉的求最优欧拉环游的方法来求一般情况下的最优欧拉环游。环游的方法来求一般情况下的最优欧拉环游。所以，求一般非负权赋权图的最优欧拉环游步骤为：所以，求一般非负权赋权图的最优欧拉环游步骤为：(1)、用添加重复边的方法求、用添加重复边的方法求G的一个赋权母图的一个赋权母图G*，使：，使：(2)、用、用Fleury算法在算法在G*中求出欧拉环游。中求出欧拉环游。28第28页，本讲稿共33页 注：步骤注：步骤(1)的好算法已经由的好算法已经由Edmons在在1973年给出。年给出。例例6 如果一个非负权的边赋权图如果一个非负权的边赋权图G中只有两个奇度顶点中只有两个奇度顶点u与与v,设计一个求其最优欧拉环游的算法。设计一个求其最优欧拉环游的算法。解：解：1、算法算法 (1)、在在u与与v间求出一条最短路间求出一条最短路P;(最短路算法最短路算法)(2)、在最短路在最短路P上，给每条边添加一条平行边得上，给每条边添加一条平行边得G的欧的欧拉母图拉母图G*;(3)、在在G的欧拉母图的欧拉母图G*中用中用Fleury算法求出一条欧拉算法求出一条欧拉环游。环游。2、算法证明算法证明29第29页，本讲稿共33页 定理：用上面方法求出的欧拉环游是最优欧拉环游。定理：用上面方法求出的欧拉环游是最优欧拉环游。证明：设证明：设u与与v是是G的两个奇度顶点的两个奇度顶点,G*是是G的任意一个欧的任意一个欧拉母图。拉母图。考虑考虑G*E*-E,显然它只有两个奇数顶点显然它只有两个奇数顶点u与与v,当然它们当然它们必须在必须在G*E*-E的同一个分支中，因此，存在的同一个分支中，因此，存在(u,v)路路P*.所以，所以，即证明定理。即证明定理。例如：求出下图的一条最优欧拉环游。例如：求出下图的一条最优欧拉环游。30第30页，本讲稿共33页 解：解：y222211u43365wxvGzy222211u43365wxvGz 最优欧拉环游：最优欧拉环游：x u y w v z w y x u w v x z y x31第31页，本讲稿共33页 作业 P97-99 习题4：1,2,3,7,8,932第32页，本讲稿共33页Thank You!33第33页，本讲稿共33页