离散数学PPT课件9平面图.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,9,平面图,Plane Graph,在实际应用中,如高速公路设计,、,印刷电路设计,都要求,线路不交叉,这就是平面图,一个图能否画在一个平面上,且任何边都不交叉,这就是图的平面化问题,.,这个问题在,近些年来,特别是大规模集成电路的发展进一步促进了对,平面图的研究,.,1.,定义,设,G,是无向图,如果能将,G,的所有结点和边都画在一个,平面上,且使得任何两条边除了端点外没有其它交点,则,称,G,是个平面图.一个图表面上是个非平面图,如果通过,改变边的位置就变成平面图,称此图是可平面化的.,例如右图,.,就是,可平面化的图,.,下面是两个,重要的非平面图,:,K,5,和,K,3,3,v,1,v,5,v,4,v,2,v,3,v,1,v,5,v,4,v,2,v,3,v,1,v,5,v,4,v,2,v,3,v,1,v,5,v,4,v,2,v,3,3,5,1,6,2,4,a,f,b,e,c,d,a,f,b,e,c,d,2.,平面图的面、边界及面的次数,设,G,是个平面图,图中边围成的,区域,其内部不含有结点,也不含,有边,称这样区域为,G,的一个,面,.,面的边界,:,围成一个面,r,的所有,边构成的回路,称之为这个,r,面的边界,.,此回路中的边数,称,之为,r,面的次数,记作,deg(r),.,有限面与无限面,:面的面积有限称为有限面,反之称为无,限面.所有平面图的外侧都有一个无限面.,例如,上图中,r,1,:,边界,:ABCDFDA deg(r,1,)=6,r,2,:,边界,:ABCA deg(r,2,)=3,r,3,:,边界,:ACDA deg(r,3,)=3,r,4,:,边界,:ADA deg(r,4,)=2,A,D,F,B,C,r,1,r,2,r,3,r,4,3.,欧拉公式,定理,8-7.1 G,是个连通的平面图,设,v,、,e,、,r,分别表示,G,中,结点数,、,边数、面数,则有,v-e+r=2,.,称此式为,欧拉公式,.,证明,:(对面数,r,归纳证明),当,r=1,时,此时图是连通无回路的,如果有两个结点,则,图的图形如右图.以后每加一条边,也加一个,结点,所以总是有,e=v-1,于是,v-e+r=v-(v-1)+1=2,结论成立.,假设当,G,有,rk-1,个面时,结论成立,.,当,G,有,r=k,个面且是连通图时,当,k2,时,至少有一个,回路,所以去掉此回路中的一条边后得到子图,G,G,中有,k-1,个面,结点数同,G,中结点数,由得,v-(e-1)+(k-1)=2,整理得,v-e+k=2,即,v-e+r=2,定理得证.,4.,平面图的判定,定理,8-7.2(,必要条件,),设,G,是有,v,个结点,、,e,条边的连通简单平面图,若,v3,则,e3v-6.,证明,:,当,e=2,时,因为,G,是简单连通图,所以,v=3,显然有,2,33-6,即,e3v-6,当,e2,时,(通过计算每个面的边界来证明),设,G,有,r,个面,因为,G,是简单图,所以每个面至少由三条边,围成,所以,r,个面的总边界数3,r,另外由于每条边在两个,面的边界中出现,所以所有面的边界总数=2,e,所以有:,2,e=(r,个面边界总数)3,r,即2,e3r,所以,r,由欧拉公式:,v-e+r=2,得,v-e+2,整理得,e3v-6,用此定理可以判定一个图不是平面图,例如证明,K,5,不是,平面图:,K,5,中有,v=5 e=10 3v-6=35-6=9,不满足,e3v-6,所以,K,5,不是平面图,.,K,5,上面定理是判定平面图的必要条件,而不是充分条件,.,即,如果一个图 满足,e3v-6,它不一定是平面图,.,例如,K,3,3,中,v=6 e=9 936-6,满足,e3v-6,但它不一定是平面图,.,下面要介绍一个判定一个平面图的,充分且必要条件,即,Kuratowski,(,库拉托斯基,),定理,.,在此之,前先介绍一个,新概念,-,在,2,度结点内同构,(,同胚,).,在一个图中有,2,度结点,删除这些结点不影响平面的,面数,例如下面两个图,:,我们称这两个图是在,2,度结点内同构的图,.,3,5,1,6,2,4,v,1,v,5,v,4,v,2,v,3,v,1,v,5,v,4,v,2,v,3,v,8,v,9,v,6,v,7,定义,:,如果,G,1,和,G,2,是同构的,或者通过反复插入或删去度,数为,2,的结点,使得它们变成同构的图,称,G,1,和,G,2,是在,2,度,结点内同构,.,例如右边,3,个图就是,在,2,度结点内同构,.,定理,8-7.3(,Kuratowski,定理,),一个图是平面图的,充分且必,要条件,是它不含有任何与,K,5,、,K,3,3,在,2,度结点内同构的子,图,.(,此定理证明略,.),判断下面,彼得森(,Peterser,),图,:,v,1,v,6,v,2,v,5,v,8,v,9,v,3,v,4,v,7,v,10,v,1,v,6,v,2,v,5,v,8,v,9,v,3,v,4,v,7,v,10,v,1,v,8,v,9,v,2,v,6,v,5,v,10,v,4,v,3,v,7,本节要求掌握,:,平面图的概念,平面图的边界,欧拉公式及其应用,平面图的判定,.,作业,:P189 8.15 8.18 8.19,