,-精品文档-,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,第17章 平面图,离 散 数 学,中国地质大学本科生课程,第17章 平面图离 散 数 学中国地质大学本科生课程,本章说明,本章的主要内容,平面图的基本概念,欧拉公式,平面图的判断,平面图的对偶图,-精品文档-,本章说明本章的主要内容-精品文档-,2,本章所涉及到的图均指无向图。,-精品文档-,本章所涉及到的图均指无向图。-精品文档-,3,17.1,平面图的基本概念,17.2,欧拉公式,17.3,平面图的判断,17.4,平面图的对偶图,本章小结,习 题,作 业,-精品文档-,17.1 平面图的基本概念-精品文档-,4,17.1,平面图的基本概念,一、关于平面图的一些基本概念,1、平面图的定义,定义17.1,G,可嵌入曲面,S,如果图,G,能以这样的方式画在曲面,S,上，即除顶点处外无边相交。,G,是可平面图或平面图若,G,可嵌入平面,。,G,的平面嵌入画出的无边相交的平面图。,非平面图无平面嵌入的图。,-精品文档-,17.1 平面图的基本概念一、关于平面图的一些基本概念-,5,（2）,是（1）的平面嵌入，（4）是（3）的平面嵌入。,-精品文档-,（2）是（1）的平面嵌入，（4）是（3）的平面嵌入。-,6,2、几点说明及一些简单结论,一般所谈平面图不一定是指平面嵌入，但讨论某些性质时，一定是指平面嵌入。,K,5,和,K,3,3,都不是平面图。,定理17.1,设,G,G,，,若,G,为平面图，则,G,也是平面图。,设,G,G,，,若,G,为非平面图，则,G,也是非平面图。,由定理可知，,K,n,(,n,5),和,K,3,n,(,n,3),都是非平面图。,定理17.,2,若,G,为平面图，则在,G,中加平行边或环所得图还是平面图。即平行边和环不影响图的平面性。,-精品文档-,2、几点说明及一些简单结论-精品文档-,7,二、平面图的面与次数（针对平面图的平面嵌入）,1、定义,定义17.2,设,G,是平面图，,G,的面由,G,的边将,G,所在的平面划分成的每一个区域。,无限面（外部面）面积无限的面，记作,R,0,。,有限面（内部面）面积有限的面，记作,R,1,R,2,R,k,。,面,R,i,的边界包围面,R,i,的所有边组成的回路组。,面,R,i,的次数,R,i,边界的长度，记作,deg,(,R,i,),。,-精品文档-,二、平面图的面与次数（针对平面图的平面嵌入）-精品文,8,2、几点说明,若平面图,G,有,k,个面，可笼统地用,R,1,R,2,R,k,表示，不需要指出外部面。,回路组是指：边界可能是初级回路（圈），可能是简单回路，也可能是复杂回路。特别地，还可能是非连通的回路之并。,平面图有4个面，,deg,(,R,1,)=1,deg,(,R,2,)=3,deg,(,R,3,)=2,deg,(,R,0,)=8。,R1,R2,R3,R0,-精品文档-,2、几点说明平面图有4个面，deg(R1)=1,deg(R,9,定理17.,3,平面图,G,中所有面的次数之和等于边数,m,的两倍，即,本定理中所说平面图是指平面嵌入。,e,E,(,G,)，,当,e,为面,R,i,和,R,j,(,i,j,),的公共边界上的边时，在计算,R,i,和,R,j,的次数时，,e,各提供1。,当,e,只在某一个面的边界上出现时，则在计算该面的次数时，,e,提供2。,于是每条边在计算总次数时，都提供2，因而,deg,(,R,i,)=2,m,。,证明,-精品文档-,定理17.3 平面图G中所有面的次数之和等于边数m的两倍，即,10,三、极大平面图,1、定义,定义17.3,若在简单平面图,G,中的任意两个不相邻的顶点之间加一条新边所得图为非平面图，则称,G,为极大平面图。,注意：,若简单平面图,G,中已无不相邻顶点，,G,显然是极大平面图，如,K,1,（,平凡图）,K,2,K,3,K,4,都是极大平面图。,2、极大平面图的主要性质,定理17.,4,极大平面图是连通的，并且,n(n,3),阶极大平面图中不可能有割点和桥。,-精品文档-,三、极大平面图-精品文档-,11,定理17.,5,设,G,为,n,(,n,3),)阶简单连通的平面图，,G,为极大平面图当且仅当,G,的每个面的次数均为3。,本节只证明必要性，即,设,G,为,n,(,n,3),)阶简单连通的平面图，,G,为极大平面图，则,G,的每个面的次数均为3。,由于,n,3,又,G,必为简单平面图，可知，,G,每个面的次数均,3。,因为,G,为平面图，又为极大平面图。可证,G,不可能存在次数3的面。,证明思路,-精品文档-,定理17.5 设G为n(n3)阶简单连通的平面图，G,12,假设存在面,R,i,的次数,deg,(,R,i,)=,s,4，,如图所示。,在,G,中，若,v,1,与,v,3,不相邻，在,R,i,内加边(,v,1,v,3,),不破坏平面性，这与,G,是极大平面图矛盾，因而,v,1,与,v,3,必相邻，由于,R,i,的存在，边(,v,1,v,3,),必在,R,i,外。,类似地，,v,2,与,v,4,也必相邻，且边(,v,2,v,4,),也必在,R,i,外部，于是必产生(,v,1,v,3,),与(,v,2,v,4,),相交于,R,i,的外部，这又矛盾于,G,是平面图，所以必有,s,3，,即,G,中不存在次数大于或等于4的面，所以,G,的每个面为3条边所围，也就是各面次数均为3。,s,S-1,-精品文档-,假设存在面Ri的次数deg(Ri)=s4，如图所示。在G中,13,只有右边的图为极大平面图。,因为只有该图每个面的次数都为3。,-精品文档-,只有右边的图为极大平面图。-精品文档-,14,四、极小非平面图,定义17.4,若在非平面图,G,中任意删除一条边，所得图,G,为平面图，则称,G,为极小非平面图。,由定义不难看出：,K,5,K,3,3,都是极小非平面图。,极小非平面图必为简单图。,例如：,以下各图均为极小非平面图。,小节结束,-精品文档-,四、极小非平面图小节结束-精品文档-,15,17.2 欧拉公式,一、欧拉公式相关定理,1、欧拉公式,定理17.,6,对于任意的连通的平面图,G,，,有,n,-,m,+,r,=2,其中，,n,、,m,、,r,分别为,G,的顶点数、边数和面数。,证明,对边数,m,作归纳法。,(1),m,0,时，由于,G,为连通图，所以,G,只能是由一个孤立顶点组成的平凡图，即,n=1，m=0，r,=1，,结论显然成立。,(2),m,1,时，由于,G,为连通图，所以,n=2，m=1，r,=1，,结论显然成立。,-精品文档-,17.2 欧拉公式 一、欧拉公式相关定理证明对边数m作归纳法,16,(3)设,m,k,(,k,1),时成立，当,m,k,+1,时，对,G,进行如下讨论。,若,G,是树，则,G,是非平凡的，因而,G,中至少有两片树叶。,设,v,为树叶，令,G,=,G,-,v,，,则,G,仍然是连通图，且,G,的边数,m,=,m,-1=,k,，,n,=,n,-1，,r,=,r,。,由假设可知,n,-,m,+,r,=2，,式中,n,，,m,，,r,分别为,G,的顶点数，边数和面数。,于是,n,-,m,+,r,=(,n,+1)-(,m,+1)+,r,=,n,-,m,+,r,=2,若,G,不是树，则,G,中含圈。,设边,e,在,G,中某个圈上，令,G,=,G,-,e,，,则,G,仍连通且,m,=,m,-1=,k,，,n,=,n,，,r,=,r,-1。,由假设有,n,-,m,+,r,=2。,于是,n,-,m,+,r,=,n,-(,m,+1)-(,r,+1)=,n,-,m,+,r,=2,-精品文档-,(3)设mk(k1)时成立，当mk+1时，对G,17,定理17.,7,对于具有,k,(,k,2),个连通分支的平面图,G,，,有,n,-,m,+,r,=,k,+1,其中,n,，,m，r,分别为,G,的顶点数，边数和面数。,证明,设,G,的连通分支分别为,G,1,、,G,2,、,G,k,，,并设,G,i,的顶点数、边数、面数分别为,n,i,、,m,i,、,r,i,、,i,=1，2，,k,。,由欧拉公式可知:,n,i,-,m,i,+,r,i,=2，,i,=1，2，,k,(17.1),易知，,由于每个,G,i,有一个外部面，而,G,只有一个外部面，所以,G,的面数,于是，,对,(17.1),的两边同时求和得,经整理得,n,-,m,+,r,=,k,+1。,-精品文档-,定理17.7 对于具有k(k2)个连通分支的平面图G，有,18,2、与欧拉公式有关的定理,定理17.,8,设,G,为连通的平面图，且每个面的次数至少为,l,(,l,3,)，,则,G,的边数与顶点数有如下关系：,由定理17.,3,（面的次数之和等于边数的2倍）及欧拉公式得,证明,解得,-精品文档-,2、与欧拉公式有关的定理由定理17.3（面的次数之和等于边,19,推论,K,5,K,3,3,不是平面图。,证明,若,K,5,是平面图，由于,K,5,中无环和平行边，所以每个面的次数均大于或等于,l,3，,由定理17.,8,可知边数10应满足,10(3/(3-2)(5-2)=9,这是个矛盾，所以,K,5,不是平面图。,若,K,3,3,是平面图，由于,K,3,3,中最短圈的长度为,l,4，,于是边数9应满足,9(4/(4-2)(6-2)=8,这又是矛盾的，所以,K,3,3,也不是平面图。,-精品文档-,推论 K5,K3,3不是平面图。证明若K5是平面图，由于,20,定理17.,9,设,G,是有,k,(,k,2),个连通分支的平面图，各面的次数至少为,l,(,l,3)，,则边数,m,与顶点数,n,应有如下关系：,定理17.1,0,设,G,为,n,(,n,3),阶,m,条边的简单平面图，则,m,3,n,6。,设,G,有,k,(,k,1),个连通分支，,若,G,为树或森林，当,n,3,时，,m=n-k,3,n,6,为真。,若,G,不是树也不是森林，则,G,中必含圈，又因为,G,是简单图，所以，每个面至少由,l,（,l,3）,条边围成，又在,l,=3,达到最大值，由定理17.,9,可知,证明,-精品文档-,定理17.9 设G是有k(k2)个连通分支的平面图，各面的,21,定理17.1,1,设,G,为,n,(,n,3),阶,m,条边的极大平面图，则,m,=3,n,6。,证明,由于极大平面图是连通图，由欧拉公式得:,r,=2+,m,-,n,(17.4),又因为,G,是极大平面图，由定理17.7的必要性可知，,G,的每个面的次数均为3，所以：,将(17.4)代入(17.5)，整理后得,m,=3,n,-6。,-精品文档-,定理17.11 设G为n(n3)阶m条边的极大平面图，则m,22,二、一个意义重大的定理,定理17.1,2,设,G,为简单平面图，则,G,的最小度,(,G,),5。,若阶数,n,6，,结论显然成立。,若阶数,n,7,时，用反证法。,假设,(,G,),6，,由握手定理可知：,证明,因而,m,3,n,，,这与定理17.1,0,矛盾。,所以，假设不成立，即,G,的最小度,(,G,),5。,本定理在图着色理论中占重要地位。,说明,-精品文档-,二、一个意义重大的定理 若阶数 n6，结论显然成立。证明因,23,一、为判断定理做准备,1、插入2度顶点和消去2度顶点,定义17.5,设,e,=(,u,v,),为图,G,的一条边，在,G,中删除,e,，,增加新的顶点,w,，,使,u,、,v,均与,w,相邻，称为在,G,中,插入2度顶点,w,。,设,w,为,G,中一个2度顶点，,w,与,u,、,v,相邻，删除,w,，,增加新边(,u,v,)，,称为在,G,中,消去2度顶点,w,。,17.3 平面图的判断,-精品文档-,一、为判断定理做