图论课件-平面图的判定与涉及平面性的不变量.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论及其应用,应用数学学院,1,本次课主要内容,(,一,),、平面图的判定,(,二,),、涉及平面性的不变量,平面图的判定与涉及平面性的不变量,2,这次课要解决的问题是：给出判定一个图是否是可平面图的充分必要条件一,),、平面图的判定,在本章第一次课中，我们已经明确：对于,3,阶以上的具有,m,条边的图,G,来说，如果,G,满足如下条件之一：,(1)m3n-6;(2)K,5,是,G,的一个子图；,(3)K,3,3,是,G,的一个子图，那么，,G,是非可平面图但上面的条件仅为,G,是非可平面图的充分条件最早给出图的平面性判定充要条件的是波兰数学家库拉托斯基,(30,年代给出,),后来，美国数学家惠特尼，加拿大数学家托特，我国数学家吴文俊等都给出了不同的充要条件3,所以，我们称,K,5,与,K,3,3,为库拉托斯基图我们主要介绍波兰数学家库拉托斯基的结果库拉托斯基定理主要基于,K,5,和,K,3,3,是非可平面图这一事实而提出的平面性判定方法一个自然的猜测是：,G,是可平面图的充分必要条件是,G,不含子图,K,5,和,K,3,3,。

上面命题必要性显然成立！但充分性能成立吗？,十分遗憾！下面例子给出了回答：,NO!,下面的图,G,是一个点数为,5,，边数为,9,的极大平面图考虑,F=GK,3,4,注：,F,由,G,的,3,个拷贝组成，分别是,G,1,G,2,G,3,三个拷贝中的边没有画出图中虚线不是对应的,G,i,中边G,u,5,u,4,u,3,u,2,u,1,v,5,v,4,v,3,v,2,v,1,w,5,w,4,w,3,w,2,w,1,G,3,G,2,G,1,5,可以证明：,F,中不含,K,5,和,K,3,3,，且,F,是非可平面图尽管我们的直觉猜测错了，但库拉托斯基还是基于,K,5,与,K,3,3,得到了图的平面性判据1,、相关概念,定义,1,在图,G,的边上插入一个,2,度顶点，使一条边分成两条边，称将图在,2,度顶点内扩充；去掉一个图的,2,度顶点，使关联它们的两条边合并成一条边，称将图,G,在,2,度顶点内收缩在,2,度顶点内收缩,在,2,度顶点内扩充,6,定义,2,两个图,G,1,与,G,2,说是同胚的，如果 ，或者通过反复在,2,度顶点内扩充和收缩后能够变成一对同构的图G,3,G,2,G,1,上面的,G,1,G,2,G,3,是同胚的。

注：图的平面性在同胚意义下不变7,定理,1(,库拉托斯基定理,),图,G,是可平面的，当且仅当它不含,K,5,或,K,3,3,同胚的子图例,1,求证：下面两图均是非平面图图,G,1,图,G,2,证明：对于,G,1,来说，按,G,1,在,2,度顶点内收缩后，可得到,K,5,所以，由库拉托斯基定理知,G,1,是非可平面图8,对于,G,2,来说，先取如下子图,G,2,的一个子图,对上面子图，按,2,度顶点收缩得与之同胚子图,K,3,3,:,K,3,3,所以，,G,2,是非可平面图9,例,2,确定下图是否是可平面图u,1,u,2,v,1,v,2,y,1,y,2,x,1,x,2,w,1,w,2,分析：我们根据图的结构形式，怀疑该图是非可平面图但我们必须找到证据！,当然我们可能考虑是否,m3n-6,遗憾的是该图不满足这个不等式！,10,u,1,u,2,v,1,v,2,y,1,y,2,x,1,x,2,w,1,w,2,所以，我们要在该图中寻找一个与,k,5,或,K,3,3,同胚的子图！,由于该图的最大度为,4,的顶点才,4,个，所以，不存在与,K,5,同胚的子图因此，只有寻找与,K,3,3,同胚的子图！,解：取,G,中红色边的一个导出子图：,也就是得到,G,的如下形式的一个子图：,11,上图显然和,K,3,3,同胚。

由库拉托斯基定理知，,G,是非可平面的u,1,u,2,v,1,v,2,y,1,y,2,x,1,x,2,w,1,w,2,注：,(1),库拉托斯基定理可以等价叙述为：,库拉托斯基定理：图,G,是非可平面的，当且仅当它含有,K,5,或,K,3,3,同胚的子图12,(2),库拉托斯基,(1896-1980),波兰数学家1913,年开始在苏格兰格拉斯哥大学学习工程学，,1915,年回到波兰发沙大学转学数学，主攻拓扑学1921,年获博士学位1930,年在利沃夫大学作数学教授期间，发现并证明了图论中的库拉托斯基定理1939,年后到发沙大学做数学教授他的一生主要研究拓扑学与集合论库拉托斯基定理：图,G,是非可平面的，当且仅当它含有,K,5,或,K,3,3,同胚的子图定义,2,给定图,G,去掉,G,中的环，用单边代替平行边而得到的图称为,G,的基础简单图13,定理,2 (1),图,G,是可平面的，当且仅当它的基础简单图是可平面的；,(2),图,G,是可平面图当且仅当,G,的每个块是可平面图证明：,(1),由平面图的定义，该命题显然成立2),必要性显然下面证明充分性不失一般性，假设,G,连通我们对,G,的块数,n,作数学归纳证明。

当,n=1,时，由条件，结论显然成立；,设当,nk,时，若,G,的每个块是可平面的，有,G,是可平面的下面考虑,n=k,时的情形14,设点,v,是,G,的割点，则按照,v,，,G,可以分成两个边不重子图,G,1,与,G,2,即,G=G,1,G,2,且,G,1,G,2,=,v,v,G,2,G,1,按归纳假设，,G,1,与,G,2,都是可平面图取,G,1,与,G,2,的平面嵌入满足点,v,都在外部面边界上，则把它们在点,v,处对接后，将得到,G,的平面嵌入即证,G,是可平面图关于图的可平面性刻画，数学家瓦格纳,(Wangner),在,1937,年得到了一个定理15,定义,3,设,uv,是简单图,G,的一条边去掉该边，重合其端点，在删去由此产生的环和平行边这一过程称为图,G,的初等收缩或图的边收缩运算称,G,可收缩到,H,是指对,G,通过一系列边收缩后可得到图,H,定理,2(,瓦格纳定理,),：简单图,G,是可平面图当且仅当它不含有可收缩到,K,5,或,K,3,3,的子图注：这是瓦格纳,1937,年在科隆大学博士毕业当年提出并证明过的一个定理16,例,3,求证彼得森图是非可平面图证明：很明显，彼得森图通过一些列边收缩运算后得到,K,5,。

由瓦格纳定理得证定理,3,至少有,9,个顶点的简单可平面图的补图是不可平面的，而,9,是这个数目中的最小的一个17,注：该定理是由数学家巴特尔、哈拉里和科达马首先得到然后由托特,(1963),给出了一个不太笨拙的证明，他采用枚举法进行验证还不知道有简洁证明，也没有得到推理方法证明例,4,找出一个,8,个顶点的可平面图，使其补图也是可平面的7,6,5,4,3,2,1,8,G,7,6,5,4,3,2,1,8,G,的补,18,例,5,设,G,是一个简单图，若顶点数,n,11,则,G,与,G,的补图中，至少有一个是不可平面图,(,要求用推理方法,).,证明：设,G,是一个,n,阶可平面图，则：,所以：,考虑：,19,令,:,则：,所以，当,n,6.5,时，,f(n),单调上升而当,n=11,时：,所以，当,n,11,时，有：,即证明了简单可平面图,G,的补图是非可平面图20,例,6,设,G,i,是一个有,n,i,个点，,m,i,条边的图，,i=1,2,证明：若,G,1,与,G,2,同胚，则：,证明：设,G,1,经过,p,1,次,2,度顶点扩充，,p,2,次,2,度顶点收缩得到,H,1,G,2,经过,q,1,次,2,度顶点扩充，,q,2,次,2,度顶点收缩得到,H,2,使得：,又设,H,1,与,H,2,的顶点数分别为,n,1,*,和,n,2,*,边数分别为,m,1,*,与,m,2,*,。

那么：,21,所以：,而由 得：,所以：,(,二,),、涉及平面性的不变量,我们将要讨论的问题是：如何刻画一个非可平面图与平面图之间的差距只作简单介绍1,、图的亏格,22,环柄：边交叉处建立的“立交桥”通过它，让一条边经过“桥下”，而另一条边经过“桥上”，从而把两条边在交叉处分开环柄示意图,定义,4,若通过加上,k,个环柄可将图,G,嵌入到球面，则,k,的最小数目，称为,G,的亏格，记为：,(G),23,定理,4,对于一个亏格为,，,有,n,个顶点，,m,条边和,个面的多面体，有：,因多面体对应一个连通图，所以上面恒等式称为一般连通图的欧拉公式推论：设,G,是一个有,n,个点,m,条边，亏格为,的连通图，则：,24,证明,(3):,因为,G,的每个面是三角形，所以每条边是两个面的公共边，得：,3,=2m,于是由定理,4,得：,对于完全图的亏格曾经是一个长期的，有趣的，困难的和成功的努力1890,年希伍德提出如下猜想：,25,希伍德由推论,(1),证明了：,同时希伍德也证明了,(K,7,)=1.,1891,年，赫夫曼对,n=8-12,进行了证明；,1952,年，林格尔对,n=13,进行了证明；,记阶数,n=12s+r,1954,年，林格尔对,r=5,进行了证明；,1961-65,年，林格尔对,r=7,、,10,、,3,进行了证明；,26,1961-65,年，杨斯、台里等对,r=4,、,0,、,1,、,9,、,6,进行了证明；,1967-68,年，林格尔、杨斯对,r=2,、,8,、,11,进行了证明；,1968,年后，法国蒙特派列尔大学文学教授杰恩对,n=18,、,20,、,23,进行了证明,.,对于完全双图，结果由林格尔独立得到。

定理,5,设,m,n,是正整数，则：,27,2,、图的厚度,定义,5,若图,G,的,k,个可平面子图的并等于,G,，则称,k,的最小值为,G,的厚度，记为,定理,6 (1),若,则,：,(2),(3),对任意的单图,G=(n,m),有：,3,、图的糙度,28,定义,6,图,G,中边不相交的不可平面子图的最多数目称为,G,的糙度，记为：,定理,7,完全图的糙度由下式给出：,（,3,n,+119,并且,3,n,+19,r,+7,，其中,r,为面数）；,29,定义,8,将,G,画在平面上时相交的边对的最少数目称为,G,的,叉数，记为,定理,9,30,作业,P143-146,习题,5,：,6,，,7,，,8,，,11,、,12,31,Thank You!,32,。