图论课件特殊平面图与平面图的对偶图

单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论及其应用,1,本次课主要内容,(,一,),、一些特殊平面图,(,二,),、平面图的对偶图,特殊平面图与平面图的对偶图,1,、极大平面图及其性质,2,、极大外平面图及其性质,2,1,、极大平面图及其性质,(,一,),、一些特殊平面图,对于一个简单平面图来说，在不邻接顶点对间加边，当边数增加到一定数量时，就会变成非平面图。这样，就启发我们研究平面图的极图问题。,定义,1,设,G,是简单可平面图，如果,G,是,K,i,(1,i4),或者在,G,的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，则称,G,是极大可平面图。,极大可平面图的平面嵌入称为极大平面图。,3,注：只有在单图前提下才能定义极大平面图。,引理 设,G,是极大平面图，则,G,必然连通；若,G,的阶数大于等于,3,，则,G,无割边。,极大平面图,非极大平面图,极大平面图,(1),先证明,G,连通。,若不然，,G,至少两个连通分支。设,G,1,与,G,2,是,G,的任意两个连通分支。,4,把,G,1,画在,G,2,的外部面上，并在,G,1,G,2,上分别取一点,u,与,v.,连接,u,与,v,得到一个新平面图,G,*,。但这与,G,是极大平面图相矛盾。,(2),当,G,的阶数,n3,时，我们证明,G,中没有割边。,若不然，设,G,中有割边,e=uv,，则,G-uv,不连通，恰有两个连通分支,G,1,与,G,2,。,设,u,在,G,1,中，而,v,在,G,2,中。由于,n,3,所以，至少有一个分支包含两个以上的顶点。设,G,2,至少含有两个顶点。又设,G,1,中含有点,u,的面是,f,将,G,2,画在,f,内。,由于,G,是单图，所以，在,G,2,的外部面上存在不等于点,v,的点,t,。现在，在,G,中连接点,u,与,t,得新平面图,G,*,它比,G,多一条边。这与,G,的极大性相矛盾。,5,下面证明极大平面图的一个重要性质。,定理,1,设,G,是至少有,3,个顶点的平面图，则,G,是极大平面图，当且仅当,G,的每个面的次数是,3,且为单图。,注：该定理可以简单记为是“极大平面图的三角形特征”，即每个面的边界是三角形。,证明：“必要性”,由引理知，,G,是单图、,G,无割边且,G,的每个面的次数至少是,3,。,假设,G,中某个面,f,的次数大于等于,4,。记,f,的边界是,v,1,v,2,v,3,v,4,v,k,。如下图所示。,6,如果,v,1,与,v,3,不邻接，则连接,v,1,v,3,，没有破坏,G,的平面性，这与,G,是极大平面图矛盾。所以,v,1,v,3,必须邻接，但必须在,f,外连线；同理,v,2,与,v,4,也必须在,f,外连线。但边,v,1,v,3,与边,v,2,v,4,在,f,外交叉，与,G,是平面图矛盾！,所以，,G,的每个面次数一定是,3.,定理的充分性是显然的。,v,1,v,2,v,3,v,4,v,5,v,k,f,7,推论：设,G,是,n,个点，,m,条边和,个面的极大平面图，且,n3.,则：,(1) m=3n-6; (2),=2n-4.,证明：因为,G,是极大平面图，所以，每个面的次数为,3.,由次数公式：,由欧拉公式：,所以得：,8,所以得：,又,所以：,注：顶点数相同的极大平面图并不唯一。例如：,正,20,面体,非正,20,面体,9,还在研究中的问题是：顶点数相同的极大平面图的个数和结构问题。,2,、极大外平面图及其性质,与极大平面图相对应的图是极小平面图。,定义,2,若一个可平面图,G,存在一种平面嵌入，使得其所有顶点均在某个面的边界上，称该图为外可平面图。外可平面图的一种外平面嵌入，称为外平面图。,外可平面图,外平面图,1,外平面图,2,10,注：对外可平面图,G,来说，一定存在一种外平面嵌入，使得,G,的顶点均在外部面的边界上。这由球极投影法可以说明。,下面研究极大外平面图的性质。,定义,3,设,G,是一个简单外可平面图，若在,G,中任意不邻接顶点间添上一条边后，,G,成为非外可平面图，则称,G,是极大外可平面图。极大外可平面图的外平面嵌入，称为极大外平面图。,极大外平面图,11,引理,设,G,是一个连通简单外可平面图，则在,G,中有一个度数至多是,2,的顶点。,证明,我们对,G,的阶数,n,作数学归纳。,当,n,3,时，引理结论显然成立；当,n=4,时，由于,K,4,不能是外可平面图，所以，四阶的外可平面图至少有一个顶点度数不超过,2,。事实上，更强一点的结论是：当,n=4,时，有两个不邻接顶点，其度数不超过,2.,设当,G,是一个阶数小于,n,的简单连通外可平面图时，存在两个不邻接顶点，其度数不超过,2,。,考虑,G,是一个阶数等于,n,的简单连通外可平面图。,情形,1,，如果,G,有割点,x,12,由归纳假设，,G-x,的两个不同分支中分别有一个异于,x,的顶点,z,与,z,1,使得度数不超过,2,。这说明,G,中有两个不邻接顶点,使得度数都不超过,2,；,x,情形,2,若,G,是,2,连通的。,考虑,G,的任意一种外平面嵌入。则,G,的外部面边界一定是圈。否则，容易推出,G,有割点。,设,C,是,G,的外平面嵌入的外部面边界。若除,C,外，图中没有其它的边，则,G=C,显然,G,中有不邻接点，度数不超过,2,；,13,若除,C,外，图中至少有边,xy,。如下图所示：,x,y,则在,C,上的两条,xy,路上的点在,G,中的两个导出子图,H,1,与,H,2,是外平面图。,有归纳假设，在,H,1,H,2,中分别存在异于,x ,y,的点,z,与,z,1,使得，它们的度数不超过,2.,x,y,z,z,1,14,定理,2,设,G,是一个有,n (n,3),个点，且所有点均在外部面上的极大外平面图，则,G,有,n-2,个内部面。,证明：对,G,的阶数作数学归纳。,当,n=3,时，,G,是三角形，显然只有一个内部面；,设当,n=k,时，结论成立。,当,n=k+1,时，首先，注意到,G,必有一个,2,度顶点,u,在,G,的外部面上。,(,这可以由上面引理得到,),考虑,G,1,=G-v,。由归纳假设，,G,1,有,k-2,个内部面。这样,G,有,k-1,个内部面。于是定理,2,得证。,15,定理,3,设,G,是一个有,n (n,3),个点，且所有点均在外部面上的外平面图，则,G,是极大外平面图，当且仅当其外部面的边界是圈，内部面是三角形。,注：这是极大外平面图的典型特征。,证明：先证明必要性。,(1),证明,G,的边界是圈。,设,W=v,1,v,2,v,n,v,1,是,G,的外部面边界。若,W,不是圈，则存在,i,与,j,使得：,1,i,jn,且,j-i1(modn),使,v,i,=v,j,=v.,此时，,G,可以示意如下：,W,v,i,-1,v,1,v,n,v,2,v,i+,1,v,j-,1,v,j+,1,v,16,v,i-1,与,v,i+1,不能邻接。否则,W,不能构成,G,的外部面边界。这样，我们连接,v,i-1,与,v,i+1,：,v,i,-1,v,1,v,n,v,2,v,i+,1,v,j-,1,v,j+,1,v,得到一个新外平面图。这与,G,的极大性矛盾。,(2),证明,G,的内部面是三角形。,首先，注意到，,G,的内部面必须是圈。因为，,G,的外部面的边界是生成圈，所以,G,是,2,连通的，所以，,G,的每个面的边界必是圈。,17,其次，设,C,是,G,中任意一个内部面的边界。如果,C,的长度大于等于,4,，则,C,中一定存在不邻接顶点，连接这两点得到一个新平面图，这与,G,的极大性矛盾。又由于,G,是单图，所以,C,的长度只能为,3.,下面证明充分性。,设,G,是一个外平面图，内部面是三角形，外部面是圈,W.,如果,G,不是极大外平面图，那么存在不邻接顶点,u,与,v,使得,G+uv,是外平面图。,但是，,G+uv,不能是外平面图。因为，若边,uv,经过,W,的内部，则它要与,G,的其它边相交；若,uv,经过,W,的外部，导致所有点不能在在,G,的同一个面上。,所以，,G,是极大外平面图。,18,定理,4,每个至少有,7,个顶点的外可平面图的补图不是外可平面图，且,7,是这个数目的最小者。,我们用枚举方法证明。,证明：对于,n=7,的极大外可平面图来说，只有,4,个。如下图所示。,直接验证：它们的补图均不是外可平面的。,而当,n=6,时，我们可以找到一个外可平面图,G(,见下图,),使得其补图是外可平面图。,19,(,二,),、平面图的对偶图,1,、对偶图的定义,定义,4,给定平面图,G,，,G,的对偶图,G*,如下构造：,(1),在,G,的每个面,f,i,内取一个点,v,i,*,作为,G*,的一个顶点；,(2),对,G,的一条边,e,若,e,是面,f,i,与,f,j,的公共边，则连接,v,i,*,与,v,j,*,，且连线穿过边,e;,若,e,是面,fi,中的割边，则以,v,i,为顶点,20,作环，且让它与,e,相交。,例如，作出平面图,G,的对偶图,G,*,G,21,2,、对偶图的性质,(1),、,G,与,G,*,的对应关系,1) G*,的顶点数等于,G,的面数；,2) G*,的边数等于,G,的边数；,3) G*,的面数等于,G,的顶点数；,4) d (v*)=deg( f ),对偶图,面,边,割边,环,边割集,回路,点,边,环,割边,回路,边割集,对 应,平面图,G,22,(2),、定理,5,定理,5,平面图,G,的对偶图必然连通,证明：在,G*,中任意取两点,v,i,*,与,v,j,*,。我们证明该两点连通即可！,用一条曲线,l,把,v,i,*,和,v,j,*,连接起来，且,l,不与,G*,的任意顶点相交。,显然，曲线,l,从,v,i,*,到,v,j,*,经过的面边序列，对应从,v,i,*,到,v,j,*,的点边序列，该点边序列就是该两点在,G*,中的通路。,注,: (1),由定理,5,知：,(G*)*,不一定等于,G;,23,证明：“必要性”,(2) G,是平面图，则 当且仅当,G,是连通的。,(,习题第,26,题,),由于,G,是平面图，由定理,5,，,G*,是连通的。而由,G*,是平面图，再由定理,5,，,(G*)*,是连通的。,所以，由 得：,G,是连通的。,“充分性”,由对偶图的定义知，平面图,G,与其对偶图,G,*,嵌入在同一平面上，当,G,连通时，容易知道：,G,*,的无界面,f,*,中仅含,G,的唯一顶点,v,而除,v,外，,G,中其它顶点,u,均与,G*,的有限面形成一一对应，且对应顶点间邻接关系保持不变，即：,24,(3),同构的平面图可以有不同构的对偶图。,例如，下面的两个图：,G,1,G,2,但,这是,因为：,G,2,中有次数是,1,的面，而,G,1,没有次数是,1,的面。所以，它们的对偶图不能同构。,25,例,2,证明：,(1) B,是平面图,G,的极小边割集，当且仅当,是,G*,的圈。,(2),欧拉平面图的对偶图是偶图。,示意图,26,证明,: (1),对,B,的边数作数学归纳。,示意图,当,B,的边数,n=1,时，,B,中边是割边,显然，在,G*,中对应环。所以，结论成立。,设对,B,的边数,nk,时，结论成立。考虑,n=k,的情形。,设,c,1,B,于是,B-c,1,是,G-c,1,=G,1,的一个极小边割集。由归纳假设：,是,G,1,*,的一个圈。且圈,C,1,*,上的顶点对应于,G,1,中的面,f,f,的边界上有极小边割集,B-e,1,的边。,27,现在，把,e,1,加入到,G,1,中，恢复,G,。,示意图,G,1,由于,G,是平面图，其作用相当于圈,C,1,*,上的一个顶点对应于,G,1,中的一个平面区域,f,被,e,1,划分成两个顶点,f,1,*,与,f,2,*,并在其间连以,e,1,所对应的边,e,1,*,。,所以，,B,对应在,G*,中的,C*,仍然是一个圈。由归纳法，结论得到证明。,示意图,28,充分性：,G*,中的一个圈，对应于,G,中,的边的集合,B,显然是,G,中的一个边割集。,示意图,若该割集不是极小边割集，则它是,G,中极小边割集之和。而由必要性知道：每个极小边割集对应,G*,的一个圈，于是推出,B,在,G*,中对应的边集合是圈之并。但这与假设矛盾。,(2),因欧拉图的任意边割集均有偶数条边。于是由,(1),G*,中不含奇圈。所以,G*,是偶图。,29,例,3,设,T,是连通平面图,G,的生成树，,证明：,T,*,=G,*,E,*,是,G,*,中的生成树。,(,习题第,27,题,),示意图,30,证明：情形,1,，如果,G,是树。,在这种情况下，,E,*,=,.,则,T,*,是平凡图，而,G*,的生成树也是平凡图，所以，结论成立；,情形,2,，如果,G,不是树。,因,G,的每个面必然含有边,e,不属于,E(T),即,G*,的每个顶点必然和,E*,中的某边关联，于是,T*,必然是,G*,的生成子图。,下面证明：,T*,中没有圈。,若,T*,中有圈。则由例,2,知：,T,的余树中含有,G,的极小边割集。但我们又可以证明：,如果,T,是连通图,G,的生成树，那么，,T,的余树不含,G,的极小边割集,。这样，,T*,不能含,G*,的圈。,31,又因在,G,中，每去掉,T,的余树中的一条边，,G,的面减少一个，当,T,的余树中的边全去掉时，,G,变成一颗树,T.,于是，有：,所以，,T*,是,G*,的生成树。,32,作业,P143-146,习题,5,：,3,，,4,，,5,，,6,，,8,，,25, 26,，,27,。,其中,25,，,26,，,27,结合课件学习。,33,Thank You !,34,