平面图及图的着色

1、8.6 平面图平面图离离 散散 数数 学学周金明周金明说明说明平面图的基本概念平面图的基本概念欧拉公式欧拉公式平面图的判断平面图的判断平面图的对偶图平面图的对偶图顶点着色及点色数顶点着色及点色数地图的着色与平面图的点着色地图的着色与平面图的点着色8.1 平面图的基本概念平面图的基本概念一、关于平面图的一些基本概念一、关于平面图的一些基本概念1、 平面图的定义平面图的定义定义定义8.18.1 q G可嵌入曲面可嵌入曲面S如果图如果图G能以这样的方式画在曲面能以这样的方式画在曲面S上上，即除顶点处外无边相交。，即除顶点处外无边相交。 q G是可平面图或平面图是可平面图或平面图若若G可嵌入平面可嵌入

2、平面。q G的平面嵌入的平面嵌入画出的无边相交的平面图。画出的无边相交的平面图。q 非平面图非平面图无平面嵌入的图。无平面嵌入的图。（2）是（是（1）的平面嵌入，（）的平面嵌入，（4）是（）是（3）的平面嵌入。）的平面嵌入。2、 几点说明及一些简单结论几点说明及一些简单结论q 一般所谈平面图不一定是指平面嵌入，但讨论某些性质时，一般所谈平面图不一定是指平面嵌入，但讨论某些性质时，一定是指平面嵌入。一定是指平面嵌入。q K5和和K3,3都不是平面图。都不是平面图。q 定理定理8.1 8.1 设设GG，若若G为平面图，则为平面图，则G 也是平面图。也是平面图。q 定理定理8.2 8.2 设设GG，

3、若若G 为非平面图，则为非平面图，则G也是非平面图。也是非平面图。q 推论推论 Kn(n 5)和和K3,n(n 3)都是非平面图。都是非平面图。q 定理定理8.3 8.3 若若G为平面图，则在为平面图，则在G中加平行边或环所得图还是中加平行边或环所得图还是平面图。平面图。即平行边和环不影响图的平面性。即平行边和环不影响图的平面性。 二、平面图的面与次数（针对平面图的平面嵌入）二、平面图的面与次数（针对平面图的平面嵌入）1、 定义定义定义定义8.28.2 设设G是平面图，是平面图，q G的面的面由由G的边将的边将G所在的平面划分成的每一个区域。所在的平面划分成的每一个区域。q 无限面（外部面）无

4、限面（外部面）面积无限的面，记作面积无限的面，记作R0。q 有限面（内部面）有限面（内部面）面积有限的面面积有限的面 ，记作，记作R1, R2, , Rk。q 面面Ri的边界的边界包围面包围面Ri的所有边组成的回路组。的所有边组成的回路组。q 面面Ri的次数的次数Ri边界的长度，记作边界的长度，记作deg(Ri)。2、几点说明、几点说明q 若平面图若平面图G有有k个面，可笼统地用个面，可笼统地用R1, R2, , Rk表示，不需表示，不需要指出外部面。要指出外部面。q 回路组是指：边界可能是初级回路（圈），可能是简单回回路组是指：边界可能是初级回路（圈），可能是简单回路，也可能是复杂回路。特别

5、地，还可能是非连通的回路路，也可能是复杂回路。特别地，还可能是非连通的回路之并。之并。平面图有平面图有4个面，个面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8。 R1R2R3R0定理定理8.48.4 平面图平面图G中所有面的次数之和等于边数中所有面的次数之和等于边数m的两倍，即的两倍，即 本定理中所说平面图是指平面嵌入。本定理中所说平面图是指平面嵌入。 eE(G)，当当e为面为面Ri和和Rj(ij)的公共边界上的边时，在计算的公共边界上的边时，在计算Ri和和Rj的次的次数时，数时，e各提供各提供1。当当e只在某一个面的边界上出现时，则在计算该面的次数时

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

7、 K2, K3, K4都是极大平面图。都是极大平面图。2、极大平面图的主要性质、极大平面图的主要性质定理定理8.58.5 极大平面图是连通的。极大平面图是连通的。定理定理8.68.6 n(n 3)阶极大平面图中不可能有割点和桥。阶极大平面图中不可能有割点和桥。定理定理8.78.7 设设G为为n(n 3) )阶简单连通的平面图，阶简单连通的平面图，G为极大平面图为极大平面图当且仅当当且仅当G的每个面的次数均为的每个面的次数均为3。q本节只证明必要性，即本节只证明必要性，即设设G为为n(n 3) )阶简单连通的平面图，阶简单连通的平面图，G为极大平面图，则为极大平面图，则G的每个面的次数均为的每个

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

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

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

11、明证明对边数对边数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进行如下讨论。进行如下讨论。q 若若G是树，则是树，则G是非平凡的，因而是非平凡的，因而G中至少有两片树叶。中至少有两片树叶。 设设v为树叶，令为树叶，令G=G-v，则则G仍然是连通图，且仍然是连通图

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

13、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 (8.1)易知，易知，11kkiiiimmnn，由于每个由于每个Gi 有一个外部面，而有一个外部面，而G只有一个外部面，所以只有一个外部面，所以G的面数的面数11kiirrk于是，于是，对对(8.1)的两边同时求和得的两边同时求和得 11112()1kkkki

14、iiiiiiiiiknmrnmrnmrk 经整理得经整理得 n-m+r = k+1。2、 与欧拉公式有关的定理与欧拉公式有关的定理定理定理8.108.10 设设G为连通的平面图，且每个面的次数至少为为连通的平面图，且每个面的次数至少为l(l3)，则则 G的边数与顶点数有如下关系：的边数与顶点数有如下关系：由定理由定理8.4（面的次数之和等于边数的（面的次数之和等于边数的2倍）及欧拉公式得倍）及欧拉公式得(2)2lmnl证明证明12deg()(2)riimRl rlmn 解得解得 (2)2lmnl推论推论 K5, K3,3不是平面图。不是平面图。证明证明q若若K5是平面图，由于是平面图，由于K5

15、中无环和平行边，所以每个面的次数中无环和平行边，所以每个面的次数均大于或等于均大于或等于l3，由由定理定理17.10可知边数可知边数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也不是平面图。也不是平面图。 定理定理8.118.11 设设G是有是有k(k2)个连通分支的平面图，各面的次数个连通分支的平面图，各面的次数至少

16、为至少为l(l3)，则边数则边数m与顶点数与顶点数n应有如下关系：应有如下关系： (1)2lmnkl定理定理8.128.12 设设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是简单图，是简单图，所以，每个面至少由所以，每个面至少由l（l 3）条边围成，又在条边围成，又在l=3达到最大值达到最大值，由定理，由定理8.11可知可知证明证明2(1)(1

17、)(1)3(2)3622lmnknknnll定理定理8.138.13 设设G为为n(n 3)阶阶m条边的极大平面图，则条边的极大平面图，则m=3n 6。证明证明 由于极大平面图是连通图，由欧拉公式得由于极大平面图是连通图，由欧拉公式得: r=2+m-n (8.4) 又因为又因为G是极大平面图，由定理是极大平面图，由定理17.7的必要性可知，的必要性可知，G的每个的每个面的次数均为面的次数均为3，所以：，所以： 将将(8.4)代入代入(8.5)，整理后得，整理后得 m = 3n-6。12deg()3(8.5)riimRr二、一个意义重大的定理二、一个意义重大的定理 定理定理8.148.14 设设

18、G为简单平面图，则为简单平面图，则G的最小度的最小度 (G) 5。q 若阶数若阶数 n 6，结论显然成立。结论显然成立。q 若阶数若阶数n 7时，用反证法。时，用反证法。 假设假设 (G) 6，由握手定理可知：由握手定理可知：证明证明12( )6niimd vn因而因而m 3n，这与定理这与定理8.12矛盾。矛盾。所以，假设不成立，即所以，假设不成立，即G的最小度的最小度 (G) 5。q本定理在图着色理论中占重要地位。本定理在图着色理论中占重要地位。说说明明定理定理8.78.7 设设G为为n(n 3) )阶简单连通的平面图，阶简单连通的平面图，G为极大平面图为极大平面图当且仅当当且仅当G的每个

19、面的次数均为的每个面的次数均为3。（仅证。（仅证充分性充分性）由定理由定理17.4可知，可知，证证明明12( ) 3(8.6)niimd vr又因为又因为G是连通的，由欧拉公式可知是连通的，由欧拉公式可知2(8.7)rmn将将(8.7)代入代入(8.6)，经过整理得，经过整理得m=3n-6。 (8.8)若若G不是极大平面图，则不是极大平面图，则G中一定存在不相邻得顶点中一定存在不相邻得顶点u,v，使得使得G=G (u,v)还是简单平面图，而还是简单平面图，而G的边数的边数m=m+1，n=n。由由(8.8)可知，可知， m3n-6 ，这与定理这与定理8.2矛盾。矛盾。所以，所以，G为极大平面图。

20、为极大平面图。小节结束小节结束1、 插入插入2度顶点和消去度顶点和消去2度顶点度顶点定义定义8.5 8.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。8.3 8.3 平面图的判断平面图的判断2、图之间的同胚、图之间的同胚定义定义8.68.6 若两个图若两个图G1与与G2同构，或通过反复插入或消去同构，或通过反

21、复插入或消去2度顶点后是同构的，则称度顶点后是同构的，则称G1与与G2是是同胚同胚的。的。上面两个图分别与上面两个图分别与K3,3, K5同胚同胚 。二、两个判断定理二、两个判断定理 定理定理8.158.15(库拉图斯基定理库拉图斯基定理1) 图图G是平面图当且仅当是平面图当且仅当G中既不含中既不含与与K5同胚子图，也不含与同胚子图，也不含与K3,3同胚子图。同胚子图。 8.4 8.4 平面图的对偶图平面图的对偶图一、对偶图的定义一、对偶图的定义定义定义8.78.7 设设G是平面图，构造是平面图，构造G的对偶图的对偶图G*如下：如下：q 在在G的面的面Ri中放置中放置G*的顶点的顶点vi* 。

22、q 设设e为为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*)。实线边图为平面图，虚线边图为其对偶图。实线边图为平面图，虚线边图为其对偶图。从定义不难看出从定义不难看出G的对偶图的对偶图G*有以下性质：有以下性

23、质：q G*是平面图。是平面图。q G*是连通图。是连通图。q 若边若边e为为G中的环，则中的环，则G*与与e对应的边对应的边e*为桥，若为桥，若e为桥，为桥，则则G*中与中与e对应的边对应的边e*为环。为环。q 在多数情况下，在多数情况下，G*为多重图（含平行边的图）。为多重图（含平行边的图）。q 同构的平面图的对偶图不一定是同构的。同构的平面图的对偶图不一定是同构的。二、平面图与对偶图的阶数、边数与面数之间的关系。二、平面图与对偶图的阶数、边数与面数之间的关系。定理定理8.168.16 设设G*是连通平面图是连通平面图G的对偶图，的对偶图，n*、m*、r*和和n、 m、r分别为分别为G*和

24、和G的顶点数、边数和面数，则的顶点数、边数和面数，则（1）n*= r（2）m*=m（3）r*=nq (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证证明明定理定理8.178.17 设设G*是具有是具有k（k 2）个连通分支的平面图个连通分支的平面图G的对的对偶图，偶图， n*, m*, r*, n, m, r分别为分别为G*和和G的顶点数、边数和的顶点数、边数和面数，面数，

25、（1）n*= r（2）m*=m（3）r*=n k+1三、自对偶图三、自对偶图定义定义8.88.8 设设G*是平面图是平面图G的对偶图，若的对偶图，若G* G，则称则称G为自对偶为自对偶图。图。q 在在n 1(n 4)边形边形Cn 1内放置内放置1个顶点，使这个顶点与个顶点，使这个顶点与Cn 1上的上的所有的顶点均相邻，所得所有的顶点均相邻，所得n阶简单图称为阶简单图称为n阶轮图阶轮图。记为。记为Wn。 q n为奇数的轮图称为为奇数的轮图称为奇阶轮图奇阶轮图。q n为偶数的轮图称为为偶数的轮图称为偶阶轮图偶阶轮图。q 轮图都是自对偶图。轮图都是自对偶图。小节结束小节结束8.5 8.5 图中顶点的

26、着色图中顶点的着色规定：规定：点着色都是对无环无向图进行的。点着色都是对无环无向图进行的。一、关于顶点着色的基本概念一、关于顶点着色的基本概念定义定义8.98.9 （1）图）图G的一种着色的一种着色对无环图对无环图G的每个顶点涂上一种颜的每个顶点涂上一种颜 色，使相邻顶点涂不同的颜色。色，使相邻顶点涂不同的颜色。（2）对）对G进行进行k着色（着色（G是是k-可着色的）可着色的）能用能用k种颜色给种颜色给G 的顶点着色。的顶点着色。（3）G的色数的色数 (G)=kG是是k-可着色的，但不是可着色的，但不是(k 1)-可着可着 色的。色的。二、关于顶点着色的几个简单结果二、关于顶点着色的几个简单结

27、果定理定理8.188.18 (G)=1当且仅当当且仅当G为零图。为零图。定理定理8.198.19 (Kn)=n。 定理定理8.208.20 奇阶轮图的色数均为奇阶轮图的色数均为3，偶阶轮图的色数为偶阶轮图的色数为4。定理定理8.218.21 设设G中至少含有一条边，则中至少含有一条边，则 (G)=2当且仅当当且仅当G为二部图为二部图。三、色数的上界三、色数的上界定理定理8.228.22 对于任意无向图对于任意无向图G，均有均有 (G) (G)+1。q n=1时，结论成立。时，结论成立。q 设设n=k(k1)时结论成立，则当时结论成立，则当n=k+1时，时， 设设v为为G中任一个顶点，令中任一个

28、顶点，令G=G-v，则则G的阶数为的阶数为k，由假设由假设可知可知 (G) (G)+1 (G)+1。 当将当将G还原成还原成G时，由于时，由于v至多与至多与G中中(G)个顶点相邻，而在个顶点相邻，而在G的点着色中，的点着色中，(G)个顶点至多用了个顶点至多用了(G)种颜色，于是在种颜色，于是在(G)+1种颜色中至少存在一种颜色给种颜色中至少存在一种颜色给v涂色，使涂色，使v与相邻顶点与相邻顶点涂不同颜色。涂不同颜色。 证证明明提示：对提示：对G的阶数的阶数n作归纳法。作归纳法。例例 求下面各图的色数。求下面各图的色数。 定理定理8.23 8.23 ( (布鲁克斯定理布鲁克斯定理) 若连通无向图若连通无向图G不是不是Kn(n 3)，也不是也不是奇数阶的圈，则奇数阶的圈，则 (G) (G)。q 因为因为(1)为为二部图，由定理二部图，由定理8.21可知，可知， (G) =2。q (