资源描述
单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Email:,图论及其应用,任课教师：杨春,数学科学学院,1,第六章 平面图,主要内容,一、平面图概念与性质,二、特殊平面图与平面图的对偶图,三、平面图的判定与涉及平面性不变量,教学时数,安排,8,学时讲授本章内容,四、平面性算法,2,本次课主要内容,(,一,),、平面图的概念,(,二,),、平面图性质,平面图概念与性质,(,三,),、图的嵌入性问题简介,(,四,),、凸多面体与平面图,3,图的平面性问题是图论典型问题之一。生活中许多问题都与该问题有关。,(,一,),、平面图的概念,例子,1,：电路板设计问题,在电路板设计时，需要考虑的问题之一是连接电路元件间的导线间不能交叉。否则，当绝缘层破损时，会出现短路故障。,显然，电路板可以模型为一个图，“要求电路元件间连接导线互不交叉”，对应于“要求图中的边不能相互交叉”。,4,例子,2,：空调管道的设计,某娱乐中心有,6,个景点，位置分布如下图。,A,1,A,4,A,5,A,3,A,2,A,6,分析者认为：,(1)A,1,与,A,4,(2)A,2,与,A,5,(3)A,3,与,A,6,间人流较少，其它景点之间人流量大，必须投资铺设空调管道，但要求空调管道间不能交叉。如何设计？,5,如果把每个景点分别模型为一个点，景点间连线，当且仅当两景点间要铺设空调管道。那么，上面问题直接对应的图为：,A,6,A,5,A,4,A,3,A,2,A,1,于是，问题转化为：能否把上图画在平面上，使得边不会相互交叉？,6,通过尝试，可以把上图画为：,于是，铺设方案为：,A,6,A,5,A,4,A,3,A,2,A,1,A,1,A,4,A,5,A,3,A,2,A,6,7,问题：要求把,3,种公用设施,(,煤气，水和电,),分别用煤气管道、水管和电线连接到,3,间房子里，要求任何一根线或管道不与另外的线或管道相交，能否办到？,例子,3,：,3,间房子和,3,种设施问题,上面问题可以模型为如下偶图：,H3,H2,H1,E,W,G,问题转化为，能否把上面偶图画在平面上，使得边与边之间不会交叉？,8,上面的例子都涉及同一个图论问题：能否把一个图画在平面上，使得边与边之间没有交叉？,针对这一问题，我们引入如下概念,定义,1,如果能把图,G,画在平面上，使得除顶点外，边与边之间没有交叉，称,G,可以嵌入平面，或称,G,是可平面图。可平面图,G,的边不交叉的一种画法，称为,G,的一种平面嵌入，,G,的平面嵌入表示的图称为平面图。,H3,H2,H1,E,W,G,图,G,H3,H2,H1,E,W,G,图,G,的平面嵌入,9,注,:,(1),可平面图概念和平面图概念有时可以等同看待；,(2),图的平面性问题主要涉及如下几个方面：,1),平面图的性质；,2),平面图的判定；,3),平面嵌入方法,(,平面性算法,);4,）涉及图的平面性问题的拓扑不变量。,由 图的平面性问题研究引申出图的一般嵌入性问题的研究，形成了拓扑图论的主要内容。我国数学家吴文俊、刘彦佩等在该方向都有重要结果。刘彦佩的专著是,图的上可嵌入性理论,(1994),，化学工业出版社出版。,历史上，波兰数学家库拉托斯基、美国数学家惠特尼、生于英国的加拿大数学家托特，我国数学家吴文俊等都在拓扑图论中有过精湛的研究。,10,(,二,),、平面图性质,定义,2 (1),一个平面图,G,把平面分成若干连通片，这些连通片称为,G,的区域，或,G,的一个面。,G,的面组成的集合用,表示。,在上图,G,中，共有,4,个面。其中,f,4,是外部面，其余是内部面。,=,f,1,f,2,f,3,f,4,。,平面图,G,f,1,f,3,f,2,f,4,(2),面积有限的区域称为平面图,G,的内部面，否则称为,G,的外部面。,11,(3),在,G,中，顶点和边都与某个给定区域关联的子图，称为该面的边界。某面,f,的边界中含有的边数,(,割边计算,2,次,),称为该面,f,的次数,记为,deg,(,f),。,平面图,G,f,1,f,3,f,2,f,4,在上图中，红色边在,G,中的导出子图为面,f,3,的边界。,1,、平面图的次数公式,12,定理,1,设,G=(n,m),是平面图，则：,证明：对,G,的任意一条边,e,如果,e,是某面割边，那么由面的次数定义，该边给,G,的总次数贡献,2,次；如果,e,不是割边，那么，它必然是两个面的公共边，因此，由面的次数定义，它也给总次数贡献,2,次。于是有：,2,、平面图的欧拉公式,13,定理,2(,欧拉公式,),设,G=(n,m),是连通平面图，,是,G,的面数，则：,证明：情形,1,，如果,G,是树，那么,m=n-1,=1,。在这种情况下，容易验证，定理中的恒等式是成立的。,情形,2,，,G,不是树的连通平面图。,假设在这种情形下，欧拉恒等式不成立。则存在一个含有最少边数的连通平面图,G,使得它不满足欧拉恒等式。设这个最少边数连通平面图,G=(n,m),面数为,，则：,14,因为,G,不是树，所以存在非割边,e,。显然，,G-e,是连通平面图，边数为,m-1,顶点数为,n,面数为,-1,。,由最少性假设，,G-e,满足欧拉等式：,化简得：,这是一个矛盾。,注：该定理可以采用对面数,作数学归纳证明。,3,、欧拉公式的几个有趣推论,15,推论,1,设,G,是具有,个面,k,个连通分支的平面图，则：,证明：对第,i(1,ik),个分支来说，设顶点数为,n,i,，边数为,m,i,，面数为,i,由欧拉公式：,所以，,16,而：,所以得：,推论,2,设,G,是具有,n,个点,m,条边,个面的连通平面图，如果对,G,的每个面,f,有：,deg(,f,),l,3,则：,17,证明：一方面，由次数公式得：,另一方面，由欧拉公式得：,所以有：,整理得：,18,注,:(1),上面推论,2,也可以叙述为：,设,G=(n,m),是连通图，如果：,则,G,是非可平面图。,(2),推论,2,的条件是,G,是平面图的必要条件,不是充分条件。,例,1,求证：,K,3,3,是非可平面图。,证明：注意到，,K,3,3,是偶图，不存在奇圈，所以，每个面的次数至少是,4,即,l,=4,19,所以，,而,m=9,，这样有：,所以，由推论,2,，,K,3,3,是非平面图。,推论,3,设,G,是具有,n,个点,m,条边,个面的简单平面图，则：,20,证明：情形,1,，,G,连通。,因为,G,是简单图，所以每个面的次数至少为,3,，即,l,=3,。于是，由推论,2,得：,情形,2,，若,G,不连通。设,G,1,G,2,G,k,是连通分支。,一方面,由推论,1,：,另一方面，由次数公式得：,所以得：,21,例,2,，证明：,K,5,是非可平面图。,证明：,K,5,是简单图，,m=10,n=5,。,3n-6=9,。,得，所以,K,5,是非可平面图。,推论,4,设,G,是具有,n,个点,m,条边的连通平面图，若,G,的每个圈均由长度是,l,的圈围成，则：,证明：由次数公式，欧拉公式容易得证。,22,推论,5,设,G,是具有,n,个点,m,条边的简单平面图，则：,证明：若不然，设,由握手定理：,这与,G,是简单平面图矛盾。,注：该结论是证明“,5,色定理”的出发点。,23,定理,3,一个连通平面图是,2,连通的，当且仅当它的每个面的边界是圈。,证明：“必要性”：,设,G,是,2,连通的平面图，因为环总是两个面的边界，且环面显然由圈围成。不失一般性，假设,G,没有环，那么,G,没有割边，也没有割点。所以，每个面的边界一定是一条闭迹。,设,C,是,G,的任意面的一个边界，我们证明，它一定为圈。,若不然，设,C,是,G,的某面的边界，但它不是圈。,因,C,是一条闭迹且不是圈，因此，,C,中存在子圈。设该子圈是,W,1,.,因,C,是某面的边界，所以,W,1,与,C,的关系可以表示为下图的形式：,24,v,v,j-1,v,1,v,2,v,i-1,v,i+1,v,n,W,1,容易知道：,v,为,G,的割点。矛盾！,“充分性”设平面图,G,的每个面的边界均为圈。此时删去,G,中任意一个点不破坏,G,的连通性，这表明,G,是,2,连通的。,推论,6,若一个平面图是,2,连通的，则它的每条边恰在两个面的边界上。,25,(,三,),、图的嵌入性问题简介,在图的平面嵌入的基础上，简单介绍：,1,、曲面嵌入,1),、球面嵌入,定理,4 G,可球面嵌入当且仅当,G,可平面嵌入。,证明：我们用建立球极平面射影的方法给出证明。,将求面,S,放在一个平面,P,上，设切点为,O,，过,O,作垂直于,P,的直线，该直线与,S,相交于,z,。,26,2),、环面嵌入,环面的形状像一个汽车轮胎的表面。,P,z,y,O,x,球极投影示意图,作映射,f,:S-,z,P,。定义,f,(x)=y,使得,x,y,z,三点共线。该映射称为球极平面射影。,通过,f,可以把嵌入球面的图映射为嵌入平面的图。反之亦然。,27,例,3,将,K,4,K,5,K,3,3,嵌入到环面上。,3),定向曲面嵌入,K,4,的环面嵌入,K,5,的环面嵌入,K,3,3,的环面嵌入,这是目前嵌入性问题研究热点。国内：刘彦佩，黄元秋等是从事该方向研究的代表。,28,2,、图的,3,维空间嵌入,定理,5,所有图均可嵌入,R,3,中。,证明：在,R,3,中作空间曲线：,把图,G,的顶点放在该直线的不同位置，则,G,的任意边不相交。,事实上，对处于曲线,l,上的任意,4,个相异顶点，它们对应的参数值分别为：,t,1,t,2,t,3,t,4,。,29,因为：,所以，上面,4,点不共面。,(,四,),、凸多面体与平面图,一个多面体称为凸多面体，如果在体上任取两点，其连线均在体上。,凸多面体的一维骨架：把一个凸多面体压缩在平面上，得到一个对应的平面图，该平面图称为该凸多面体的一维骨架。,30,定理,6,存在且只存在,5,种正多面体：它们是正四、六、八、十二、二十面体。,证明：任取一个正,面体，其顶点数、棱数分别是,n,和,m,。对应的一维骨架是一个每个面次数为,l,顶点度数为,r,的简单平面正则图,G.,正八面体一维骨架,正二十面体一维骨架,31,由次数公式得：,以上两等式中：,l,3,r 3,由握手定理得：,由,(1),与,(2),得：,将,(3),代入欧拉公式得：,在,(4),中，,32,于是得不等式组：,不等式组,(5),的正整数解恰有,5,组：,正二十面体,20,30,12,3,5,5,正八面体,8,12,6,3,4,4,正十二面体,12,30,20,5,3,3,正方体,6,12,8,4,3,2,正四面体,4,6,4,3,3,1,相应的正多面体,m,n,r,l,序号,定理得证。,33,Thank You!,34,
展开阅读全文