图论ppt课件平面性算法

,单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论及其应用,应用数学学院,1,图论及其应用应用数学学院1,本次课主要内容,(,一,),、涉及算法的相关概念,(,二,),、平面性算法,平面性算法,2,本次课主要内容(一)、涉及算法的相关概念(二)、平面性算法平,关于图的平面性问题，我们建立了一些可平面性判定方法：,(,一,),、涉及算法的相关概念,(1),对于简单图,G=(n,m),，如果,m3n-6,，则,G,是非可平面的；,(2),对于连通图,G=(n,m),，如果每个面次数至少为,l,3,且,m(n-2),l,/(,l,-2),，则,G,是非可平面的；,(3),库拉托斯基定理：,G,是可平面的当且仅当,G,不含有与,K,5,或,K,3,3,同胚的子图；,(4),瓦格纳定理：,G,是可平面的当且仅当,G,不含有能够收缩成,K,5,或,K,3,3,的子图；,3,关于图的平面性问题，我们建立了一些可平面性判定方法,上面的方法，局限性很大。这次课我们将给出一个算法，其作用是：如果,G,非可平面，通过算法可以得到判定；如果,G,是可平面图，通过算法，可以给出一种平面嵌入形式。,定义,1,设,H,是,G,的一个子图，在,E(G)-E(H),中定义一个二元关系“,”:,(1)e,1,与,e,2,分别是,W,的始边和终边，且,(2)W,与,H,的内点不能相交。,容易验证：上面的关系是,E(G)-E(H),元间的等价关系。,4,上面的方法，局限性很大。这次课我们将给出一个算法，,定义,2,设,B,是,E(G)-E(H),关于二元关系“,”,的等价类在,G,中的边导出子图，则称,B,是,G,关于子图,H,的一座桥。桥与,H,的公共顶点称为桥,B,在,H,中的附着顶点。,例,1,在下图中，红色边在,G,中导出子图为,H,。求出,G,关于,H,的所有桥。,G,G,B,1,B,2,B,3,B,4,5,定义2 设B是E(G)-E(H)关于二元关系“,定义,3,设,H,是图,G,的可平面子图，是,H,的一种平面嵌入。若,G,也是可平面图，且存在,G,的一个平面嵌入 ，且：,称 是,G,容许的。,例,2,在,G,中，我们取红色边导出的子图为,H,并取,容易知道：是,G,容许的。,G,6,定义3 设H是图G的可平面子图，是H的一,例,3,在,G,中，我们取红色边导出的子图为,H,并取,容易知道：不 是,G,容许的。,定义,4,设,B,是,G,中子图,H,的任意一座桥，若,B,对,H,的所有附着顶点都位于 的某个面,f,的边界上，则称,B,在面,f,内可画入，否则，称,B,在面,f,内不可画入。,7,例3 在G中，我们取红色边导出的子图为H,并取,对于,G,的桥,B,令：,例,4,红色边的导出子图是,H,如果取 确定,H,的桥在 中可以画入的面集合。,B,3,B,2,B,1,f,3,f,2,f,1,G,解：,8,对于G的桥B,令：例4 红色边的导出子图是H,定理,1,设 是,G,容许的，则对于,H,的每座桥,B:,证明：因 是,G,容许的，由定义，存在,G,的一个平面嵌入 ，使得：,于是，,H,的桥,B,所对应的 的子图，必然限制在 的某个面内。所以：,注：定理,1,实际上给出了一个图是可平面图的一个必要条件。这个必要条件表明：如果存在,G,的一个可平面子图,H,9,定理1 设 是G容许的，则对于H的每,使得对于某桥,B,，有 ，那么，,G,是非可平面的。,根据上面的结论：我们可以按如下方式来考虑,G,的平面性问题：,先取,G,的一个可平面子图,H,1,其平面嵌入是,对于,H,1,的每座桥,B,如果：，则,G,非可平面。,否则，取,H,1,的桥,B,1,作：,H,2,=B,1,H,1,再取一个面,将,B,1,画入 的面,f,中。,10,使得对于某桥B，有,如果,B,1,可平面，则只要把,B,1,平面嵌入后，得到,H,2,的平面嵌入,然后再进行上面相同的操作，可以得到,G,的边数递增的子图平面嵌入序列：,最终，得到可平面图,G,的一种平面嵌入形式。,(,二,),、平面性算法,1964,年，,Demoucron,Mlgrance,和,Pertuiset,提出了下面的平面性算法，简称,DMP,算法。,11,如果B1可平面，则只要把B1平面嵌入后，得到H2的平,设,G,是至少三个顶点的简单块。,(1),取,G,的一个圈,H,1,求出,H,1,的一个平面嵌入 。置,i=1;,(2),若,E(G)-E(H,i,)=,则停止；否则，确定,G,中,H,i,的所有桥，并对每座桥,B,，求出 ；,(3),若存在桥,B,使得：，则停止,(G,不可平面,),；否则，在,H,i,的所有桥中确定一个使得 最小的,B,，并取 。,(4),在桥,B,中取一条连接,H,i,中两个附着顶点的路,P,i,置,H,i+1,=H,i,P,i,把,P,i,画在 的面,f,内,得到,12,设G是至少三个顶点的简单块。(1)取G的一,(5),置,i=i+1,转,(2),。,例,5,用平面性算法考察下图,G,的平面性。,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,图,G,解：,(1),取,G,的一个圈,H,1,并作平面嵌入：,13,(5)置i=i+1转(2)。例5 用平面性,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,图,G,(2),v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,H,1,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,f,1,f,2,14,v6v5v4v3v2v1v8v7图G (2)v6v5v,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,图,G,(3),取,B,1,和,f,1,.(4),取,P,1,=v,1,v,3,f,3,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,f,1,f,2,15,v6v5v4v3v2v1v8v7图G (3)取B1和,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,图,G,(3),取,B,2,和,f,3,.(4),取,P,2,=v,2,v,7,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,f,1,f,2,f,3,16,v6v5v4v3v2v1v8v7图G (3)取B2和,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,图,G,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,f,1,f,2,f,3,f,4,17,v6v5v4v3v2v1v8v7图Gv6v5v4v3v2v1,(3),取,B,1,和,f,1,.(4),取,P,3,=v,1,v,4,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,图,G,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,f,1,f,2,f,3,f,5,f,4,18,(3)取B1和f1.(4)取P3=v1v,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,图,G,(3),取,B,1,和,f,5,.(4),取,P,4,=v,2,v,6,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,f,1,f,2,f,3,f,6,f,4,f,5,19,v6v5v4v3v2v1v8v7图G (3)取B1和,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,图,G,继续下去，得到：,v,6,v,5,v,4,v,3,v,2,v,1,v,8,v,7,算法分析：主要运算包括：,20,v6v5v4v3v2v1v8v7图G 继续下去，得到：,（,i,）找出块,G,中的一个圈,H,i,；,（,ii,）确定,G,中,H,i,的桥以及它们对于,H,i,的附着点；,（,iii,）对于,的每个面,f,确定其周界；,（,iv,）对于,的每座桥,B,，确定,（,v,）在,H,i,的某座桥,B,中求一条起点与终点均为附着点,的一条路,P,i,。,可证上述每一个算法均存在好算法，因此平面性算法,也是好算法。,本章部分习题解答,21,（i）找出块G中的一个圈Hi；（ii）确定G中Hi的桥以及它,例,1,求证，每个,5,连通简单可平面图至少有,12,个顶点。,证明：设,G,是,5,连通图，则：,由惠特尼定理得：,所以：,另一方面：,G,是,5,连通简单可平面图，所以有：,于是得：,即：,所以：,n,12,。,22,例1 求证，每个5连通简单可平面图至少有12个顶点。,例,2,求证，没有,6,连通简单可平面图。,证明：若不然，设,G,是,6,连通图，则：,由惠特尼定理得：,所以：,于是得：,这与,G,是简单平面图矛盾。,例,3,求证：若,G,是连通平面图，且所有顶点度数不小于,3,，则,G,至少有一个面,f,，使得：,deg(f),5,。,23,例2 求证，没有6连通简单可平面图。证明,证明：若不然，则：,由欧拉公式得：,于是得：,另一方面：由,(G)3,得：,2m3n 3n-6,这样导出矛盾。,例,4,设,G,是一个,(n,m),图。求证：若,G,是外可平面图，且没有三角形，则：,m,(3n-4)/2,24,证明：若不然，则：由欧拉公式得：于是,证明：由条件易知：,由欧拉公式得：,于是得：,例,5,设,G,是一个,(n,m),单图，图,G,分解为可平面的最少个数称为,G,的厚度,(G).,求证：,(1),25,证明：由条件易知：由欧拉公式得：于是,(2),证明,:(1),当,n=1,时，结论成立。,设当,n,3,时，,G,分解为,(G),个可平面子图,G,i,(1i,(G),因为每个,G,i,是平面单图，于是：,所以：,所以：,26,(2)证明:(1)当n=1时，结论成立,(2),因为,K,3,K,4,是平面图，所以,(K,3,)=,(K,4,)=1,，而直接计算：,当,5,n8,时，,K,n,是非完全图。因为存在,8,阶简单可平面图,G,，其补图也是可平面图，所以对,5n8,，,K,n,可以分解为两个可平面图，即：,(K,n,)=2(5n8).,另一方面：当,5,n8,时，直接计算知：,这就证明了,(2),。,27,(2)因为K3,K4是平面图，所以(K3)=,说明：习题,6,的,1-9,题比较简单，要求自己独立完成。没有讲到的习题，作为参考。,28,说明：习题6的1-9题比较简单，要求自己独立完,作业,P143-146,习题,6,：,1-9,29,作业 P143-146 习题6：1-9,Thank You!,30,Thank You!30,