《离散数学平面》PPT课件

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,8.4 平面图,平面图与平面嵌入,平面图的面、有限面、无限面,面的次数,极大平面图,极小非平面图,欧拉公式,平面图的对偶图,1,平面图和平面嵌入,定义,如果能将图,G,除顶点外边不相交地画在平面上,则称,G,是,平面图,.这个画出的无边相交的图称作,G,的,平面嵌入,.没有平面嵌入的图称作,非平面图,.,例如 下图中(1)(4)是平面图,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面图.,2,平面图和平面嵌入(续),今后称一个图是平面图,可以是指定义中的平面图,又可以是指平面嵌入,视当时的情况而定,.,当讨论的问题与图的画法有关时,是指平面嵌入,.,K,5,和,K,3,3,是非平面图,设,G,G,若,G,为平面图,则,G,也是,平面图,;,若,G,为非平面图,则,G,也,是非平面图,.,K,n,(,n,5,),K,3,n,(,n,3,),都是非平面图,.,平行边与环不影响图的平面性,.,K,5,K,3,3,3,平面图的面与次数,设,G,是一个平面嵌入,G,的面,:由,G,的边将平面划分成的每一个区域,无限面(外部面),:面积无限的面,用,R,0,表示,有限面(内部面),:面积有限的面,用,R,1,R,2,R,k,表示,面,R,i,的边界,:包围,R,i,的所有边构成的回路组,面,R,i,的次数,:,R,i,边界的长度，用deg(,R,i,)表示,说明:构成一个面的边界的回路组可能是初级回路,简单回,路,也可能是复杂回路,还可能是非连通的回路之并.,定理,平面图各面的次数之和等于边数的2倍,.,4,平面图的面与次数(续),例1 右图有4个面,deg(,R,1,)=1,deg(,R,2,)=3,deg(,R,3,)=2,deg(,R,0,)=8.请写各面的边界.,例,2 左边2个图是同一个平面图的平面嵌入.,R,1,在(1)中是外部面,在(2)中是内部面;,R,2,在(1)中是内部面,在(2)中是外部面.其实,在平面嵌入中可把任何面作为外部面.,5,极大平面图,定义,若,G,是简单平面图,并且在任意两个不相邻的顶点之,间加一条新边所得图为非平面图,则称,G,为,极大平面图,.,性质,若简单平面图中已无不相邻顶点，则是极大平面图.如,K,1,K,2,K,3,K,4,都是极大平面图.,极大平面图必连通.,阶数大于等于3的极大平面图中不可能有割点和桥.,设,G,为,n,(,n,3,)阶极大平面图,则,G,每个面的次数均为3.,任何,n,(,n,4)阶极大平面图,G,均有,(,G,),3.,6,实例,3个图都是平面图,但只有右边的图为极大平面图.,7,极小非平面图,定义,若,G,是非平面图,并且任意删除一条边所得图,都是平面图,则称,G,为,极小非平面图,.,说明:,K,5,K,3,3,都是极小非平面图,极小非平面图必为简单图,下面4个图都是极小非平面图,8,欧拉公式,定理8.11(欧拉公式),设,G,为,n,阶,m,条边,r,个面的连通平面图，,则,n,m,+,r,=2.,证 对边数,m,做归纳证明.,m,=0,G,为平凡图,结论为真.,设,m,=,k,(,k,0,)结论为真,m,=,k,+1时分情况讨论如下:,(1),G,中无圈,则,G,必有一个度数为1的顶点,v,删除,v,及它关,联的边,记作,G,.,G,连通,有,n,-1个顶点,k,条边和,r,个面.由,归,纳假设,(,n,-1)-,k,+,r,=2,即,n,-(,k,+1)+,r,=2,得证,m,=,k,+1时结论成立.,(2)否则,删除一个圈上的一条边,记作,G,.,G,连通,有,n,个顶,点,k,条边和,r-,1个面.由,归纳假设,n,-,k,+(,r,-1)=2,即,n,-(,k,+1)+,r,=2,得证,m,=,k,+1时结论也成立.证毕.,9,欧拉公式(续),欧拉公式的推广,设,G,是有,p,(,p,2)个连通分支的平面图,则,n,m,+,r,=,p,+1,证 设第,i,个连通分支有,n,i,个顶点,m,i,条边和,r,i,个面.,对各连通分支用欧拉公式,n,i,m,i,+,r,i,=2,i,=1,2,p,求和并注意,r,=,r,1,+,+,r,p,+,p,1,即得,n,m,+,r,=,p,+1,10,与欧拉公式有关的定理,K,5,K,3,3,定理,设,G,为,n,阶连通平面图,有,m,条边,且每个面的次数不,小于,l,(,l,3),则,证 由定理(各面次数之和等于边数的2倍)及欧拉公式得,2,m,lr,=,l,(2+,m-n,),可解得所需结论.,推论,K,5,和,K,3,3,不是平面图.,证 用反证法,假设它们是平面图,则,K,5,:,n,=5,m,=10,l,=3,K,3,3,:,n,=6,m,=9,l,=4,与定理矛盾.,11,与欧拉公式有关的定理(续),定理,:设,G,为有,p,(,p,2)个连通分支的平面图,且每个面的次数不小于,l,(,l,3),则,定理,设,G,为简单平面图，则,(,G,),5.,12,同胚与收缩,消去2度顶点,v,如上图从(1)到(2),插入2度顶点,v,如上图从(2)到(1),G,1,与,G,2,同胚,:,G,1,与,G,2,同构,或,经过反复插入、或消去2度顶,点后同构,收缩边,e,如下图从(1)到(2),13,库拉图斯基定理,定理,G,是平面图,G,中不含与,K,5,同胚的子图,也不,含与,K,3,3,同胚的子图.,定理,G,是平面图,G,中无可收缩为,K,5,的子图,也无,可收缩为,K,3,3,的子图.,14,非平面图证明,例 证明下述2个图均为非平面图.,证,图中红色部分分别与,K,3,3,和,K,5,同胚,15,平面图的对偶图,定义,设平面图,G,有,n,个顶点,m,条边和,r,个面,构造,G,的,对偶图,G,*=如下：,在,G,的每一个面,R,i,中任取一个点,v,i,*,作为,G,*的顶点,V,*=,v,i,*|i,=1,2,r,.,对,G,每一条边,e,k,若,e,k,在,G,的面,R,i,与,R,j,的公共边界上,则作边,e,k,*=(,v,i,*,v,j,*),且与,e,k,相交;若,e,k,为,G,中的桥且在,面,R,i,的边界上,则作环,e,k,*=(,v,i,*,v,i,*).,E,*=,e,k,*|,k,=1,2,m,.,16,平面图的对偶图（续）,例 黑色实线为原平面图,红色虚线为其对偶图,17,平面图的对偶图(续),性质：,G,*是平面图，而且是平面嵌入.,G,*是连通图,若边,e,为,G,中的环，则,G,*与,e,对应的边,e,*为桥;若,e,为桥，则,G,*中与,e,对应的边,e,*为环.,在多数情况下，,G,*含有平行边.,同构的平面图的对偶图不一定同构.,上面两个平面图是同构的,但它们的对偶图不同构.,18,平面图与对偶图的阶数、边数与面数之间的关系:,设,G,*是平面图,G,的对偶图，,n,*,m,*,r,*和,n,m,r,分别,为,G,*和,G,的顶点数、边数和面数，则,(1),n,*=,r,(2),m,*=,m,(3),r,*=,n-p+,1,其中,p,是,G,的连通分支数,(4)设,G,*的顶点,v,i,*位于,G,的面,R,i,中,则,d,(,v,i,*)=deg(,R,i,),平面图的对偶图(续),19,