离散数学17平面图ppt课件

1、第17章 平面图离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程q本章的主要内容本章的主要内容q平面图的基本概念平面图的基本概念q欧拉公式欧拉公式q平面图的判断平面图的判断q平面图的对偶图平面图的对偶图本章所涉及到的图均指无向图。本章所涉及到的图均指无向图。q 17.1 17.1 平面图的基本概念平面图的基本概念q 17.2 17.2 欧拉公式欧拉公式q 17.3 17.3 平面图的判断平面图的判断q 17.4 17.4 平面图的对偶图平面图的对偶图q 本章小结本章小结q 习习 题题q 作作 业业一、关于平面图的一些基本概念一、关于平面图的一些基本概念1、 平面图的定义平面图

2、的定义定义定义17.1 G可嵌入曲面可嵌入曲面S如果图如果图G能以这样的方式画在曲面能以这样的方式画在曲面S上，即上，即除顶点处外无边相交。除顶点处外无边相交。 G是可平面图或平面图是可平面图或平面图若若G可嵌入平面。可嵌入平面。G的平面嵌入的平面嵌入画出的无边相交的平面图。画出的无边相交的平面图。非平面图非平面图无平面嵌入的图。无平面嵌入的图。（2是是1的平面嵌入，（的平面嵌入，（4是是3的平面嵌入。的平面嵌入。2、 几点说明及一些简单结论几点说明及一些简单结论一般所谈平面图不一定是指平面嵌入，但讨论某些性质时，一一般所谈平面图不一定是指平面嵌入，但讨论某些性质时，一定是指平面嵌入。定是指平

3、面嵌入。K5和和K3,3都不是平面图。都不是平面图。定理定理17.1 设设GG，若，若G为平面图，则为平面图，则G也是平面图。也是平面图。 设设GG，若，若G为非平面图，则为非平面图，则G也是非平面图也是非平面图。由定理可知，由定理可知， Kn(n5)和和K3,n(n3)都是非平面图。都是非平面图。定理定理17.2 若若G为平面图，则在为平面图，则在G中加平行边或环所得图还是平中加平行边或环所得图还是平面图。面图。即平行边和环不影响图的平面性。即平行边和环不影响图的平面性。 二、平面图的面与次数针对平面图的平面嵌入）二、平面图的面与次数针对平面图的平面嵌入）1、 定义定义定义定义17.2 设设

4、G是平面图，是平面图，G的面的面由由G的边将的边将G所在的平面划分成的每一个区域。所在的平面划分成的每一个区域。无限面外部面）无限面外部面）面积无限的面，记作面积无限的面，记作R0。有限面内部面）有限面内部面）面积有限的面面积有限的面 ，记作，记作R1, R2, , Rk。面面Ri的边界的边界包围面包围面Ri的所有边组成的回路组。的所有边组成的回路组。面面Ri的次数的次数Ri边界的长度，记作边界的长度，记作deg(Ri)。2、几点说明、几点说明若平面图若平面图G有有k个面，可笼统地用个面，可笼统地用R1, R2, , Rk表示，不需表示，不需要指出外部面。要指出外部面。回路组是指：边界可能是初

5、级回路圈），可能是简单回路回路组是指：边界可能是初级回路圈），可能是简单回路，也可能是复杂回路。特别地，还可能是非连通的回路之，也可能是复杂回路。特别地，还可能是非连通的回路之并。并。平面图有平面图有4个面，个面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8。 R1R2R3R0定理定理17.3 17.3 平面图平面图G G中所有面的次数之和等于边数中所有面的次数之和等于边数m m的两倍，即的两倍，即 本定理中所说平面图是指平面嵌入。本定理中所说平面图是指平面嵌入。 eE(G)，当当e为面为面Ri和和Rj(ij)的公共边界上的边时，在计算的公共边界上的边时

6、，在计算Ri和和Rj的的次数时，次数时，e各提供各提供1。当当e只在某一个面的边界上出现时，则在计算该面的次数时只在某一个面的边界上出现时，则在计算该面的次数时，e提供提供2。于是每条边在计算总次数时，都提供于是每条边在计算总次数时，都提供2，因而，因而deg(Ri)=2m。1deg()2riiRmrG其中 为 的面数证证明明三、极大平面图三、极大平面图1、 定义定义定义定义17.3 若在简单平面图若在简单平面图G中的任意两个不相邻的顶点之间中的任意两个不相邻的顶点之间加一条新边所得图为非平面图，则称加一条新边所得图为非平面图，则称G为极大平面图。为极大平面图。留意：若简单平面图留意：若简单平

7、面图G中已无不相邻顶点，中已无不相邻顶点，G显然是极大平显然是极大平面图，如面图，如K1平凡图）平凡图）, K2, K3, K4都是极大平面图。都是极大平面图。2、极大平面图的主要性质、极大平面图的主要性质定理定理17.4 极大平面图是连通的，并且极大平面图是连通的，并且n(n3)阶极大平面图阶极大平面图中不可能有割点和桥。中不可能有割点和桥。定理定理17.5 17.5 设设G G为为n(nn(n3) )3) )阶简单连通的平面图，阶简单连通的平面图，G G为极大平面为极大平面图当且仅当图当且仅当G G的每个面的次数均为的每个面的次数均为3 3。q本节只证明必要性，即设本节只证明必要性，即设G

8、为为n(n3) )阶简单连通的平面图，阶简单连通的平面图，G为极大平面图，则为极大平面图，则G的每个面的次数均为的每个面的次数均为3。q由于由于n3, 又又G必为简单平面图，可知，必为简单平面图，可知，G每个面的次数均每个面的次数均3。q因为因为G为平面图，又为极大平面图。可证为平面图，又为极大平面图。可证G不可能存在次数不可能存在次数3的面。的面。证证明明思思路路假设存在面假设存在面Ri的次数的次数deg(Ri)=s4，如下图。如下图。在在G中，若中，若v1与与v3不相邻，在不相邻，在Ri内加边内加边(v1,v3)不破坏平面性，不破坏平面性，这与这与G是极大平面图矛盾，因而是极大平面图矛盾，

9、因而v1与与v3必相邻，由于必相邻，由于Ri的存在的存在，边，边(v1,v3)必在必在Ri外。外。 类似地，类似地，v2与与v4也必相邻，且边也必相邻，且边(v2,v4)也必在也必在Ri外部，于是外部，于是必产生必产生(v1,v3)与与(v2,v4)相交于相交于Ri的外部，这又矛盾于的外部，这又矛盾于G是平面是平面图，所以必有图，所以必有s3，即，即G中不存在次数大于或等于中不存在次数大于或等于4的面，所的面，所以以G的每个面为的每个面为3条边所围，也就是各面次数均为条边所围，也就是各面次数均为3。sS-1 只有右边的图为极大平面图。只有右边的图为极大平面图。 因为只有该图每个面的次数都为因为

10、只有该图每个面的次数都为3。 四、极小非平面图四、极小非平面图定义定义17.4 若在非平面图若在非平面图G中任意删除一条边，所得图中任意删除一条边，所得图G为平为平面图，则称面图，则称G为极小非平面图。为极小非平面图。由定义不难看出：由定义不难看出：K5, K3,3都是极小非平面图。都是极小非平面图。极小非平面图必为简单图。极小非平面图必为简单图。例如：以下各图均为极小非平面图。例如：以下各图均为极小非平面图。17.2 17.2 欧拉公式欧拉公式 一、欧拉公式相关定理一、欧拉公式相关定理1、 欧拉公式欧拉公式定理定理17.6 对于任意的连通的平面图对于任意的连通的平面图G，有，有n-m+r=2

11、其中，其中，n、m、r分别为分别为G的顶点数、边数和面数。的顶点数、边数和面数。 证证明明对边数对边数m作归纳法。作归纳法。 (1) m0时，由于时，由于G为连通图，所以为连通图，所以G只能是由一个孤立顶只能是由一个孤立顶点组成的平凡图，即点组成的平凡图，即n=1，m=0，r=1，结论显然成立。，结论显然成立。(2) m1时，由于时，由于G为连通图，所以为连通图，所以n=2，m=1，r=1，结论，结论显然成立。显然成立。 (3)设设mk(k1)时成立，当时成立，当mk+1时，对时，对G进行如下讨论。进行如下讨论。若若G是树，则是树，则G是非平凡的，因而是非平凡的，因而G中至少有两片树叶。中至少

12、有两片树叶。 设设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 定理定理

13、17.7 17.7 对于具有对于具有k(k2)k(k2)个连通分支的平面图个连通分支的平面图G G，有，有 n-m+r = k+1 n-m+r = k+1其中其中n n，m m，r r分别为分别为G G的顶点数，边数和面数。的顶点数，边数和面数。 证证明明 设设G的连通分支分别为的连通分支分别为G1、G2、Gk，并设，并设Gi的顶点数、的顶点数、边数、面数分别为边数、面数分别为ni、mi、ri、i=1，2，k。 由欧拉公式可知由欧拉公式可知: ni-mi+ri = 2，i=1，2，k (17.1)易知，易知，11kkiiiimmnn，由于每个由于每个Gi 有一个外部面，而有一个外部面，而G只有

14、一个外部面，所以只有一个外部面，所以G的面的面数数11kiirrk于是，对于是，对(17.1)的两边同时求和得的两边同时求和得 11112()1kkkkiiiiiiiiiiknmrnmrnmrk 经整理得经整理得 n-m+r = k+1。2、 与欧拉公式有关的定理与欧拉公式有关的定理定理定理17.8 设设G为连通的平面图，且每个面的次数至少为为连通的平面图，且每个面的次数至少为l(l3)，那么，那么 G的边数与顶点数有如下关系：的边数与顶点数有如下关系：由定理由定理17.3面的次数之和等于边数的面的次数之和等于边数的2倍及欧拉公式得倍及欧拉公式得(2)2lmnl证证明明12deg()(2)ri

15、imRl rlmn 解得解得 (2)2lmnl推论推论 K5, K3,3 K5, K3,3不是平面图。不是平面图。证证明明q若若K5是平面图，由于是平面图，由于K5中无环和平行边，所以每个面的次中无环和平行边，所以每个面的次数均大于或等于数均大于或等于l3，由定理，由定理17.8可知边数可知边数10应满足应满足q 10(3/(3-2)(5-2) = 9q 这是个矛盾，所以这是个矛盾，所以K5不是平面图。不是平面图。 q若若K3,3是平面图，由于是平面图，由于K3,3中最短圈的长度为中最短圈的长度为l4，于是边数，于是边数9应满足应满足 q9 (4/(4-2)(6-2) = 8q 这又是矛盾的，

16、所以这又是矛盾的，所以K3,3也不是平面图。也不是平面图。 定理定理17.9 17.9 设设G G是有是有k(k2)k(k2)个连通分支的平面图，各面的次数个连通分支的平面图，各面的次数至少为至少为l(l3)l(l3)，则边数，则边数m m与顶点数与顶点数n n应有如下关系：应有如下关系： (1)2lmnkl定理定理17.10 17.10 设设G G为为n(nn(n3)3)阶阶m m条边的简单平面图，则条边的简单平面图，则m m3n3n6 6。 设设G有有k(k1)个连通分支，个连通分支，若若G为树或森林，当为树或森林，当n3时，时，m=n-k3n6为真。为真。若若G不是树也不是森林，则不是树

17、也不是森林，则G中必含圈，又因为中必含圈，又因为G是简单图，是简单图，所以，每个面至少由所以，每个面至少由ll3条边围成，又在条边围成，又在l=3达到最大达到最大值，由定理值，由定理17.9可知可知证证明明2(1)(1)(1)3(2)3622lmnknknnll定理定理17.11 17.11 设设G G为为n(nn(n3)3)阶阶m m条边的极大平面图，则条边的极大平面图，则m=3nm=3n6 6。证证明明 由于极大平面图是连通图，由欧拉公式得由于极大平面图是连通图，由欧拉公式得: r=2+m-n (17.4) 又因为又因为G是极大平面图，由定理是极大平面图，由定理17.7的必要性可知，的必要

18、性可知，G的每个的每个面的次数均为面的次数均为3，所以：，所以： 将将(17.4)代入代入(17.5)，整理后得，整理后得 m = 3n-6。12deg()3(17.5)riimRr二、一个意义重大的定理二、一个意义重大的定理 定理定理17.12 17.12 设设G G为简单平面图，则为简单平面图，则G G的最小度的最小度(G)(G)5 5。q 若阶数若阶数 n6，结论显然成立。，结论显然成立。q 若阶数若阶数n7时，用反证法。时，用反证法。q 假设假设(G) 6，由握手定理可知：，由握手定理可知：证证明明12( )6niimd vn因而因而m 3n，这与定理，这与定理17.10矛盾。矛盾。所

19、以，假设不成立，即所以，假设不成立，即G的最小度的最小度(G)5。q本定理在图着色理论中占重要地位。本定理在图着色理论中占重要地位。一、为判断定理做准备一、为判断定理做准备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 17.3 平面

20、图的判断平面图的判断2、图之间的同胚、图之间的同胚若两个图若两个图G1与与G2同构，或通过反复插入或消去同构，或通过反复插入或消去2度顶点后度顶点后是同构的，则称是同构的，则称G1与与G2是同胚的。是同胚的。上面两个图分别与上面两个图分别与K3,3, K5同胚同胚 。二、两个判断定理二、两个判断定理 定理定理17.13(库拉图斯基定理库拉图斯基定理1) 图图G是平面图当且仅当是平面图当且仅当G中既不含中既不含与与K5同胚子图，也不含与同胚子图，也不含与K3,3同胚子图。同胚子图。 定理定理17.14(库拉图斯基定理库拉图斯基定理2) 图图G是平面图当且仅当是平面图当且仅当G中既没有中既没有可以

21、收缩到可以收缩到K5的子图，也没有可以收缩到的子图，也没有可以收缩到K3,3的子图。的子图。 例例17.1 17.1 证明彼得松图不是平面图。证明彼得松图不是平面图。 将彼得松图顶点标顺序，见图将彼得松图顶点标顺序，见图 (1)所示。所示。证证明明还可以这样证明：还可以这样证明：用用G表示彼得松图，令表示彼得松图，令 G=G-(j,g),(c,d)G如图如图 (3)所示，易知它与所示，易知它与K3,3同胚，同胚，在图中将边在图中将边(a,f), (b,g), (c,h), (d,i), (e,j)收缩，收缩，所得图为图所得图为图 (2)所示，它是所示，它是K5，由定理由定理17.16可知，彼得

22、松图不是平面图。可知，彼得松图不是平面图。由定理由定理17.15可知，可知，G为非平面图。为非平面图。例例17.2 17.2 对对K5K5插入插入2 2度顶点，或在度顶点，或在K5K5外放置一个顶点使其与外放置一个顶点使其与K5K5上的若上的若干顶点相邻，共可产生多少个干顶点相邻，共可产生多少个6 6阶简单连通非同构的非平面图？阶简单连通非同构的非平面图？ 用插入用插入2度顶点的方法只能产生度顶点的方法只能产生一个非平面图，如图一个非平面图，如图(1)所示。所示。解解答答在在K5外放置一个顶点，使其与外放置一个顶点，使其与K5上的上的1个到个到5个顶点相邻，得个顶点相邻，得5个图，如图个图，如

23、图 (2)到到(6)所示。所示。它与它与K5同胚，所以是非平面图。同胚，所以是非平面图。它们都含它们都含K5为子图，由库拉图为子图，由库拉图斯基定理可知，它们都是非平斯基定理可知，它们都是非平面图，并且也满足其它要求。面图，并且也满足其它要求。例例17.3 17.3 由由K3,3K3,3加若干条边能生成多少个加若干条边能生成多少个6 6阶连通的简单的非同构的阶连通的简单的非同构的非平面图？非平面图？ 对对K3,3加加16条边所得图都含条边所得图都含K3,3为子图，由库拉图斯基定理为子图，由库拉图斯基定理可知，它们都是非平面图。可知，它们都是非平面图。 在加在加2条、加条、加3条、加条、加4条边

24、时又各产生两个非同构的非平面图，条边时又各产生两个非同构的非平面图，连同连同K3,3本身共有本身共有10个满足要求的非平面图。其中，绿线边表个满足要求的非平面图。其中，绿线边表示后加的新边。示后加的新边。 解解答答17.4 17.4 平面图的对偶图平面图的对偶图一、对偶图的定义一、对偶图的定义定义定义17.6 设设G是某平面图的某个平面嵌入，构造是某平面图的某个平面嵌入，构造G的对偶图的对偶图G*如下：如下：在在G的面的面Ri中放置中放置G*的顶点的顶点vi* 。设设e为为G的任意一条边，的任意一条边，若若e在在G的面的面Ri与与Rj的公共边界上，做的公共边界上，做G*的边的边e*与与e相交，

25、相交，且且e*关联关联G*的位于的位于Ri与与Rj中的顶点中的顶点vi*与与vj*，即，即e*=(vi*,vj*)，e*不与其它任何边相交。不与其它任何边相交。若若e为为G中的桥且在面中的桥且在面Ri的边界上，则的边界上，则e*是以是以Ri中中G*的顶的顶点点vi*为端点的环，即为端点的环，即e*=(vi*,vi*)。实线边图为平面图，虚线边图为其对偶图。实线边图为平面图，虚线边图为其对偶图。从定义不难看出从定义不难看出G的对偶图的对偶图G*有以下性质：有以下性质：G*是平面图，而且是平面嵌入。是平面图，而且是平面嵌入。G*是连通图。是连通图。若边若边e为为G中的环，则中的环，则G*与与e对应

26、的边对应的边e*为桥，若为桥，若e为桥，则为桥，则G*中与中与e对应的边对应的边e*为环。为环。在多数情况下，在多数情况下，G*为多重图含平行边的图）。为多重图含平行边的图）。同构的平面图平面嵌入的对偶图不一定是同构的。同构的平面图平面嵌入的对偶图不一定是同构的。二、平面图与对偶图的阶数、边数与面数之间的关系。二、平面图与对偶图的阶数、边数与面数之间的关系。定理定理17.15 设设G*是连通平面图是连通平面图G的对偶图，的对偶图，n*、m*、r*和和n、 m、r分别为分别为G*和和G的顶点数、边数和面数，那么的顶点数、边数和面数，那么（1n*= r（2m*=m（3r*=n（4设设G*的顶点的顶

27、点v*i位于位于G的面的面Ri中，则中，则dG*(vi *)=deg(Ri)q (1)、(2)由由G*的构造可知是显然的。的构造可知是显然的。 q (3)由于由于G与与G*都连通，因而满足欧拉公式都连通，因而满足欧拉公式: q n-m+r = 2 n*-m*+r* = 2q 由由(1)、(2)可知，可知， r* = 2+m*-n* = 2+m-r = nq (4)设设G的面的面Ri的边界为的边界为Ci，设，设Ci中有中有k1(k10)条桥，条桥，k2个非个非桥边，于是桥边，于是q Ci的长度为的长度为k2+2k1，即，即deg(Ri)k2+2k1，q k1条桥对应条桥对应vi*处有处有k1个环

28、，个环，k2条非桥边对应从条非桥边对应从vi*处引出处引出k2条边，条边，q 所以所以dG*(vi*)k2+2k1deg(Ri)。证证明明定理定理17.16 17.16 设设G G* *是具有是具有k kk k2 2个连通分支的平面图个连通分支的平面图G G的的对偶图，对偶图， n n* *, m, m* *, r, r* *, n, m, r, n, m, r分别为分别为G G* *和和G G的顶点数、的顶点数、边数和面数，边数和面数，（1 1n n* *= r= r（2 2m m* *=m=m（3 3r r* *=n=nk+1k+1（4 4设设G G* *的顶点的顶点v v* *i i位于位于G G的面的面RiRi中，则中，则dGdG* *(v(v* *i)=deg(Ri)i)