离散数学平面图PPT优秀课件

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

2、概念平面图的基本概念 一、关于平面图的一些基本概念一、关于平面图的一些基本概念 1、 平面图的定义平面图的定义 定义定义17.117.1 q G可嵌入曲面可嵌入曲面S如果图如果图G能以这样的方式画在曲面能以这样的方式画在曲面S上，上， 即除顶点处外无边相交。即除顶点处外无边相交。 q G是可平面图或平面图是可平面图或平面图若若G可嵌入平面可嵌入平面。 q G的平面嵌入的平面嵌入画出的无边相交的平面图。画出的无边相交的平面图。 q 非平面图非平面图无平面嵌入的图。无平面嵌入的图。 6 （2）是（是（1）的平面嵌入，（）的平面嵌入，（4）是（）是（3）的平面嵌入。）的平面嵌入。 7 2、 几点说明

3、及一些简单结论几点说明及一些简单结论 q 一般所谈平面图不一定是指平面嵌入，但讨论某些性质时，一般所谈平面图不一定是指平面嵌入，但讨论某些性质时， 一定是指平面嵌入。一定是指平面嵌入。 q K5和和K3,3都不是平面图。都不是平面图。 q 定理定理17.117.1 设设GG，若若G为平面图，则为平面图，则G 也是平面图。也是平面图。 q 设设GG，若若G 为非平面图，则为非平面图，则G也是非平面图。也是非平面图。 q 由定理可知，由定理可知， Kn(n 5)和和K3,n(n 3)都是非平面图。都是非平面图。 q 定理定理17.17.2 2 若若G为平面图，则在为平面图，则在G中加平行边或环所得

4、图还是中加平行边或环所得图还是 平面图。平面图。 即平行边和环不影响图的平面性。即平行边和环不影响图的平面性。 8 二、平面图的面与次数（针对平面图的平面嵌入）二、平面图的面与次数（针对平面图的平面嵌入） 1、 定义定义 定义定义17.217.2 设设G是平面图，是平面图， q G的面的面由由G的边将的边将G所在的平面划分成的每一个区域。所在的平面划分成的每一个区域。 q 无限面（外部面）无限面（外部面）面积无限的面，记作面积无限的面，记作R0。 q 有限面（内部面）有限面（内部面）面积有限的面面积有限的面 ，记作，记作R1, R2, , Rk。 q 面面Ri的边界的边界包围面包围面Ri的所有

5、边组成的回路组。的所有边组成的回路组。 q 面面Ri的次数的次数Ri边界的长度，记作边界的长度，记作deg(Ri)。 9 2、几点说明、几点说明 q 若平面图若平面图G有有k个面，可笼统地用个面，可笼统地用R1, R2, , Rk表示，不需表示，不需 要指出外部面。要指出外部面。 q 回路组是指：边界可能是初级回路（圈），可能是简单回回路组是指：边界可能是初级回路（圈），可能是简单回 路，也可能是复杂回路。特别地，还可能是非连通的回路路，也可能是复杂回路。特别地，还可能是非连通的回路 之并。之并。 平面图有平面图有4个面，个面，deg(R1)=1, deg(R2)=3, deg(R3)=2,

6、deg(R0)=8。 R1 R2 R3 R0 10 定理定理17.17.3 3 平面图平面图G中所有面的次数之和等于边数中所有面的次数之和等于边数m的两倍，即的两倍，即 本定理中所说平面图是指平面嵌入。本定理中所说平面图是指平面嵌入。 eE(G)， 当当e为面为面Ri和和Rj(ij)的公共边界上的边时，在计算的公共边界上的边时，在计算Ri和和Rj的次的次 数时，数时，e各提供各提供1。 当当e只在某一个面的边界上出现时，则在计算该面的次数时只在某一个面的边界上出现时，则在计算该面的次数时 ，e提供提供2。 于是每条边在计算总次数时，都提供于是每条边在计算总次数时，都提供2，因而，因而deg(R

7、i)=2m。 1 deg()2 r i i RmrG 其中 为 的面数 证证 明明 11 三、极大平面图三、极大平面图 1、 定义定义 定义定义17.317.3 若在简单平面图若在简单平面图G中的任意两个不相邻的顶点之中的任意两个不相邻的顶点之 间加一条新边所得图为非平面图，则称间加一条新边所得图为非平面图，则称G为极大平面图。为极大平面图。 注意：注意：若简单平面图若简单平面图G中已无不相邻顶点，中已无不相邻顶点，G显然是极大平显然是极大平 面图，如面图，如K1（平凡图）平凡图）, K2, K3, K4都是极大平面图。都是极大平面图。 2、极大平面图的主要性质、极大平面图的主要性质 定理定理

8、17.17.4 4 极大平面图是连通的，并且极大平面图是连通的，并且n(n 3)阶极大平面图阶极大平面图 中不可能有割点和桥。中不可能有割点和桥。 12 定理定理17.17.5 5 设设G为为n(n 3) )阶简单连通的平面图，阶简单连通的平面图，G为极大平面图为极大平面图 当且仅当当且仅当G的每个面的次数均为的每个面的次数均为3。 q本节只证明必要性，即本节只证明必要性，即设设G为为n(n 3) )阶简单连通的平面图，阶简单连通的平面图，G 为极大平面图，则为极大平面图，则G的每个面的次数均为的每个面的次数均为3。 q由于由于n 3, 又又G必为简单平面图，可知，必为简单平面图，可知，G每个

9、面的次数均每个面的次数均 3。 q因为因为G为平面图，又为极大平面图。可证为平面图，又为极大平面图。可证G不可能存在次数不可能存在次数3 的面。的面。 证证 明明 思思 路路 13 假设存在面假设存在面Ri的次数的次数deg(Ri)=s4， 如图所示。如图所示。 在在G中，若中，若v1与与v3不相邻，在不相邻，在Ri内加边内加边(v1,v3)不破坏平面性，这不破坏平面性，这 与与G是极大平面图矛盾，因而是极大平面图矛盾，因而v1与与v3必相邻，由于必相邻，由于Ri的存在，的存在， 边边(v1,v3)必在必在Ri外。外。 类似地，类似地，v2与与v4也必相邻，且边也必相邻，且边(v2,v4)也必

10、在也必在Ri外部，于是必外部，于是必 产生产生(v1,v3)与与(v2,v4)相交于相交于Ri的外部，这又矛盾于的外部，这又矛盾于G是平面图，是平面图， 所以必有所以必有s3，即即G中不存在次数大于或等于中不存在次数大于或等于4的面，所以的面，所以G的的 每个面为每个面为3条边所围，也就是各面次数均为条边所围，也就是各面次数均为3。 s S-1 14 只有右边的图为极大平面图。只有右边的图为极大平面图。 因为只有该图每个面的次数都为因为只有该图每个面的次数都为3。 15 四、极小非平面图四、极小非平面图 定义定义17.417.4 若在非平面图若在非平面图G中任意删除一条边，所得图中任意删除一条

11、边，所得图G为平面为平面 图，则称图，则称G为极小非平面图。为极小非平面图。 由定义不难看出：由定义不难看出： q K5, K3,3都是极小非平面图。都是极小非平面图。 q 极小非平面图必为简单图。极小非平面图必为简单图。 例如：例如：以下各图均为极小非平面图。以下各图均为极小非平面图。 16 17.2 17.2 欧拉公式欧拉公式 一、欧拉公式相关定理一、欧拉公式相关定理 1、 欧拉公式欧拉公式 定理定理17.17.6 6 对于任意的连通的平面图对于任意的连通的平面图G，有有 n-m+r=2 其中，其中，n、m、r分别为分别为G的顶点数、边数和面数。的顶点数、边数和面数。 证明证明 对边数对边

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

13、，且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 q 若若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 18 定理定理17.17.7 7 对于具有对于具有k(k2)个连通分支的平面图个连通分支

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

15、边同时求和得的两边同时求和得 1111 2()1 kkkk iiiiii iiii knmrnmrnmrk 经整理得经整理得 n-m+r = k+1。 19 2、 与欧拉公式有关的定理与欧拉公式有关的定理 定理定理17.17.8 8 设设G为连通的平面图，且每个面的次数至少为为连通的平面图，且每个面的次数至少为 l(l3)，则则 G的边数与顶点数有如下关系：的边数与顶点数有如下关系： 由定理由定理17.3（面的次数之和等于边数的（面的次数之和等于边数的2倍）及欧拉公式得倍）及欧拉公式得 (2) 2 l mn l 证明证明 1 2deg()(2) r i i mRl rlmn 解得解得 (2)

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

17、也不是平面图。 21 定理定理17.17.9 9 设设G是有是有k(k2)个连通分支的平面图，各面的次数至个连通分支的平面图，各面的次数至 少为少为l(l3)，则边数则边数m与顶点数与顶点数n应有如下关系：应有如下关系： (1) 2 l mnk l 定理定理17.117.10 0 设设G为为n(n 3)阶阶m条边的简单平面图，则条边的简单平面图，则m 3n 6。 设设G有有k(k 1)个连通分支，个连通分支， q 若若G为树或森林，当为树或森林，当n 3时，时，m=n-k 3n 6为真。为真。 q 若若G不是树也不是森林，则不是树也不是森林，则G中必含圈，又因为中必含圈，又因为G是简单图，是简

18、单图， 所以，每个面至少由所以，每个面至少由l（l 3）条边围成，又在条边围成，又在l=3达到最大值达到最大值 ，由定理，由定理17.9可知可知 证明证明 2 (1)(1)(1)3(2)36 22 l mnknknn ll 22 定理定理17.117.11 1 设设G为为n(n 3)阶阶m条边的极大平面图，则条边的极大平面图，则m=3n 6。 证明证明 由于极大平面图是连通图，由欧拉公式得由于极大平面图是连通图，由欧拉公式得: r=2+m-n (17.4) 又因为又因为G是极大平面图，由定理是极大平面图，由定理17.7的必要性可知，的必要性可知，G的每个的每个 面的次数均为面的次数均为3，所以

19、：，所以： 将将(17.4)代入代入(17.5)，整理后得，整理后得 m = 3n-6。 1 2deg()3(17.5) r i i mRr 23 二、一个意义重大的定理二、一个意义重大的定理 定理定理17.117.12 2 设设G为简单平面图，则为简单平面图，则G的最小度的最小度 (G) 5。 q 若阶数若阶数 n 6，结论显然成立。结论显然成立。 q 若阶数若阶数n 7时，用反证法。时，用反证法。 假设假设 (G) 6，由握手定理可知：由握手定理可知： 证明证明 1 2( )6 n i i md vn 因而因而m 3n，这与定理这与定理17.10矛盾。矛盾。 所以，假设不成立，即所以，假设

20、不成立，即G的最小度的最小度 (G) 5。 q本定理在图着色理论中占重要地位。本定理在图着色理论中占重要地位。 24 一、为判断定理做准备一、为判断定理做准备 1、 插入插入2度顶点和消去度顶点和消去2度顶点度顶点 定义定义17.517.5 q 设设e=(u,v)为图为图G的一条边，在的一条边，在G中删除中删除e，增加新的顶点增加新的顶点w， 使使u、v均与均与w相邻，称为在相邻，称为在G中中插入插入2度顶点度顶点w。 q 设设w为为G中一个中一个2度顶点，度顶点，w与与u、v相邻，删除相邻，删除w，增加新边增加新边 (u,v)，称为在称为在G中中消去消去2度顶点度顶点w。 17.3 17.3

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

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

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

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

25、们都是非平面图。知，它们都是非平面图。 在加在加2条、加条、加3条、加条、加4条边时又各产生两个非同构的非平面图，条边时又各产生两个非同构的非平面图， 连同连同K3,3本身共有本身共有10个满足要求的非平面图。其中，绿线边表示个满足要求的非平面图。其中，绿线边表示 后加的新边。后加的新边。 解答解答 30 17.4 17.4 平面图的对偶图平面图的对偶图 一、对偶图的定义一、对偶图的定义 定义定义17.17.6 6 设设G是某平面图的某个平面嵌入，构造是某平面图的某个平面嵌入，构造G的对偶图的对偶图 G*如下：如下： q 在在G的面的面Ri中放置中放置G*的顶点的顶点vi* 。 q 设设e为为

26、G的任意一条边，的任意一条边， 若若e在在G的面的面Ri与与Rj的公共边界上，做的公共边界上，做G*的边的边e*与与e相交，相交， 且且e*关联关联G*的位于的位于Ri与与Rj中的顶点中的顶点vi*与与vj*，即即e*=(vi*,vj*) ，e*不与其它任何边相交。不与其它任何边相交。 若若e为为G中的桥且在面中的桥且在面Ri的边界上，则的边界上，则e*是以是以Ri中中G*的顶点的顶点 vi*为端点的环，即为端点的环，即e*=(vi*,vi*)。 31 实线边图为平面图，虚线边图为其对偶图。实线边图为平面图，虚线边图为其对偶图。 32 从定义不难看出从定义不难看出G的对偶图的对偶图G*有以下性

27、质：有以下性质： q G*是平面图，而且是平面嵌入。是平面图，而且是平面嵌入。 q G*是连通图。是连通图。 q 若边若边e为为G中的环，则中的环，则G*与与e对应的边对应的边e*为桥，若为桥，若e为桥，为桥， 则则G*中与中与e对应的边对应的边e*为环。为环。 q 在多数情况下，在多数情况下，G*为多重图（含平行边的图）。为多重图（含平行边的图）。 q 同构的平面图（平面嵌入）的对偶图不一定是同构的。同构的平面图（平面嵌入）的对偶图不一定是同构的。 33 二、平面图与对偶图的阶数、边数与面数之间的关系。二、平面图与对偶图的阶数、边数与面数之间的关系。 定理定理17.117.15 5 设设G*

28、是连通平面图是连通平面图G的对偶图，的对偶图，n*、m*、r*和和n 、 m、r分别为分别为G*和和G的顶点数、边数和面数，则的顶点数、边数和面数，则 （1）n*= r （2）m*=m （3）r*=n （4）设设G*的顶点的顶点v*i位于位于G的面的面Ri中，则中，则dG*(vi *)=deg(Ri) 34 q (1)、(2)由由G*的构造可知是显然的。的构造可知是显然的。 q (3)由于由于G与与G*都连通，因而满足欧拉公式都连通，因而满足欧拉公式: n-m+r = 2 n*-m*+r* = 2 由由(1)、(2)可知，可知， r* = 2+m*-n* = 2+m-r = n q (4)设设

29、G的面的面Ri的边界为的边界为Ci，设设Ci中有中有k1(k10)条桥，条桥，k2个非桥边个非桥边 ，于是，于是 Ci的长度为的长度为k2+2k1，即即deg(Ri)k2+2k1， k1条桥对应条桥对应vi*处有处有k1个环，个环，k2条非桥边对应从条非桥边对应从vi*处引出处引出k2条边，条边， 所以所以dG*(vi*)k2+2k1deg(Ri)。 证证 明明 35 定理定理17.117.16 6 设设G*是具有是具有k（k 2）个连通分支的平面图个连通分支的平面图G的的 对偶图，对偶图， n*, m*, r*, n, m, r分别为分别为G*和和G的顶点数、边数的顶点数、边数 和面数，和面数， （1）n*= r （2）m*=m （3）r*=n k+1 （4）设设G*的顶点的顶点v*i位于位于G的面的面Ri中，则中，则dG*(v*i)=deg(Ri) 36 三、自对偶图三、自对偶图 定义定义17.17