离散数学课件第八章(第4讲).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,8.5,特殊的图,欧拉图,汉密尔顿图,平面图,对偶图,欧拉图,哥尼斯堡七桥问题：,18,世纪在哥尼斯堡城,(,今俄罗斯加里宁格勒,),的普莱格尔河上有,7,座桥，将河中的两个岛和河岸连结，如下图所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍,7,座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。,于是“七桥问题”就等价于上图能否一笔画成的问题。,欧拉提出不存在一次走遍,7,座桥，而每座桥只许通过一次的走法。,陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成,4,个结点，,7,座桥表示成,7,条连接这,4,个结点的边，如下图所示。,定义,1,：给定无孤立结点图,G,，若存在一条路，经过图中每边一次且仅一次，该条路称为,欧拉路。,定义,2,：给定无孤立结点图,G,，若存在一条回路，经过图中每边一次且仅一次，该回路称为,欧拉回路,。具有欧拉回路的图称为,欧拉图,。,v,2,v,3,v,4,v,1,（,V,1,、,V,2,、,V,3,、,V,1,、,V,4,、,V,3,）是一条欧拉路,定理,1,：给定无向连通图,G,，,G,是欧拉图，当且仅当图中每个结点都是,偶数度,结点。,定理,2,：无向图连通图,G,有一条欧拉路，当且仅当,G,有,零个,或,两个奇数度,结点。,v,2,v,3,v,4,v,1,例：,证明：,n,阶完全无向图,K,n,是欧拉图当且仅当,n,为奇数。,证：,n,阶完全无向图,K,n,是连通图且每个节点的度数均为,n-1,，于是,K,n,是欧拉图当且仅当,n-1,是偶数，即,n,为奇数。,例：,从图中找一,条欧拉路。,解,：有两个奇数度结点,:v,1,和,v,4,，所以存在欧拉路。,L=v,1,v,2,v,3,v,4,v,5,v,2,v,4,是一条欧拉路。,定理,3,：有向图,G,为欧拉图，当且仅当,G,是连通的，且每个结点入度等于出度。,定理,4,：一个有向图,G,中具有 欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度小,1,，一个结点的入度比出度大,1,。,欧拉回路问题既是一个有趣的游戏问题,又是一个有实用价值的问题。,邮递员一般的邮递路线是需要遍历某些特定的街道,理想地,他应该走一条欧拉路,即不重复地走遍图中的每一条边。,有的邮递任务是联系某些特定的收发点,不要求走遍每一条边,只要求不重复地遍历图中的每一个顶点,此时感兴趣的是图中的顶点,这就是下面研究的汉密尔顿图。,汉密尔顿图,1859,年,爱尔兰数学家汉密尔顿,(,Halmiton),提出一个“周游世界”的游戏,它把图,(,a),所示的正十二面体的二十个顶点当作是地球上的二十个城市,要求旅游者从某个城市出发,沿棱,走过每个城市一次且仅一次,最后回到出发点,。,(,b),图中粗线所构成的回路就是问题的答案。,a,b,定义,1,：给定图,G,，若存在一条通路，经过图中的每个结点恰好一次，这条通路称作汉密尔顿路。,定义,2,：给定图,G,，若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图。,例：,(a),存在汉密尔顿回路,(a),是汉密尔顿图。,(b),存在汉密尔顿通路但不存在汉密尔顿回路,(b),不是汉密尔顿图。,(c),不存在汉密尔顿通路且不存在汉密尔顿回路,(,c),不是汉密尔顿图。,（,a,）,（,b,）,（,c,）,练习：,一只小蚂蚁可否从立方体的一个顶点出发，沿着棱爬行，,它爬过每一个顶点一次且仅一次，最后回到原出发点？,例：,证明：若一个无向图,G=(V,，,E),存在一个节点,v,使得,deg(v)=1,，则,G,不是汉密尔顿图。,证,:,因为图,G,的汉密尔顿回路要经过节点,v,，这是显然,deg(v),2,，故,G,不是汉密尔顿图。,定理,1,：,若图,G=,为汉密尔顿图，则对于结点集,V,的每个非空子集,S(,真子集,S,),有：,W(G-S),|S|,成立，其中,W(G-S),是,G-S,中的连通分支数。,(,必要条件,),。,v,1,v,2,v,7,v,3,v,5,v,8,v,4,v,6,v,2,v,7,v,3,v,5,v,8,v,6,定理,2,：,设图,G,是有,n,个结点的简单无向图，若,G,中任意两个结点度数之和大于等于,n,，则,G,是 汉密尔顿图。（这是,充分条件，,但不是,必要条件,）,（,a,）,（,b,）,欧拉图和汉密尔顿图之间的区别：,(1),欧拉回路是,简单回路,而汉密尔顿图回路是,基本回路,。,简单回路：,各边都不相同的回路。,基本回路：,除终点与始点外，其它结点都不相同的回路。,(2,),欧拉图,遍历边,而,汉密尔顿,图,遍历顶点,。,平面图,例：,K,3,3,图如下，试问：能否转变成与其等价的，且使得任何两条边除了端点外没有其它的交点的平面上的图？,4,5,6,定义,1,：设,G=,是一个无向图，如果能够把,G,的所有结点和边画在平面上，且使得任何两条边除了端点外没有其它的交点，就称,G,是一个平面图。,判断一个图是否为平面图的简单方法是观察法：,找出基本循环，将交叉的边分别放置在基本循环内或外而避免交叉。如下图所示：,但并非所有的图经过处理之后都可变为平面图。,定义,2,：设,G,是一连通平面图，由图中的边所包围的区域，且在该区域内既不包含图的结点，也不包含图的边，这样的区域称为,G,的,面,。,包围一个面的诸边称为此面的边界。,面的面积为有限者称为有限面，面的面积为无限者称为无限面。,例：,为有限面,为无限面,定义,3,：一个面的边界的回路长度称作是该面的次数，记为：,deg(r),定理,1,：一个有限平面图，面的次数之和等于其边数的两倍。,证明：对于,G,中的每一条边,e,，,e,或是两个面的公共边，或是在一个面中为悬挂边被作为边界计算两次，故定理成立。,定理,2,：,(,欧拉定理,),设图,G,是一个,n,个结点,m,条边的连通平面图，它的面数为,r,，则有欧拉公式：,n,m,r,2,。,证明,:,用归纳法,m,=0,时，,G,为平凡图，,n,=1,，,r,=1,，公式成立。,设,m,=,k,-1,（,k,1,）时公式成立，现在考虑,m,=,k,时的情况。因为在连通图上增加一条边仍为连通图，则有三种情况：,（,1,）所增边为悬挂边，此时,G,的面数不变，顶点数增,1,，公式成立。,（,2,）在图的任意两个不相邻点间增加一条边，此时,G,的面数增,1,，边数增,1,，但顶点数不变，公式成立。,（,3,）所增边为一个环，此时,G,的面数增,1,，边数增,1,，但顶点数不变，公式成立。,练习：,在由,6,个结点，,12,条边构成的连通简单平面图中，每个面由几条边围成？,定理,3,:,设,G,是一个包含,n,个结点,m,条边的连通简单平面图，,且每个面的次数至少为,l,（,l,3,），则,于是有,故,证明,:,由定理,1,(,r,为,G,的面数,),再由欧拉公式,n,-,m,+,r,=2,推论,1,:,设图,G,是一个包含,n,个结点,m,条边的连通简单平面图，若,n3,则,m3n-6,。,证明：由于,G,是,n,3,的简单连通平面图，所以,G,的每个面至少由,3,条边围成，即,l,3,，由定理,3,得,m,3,n,-6.,推论,1,给出了平面图的必要条件，若不满足这些条件，则一定不是平面图。,例：,K,5,图不是平面图。,例：证明当每个结点的度数大于等于,3,时，不存在,7,条边的连通简单平面图。,证,：,(,反证,),：,设,G,是,(n,，,m),图，若,m=7,，根据推论,1,知，,m,3n-6,，即,7,3n-6,，于是,3n,13,。根据握手定理，有,即,3n,14,。这与,3n,13,矛盾。,练习：,(1),设,G,是包含,n,个结点,(n3),m,条边的连通简单平面图，证明,G,中至少有一个结点的度数小于等于,5,。,(2),设,G,是包含,n,个结点,(n3),边数,m,小于,30,的连通简单平面图，证明,G,中存在结点,v,d(v)4,。,推论,2,:,若连通简单平面图,G,不以,K,3,为子图，则,m,2,n-,4,。,证明,:,由于,G,中不含,K,3,，所以,G,的每个面至少由,4,条边围成，即,l,4,，代入定理,3,，得,m,2,n,-4.,例：证明,K,5,和,K,3,，,3,是非平面图。,证明,:,假设,K,5,是平面图，由推论,1,可知应有,m,3,n,-6,，而当,n,=5,，,m,=10,时，这是不可能的，所以,K,5,是非平面图。,假设,K,3,，,3,是平面图，因其不含子图,K,3,，由推论,2,可 知，当,n,=6,，,m,=9,时，,m,2,n,-4,是不可能的，所以,K,3,，,3,是非平面图。,(2),若,e,是,G,中两个不同面,R,i,和,R,j,的公共边，则存在且仅存在一条边,e*,k,G*,与,e,相交；,(3),若,e,是一个面,R,i,内的边，则在,G*,中有一条与,e,交叉的环。,则称,G*,为,G,的对偶图，,G*,与,G,互为对偶图。,定义,设平面图,G=V,E,有,r,个面,R,1,，,R,2,，,，,R,r,，若有图,G,*,=V,*,E,*,满足下述条件：,(1),R,i,G,，内部有且仅有一个结点,v*,i,V,*,，,i=1,，,2,，,，,r,。,1.,对偶图,对偶图,例,:,图（,a,）和（,b,）中，,G*,是,G,的对偶图，,G,的边用实线表示，,G*,的边用虚线 表示。,（,a,）,（,b,）,2.,着色问题,在地图上，相邻国家涂不同的颜色，最少需要多少种颜色？,100,多年前，有人提出了,“,四色猜想,”,，即只用四种颜色就能做到，但一直无法证明，直到,1976,年美国数学家才用电子计算机证明了这一猜想。,地图着色自然是对平面图的面着色，利用对偶图，可将其转化为相对简单的顶点着色问题，即对图中相邻的顶点涂不同的颜色。,韦尔奇,鲍威尔（,WelchPowell,）给出了一种对图的着色方法，步骤如下：,（,1,）将图,G,中的顶点按度数递减次序排列。,（,2,）用第一种颜色对第一顶点着色，并将与已着色顶点不邻接的顶点也着第一种颜色。,（,3,）按排列次序用第二种颜色对未着色的顶点重复（,2,）。用第三种颜色继续以上做法，直到所有的顶点均着上色为止。,例,:,用韦尔奇,鲍威尔法对下图着色。,（,1,）各顶点按度数递减次序排列：,c,，,a,，,e,，,f,，,b,，,h,，,g,，,d,。,（,2,）对,c,和与,c,不邻接的,e,，,b,着第一种颜色。,（,3,）对,a,和与,a,不邻接的,g,，,d,着第二种颜色。,（,4,）对,f,和与,f,不邻接的,h,着第三种颜色。,