离散数学教案平面图及图的着色.ppt

《离散数学教案平面图及图的着色.ppt》由会员分享，可在线阅读，更多相关《离散数学教案平面图及图的着色.ppt（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 1第第1717章章 平面图及图的着色平面图及图的着色离散数学离散数学 2本章说明本章说明q本章的主要内容本章的主要内容平面图的基本概念平面图的基本概念欧拉公式欧拉公式平面图的判断平面图的判断平面图的对偶图平面图的对偶图顶点着色及点色数顶点着色及点色数地图的着色与平面图的点着色地图的着色与平面图的点着色边着色及边色数边着色及边色数 3本章所涉及到的图均指无向图。本章所涉及到的图均指无向图。 4q 17.1 17.1 平面图的基本概念平面图的基本概念q 17.2 17.2 欧拉公式欧拉公式q 17.3 17.3 平面图的判断平面图的判断q 17.4 17.4 平面图的对偶图平面图的对偶图q 17

2、.5 17.5 图中顶点的着色图中顶点的着色q 17.6 17.6 地图的着色与平面图的点着色地图的着色与平面图的点着色q 17.7 17.7 边着色边着色q 本章小结本章小结q 习习 题题q 作作 业业 517.1 平面图的基本概念平面图的基本概念一、关于平面图的一些基本概念一、关于平面图的一些基本概念1、 平面图的定义平面图的定义定义定义17.117.1 q G可嵌入曲面可嵌入曲面S如果图如果图G能以这样的方式画在曲面能以这样的方式画在曲面S上上，即除顶点处外无边相交。，即除顶点处外无边相交。 q G是可平面图或平面图是可平面图或平面图若若G可嵌入平面可嵌入平面。q G的平面嵌入的平面嵌入

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

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

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

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

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

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

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

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

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

12、、m、r分别为分别为G的顶点数、边数和面数。的顶点数、边数和面数。 证明证明对边数对边数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中至少有两片树叶。中至少有两片树叶

13、。 设设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=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 18定理定理17.9

14、 17.9 对于具有对于具有k(k2)个连通分支的平面图个连通分支的平面图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)易知，易知，11kkiiiimmnn，由于每个由于每个Gi 有一个外部面，而有一个外部面，而G只有一个外部面，所以只有一个外部面，所以G的面数的面数11kiirrk

15、于是，于是，对对(17.1)的两边同时求和得的两边同时求和得 11112()1kkkkiiiiiiiiiiknmrnmrnmrk 经整理得经整理得 n-m+r = k+1。 192、 与欧拉公式有关的定理与欧拉公式有关的定理定理定理17.1017.10 设设G为连通的平面图，且每个面的次数至少为为连通的平面图，且每个面的次数至少为l(l3)，则则 G的边数与顶点数有如下关系：的边数与顶点数有如下关系：由定理由定理17.4（面的次数之和等于边数的（面的次数之和等于边数的2倍）及欧拉公式得倍）及欧拉公式得(2)2lmnl证明证明12deg()(2)riimRl rlmn 解得解得 (2)2lmnl

16、 20推论推论 K5, K3,3不是平面图。不是平面图。证明证明q若若K5是平面图，由于是平面图，由于K5中无环和平行边，所以每个面的次数中无环和平行边，所以每个面的次数均大于或等于均大于或等于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也不是平面图。也不是平面图。 21定理

17、定理17.1117.11 设设G是有是有k(k2)个连通分支的平面图，各面的次数个连通分支的平面图，各面的次数至少为至少为l(l3)，则边数则边数m与顶点数与顶点数n应有如下关系：应有如下关系： (1)2lmnkl定理定理17.1217.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是简单图，是简单图，所以，每个面至少由所以，每个面至少由

18、l（l 3）条边围成，又在条边围成，又在l=3达到最大值达到最大值，由定理，由定理17.11可知可知证明证明2(1)(1)(1)3(2)3622lmnknknnll 22定理定理17.1317.13 设设G为为n(n 3)阶阶m条边的极大平面图，则条边的极大平面图，则m=3n 6。证明证明 由于极大平面图是连通图，由欧拉公式得由于极大平面图是连通图，由欧拉公式得: r=2+m-n (17.4) 又因为又因为G是极大平面图，由定理是极大平面图，由定理17.7的必要性可知，的必要性可知，G的每个的每个面的次数均为面的次数均为3，所以：，所以： 将将(17.4)代入代入(17.5)，整理后得，整理后

19、得 m = 3n-6。12deg()3(17.5)riimRr 23二、一个意义重大的定理二、一个意义重大的定理 定理定理17.1417.14 设设G为简单平面图，则为简单平面图，则G的最小度的最小度 (G) 5。q 若阶数若阶数 n 6，结论显然成立。结论显然成立。q 若阶数若阶数n 7时，用反证法。时，用反证法。 假设假设 (G) 6，由握手定理可知：由握手定理可知：证明证明12( )6niimd vn因而因而m 3n，这与定理这与定理17.12矛盾。矛盾。所以，假设不成立，即所以，假设不成立，即G的最小度的最小度 (G) 5。q本定理在图着色理论中占重要地位。本定理在图着色理论中占重要地

20、位。说说明明 24定理定理17.717.7 设设G为为n(n 3) )阶简单连通的平面图，阶简单连通的平面图，G为极大平面为极大平面图当且仅当图当且仅当G的每个面的次数均为的每个面的次数均为3。（仅证。（仅证充分性充分性）由定理由定理17.4可知，可知，证证明明12( ) 3(17.6)niimd vr又因为又因为G是连通的，由欧拉公式可知是连通的，由欧拉公式可知2(17.7)rmn将将(17.7)代入代入(17.6)，经过整理得，经过整理得m=3n-6。 (17.8)若若G不是极大平面图，则不是极大平面图，则G中一定存在不相邻得顶点中一定存在不相邻得顶点u,v，使得使得G=G (u,v)还是

21、简单平面图，而还是简单平面图，而G的边数的边数m=m+1，n=n。由由(17.8)可知，可知， m3n6，这与定理这与定理17.2矛盾。矛盾。所以，所以，G为极大平面图。为极大平面图。小节结束小节结束 25一、为判断定理做准备一、为判断定理做准备1、 插入插入2度顶点和消去度顶点和消去2度顶点度顶点定义定义17.5 17.5 q 设设e=(u,v)为图为图G的一条边，在的一条边，在G中删除中删除e，增加新的顶点增加新的顶点w，使使u、v均与均与w相邻，称为在相邻，称为在G中中插入插入2度顶点度顶点w。q 设设w为为G中一个中一个2度顶点，度顶点，w与与u、v相邻，删除相邻，删除w，增加新边增加

22、新边(u,v)，称为在称为在G中中消去消去2度顶点度顶点w。17.3 17.3 平面图的判断平面图的判断 262、图之间的同胚、图之间的同胚定义定义17.617.6 若两个图若两个图G1与与G2同构，或通过反复插入或消去同构，或通过反复插入或消去2度顶点后是同构的，则称度顶点后是同构的，则称G1与与G2是是同胚同胚的。的。上面两个图分别与上面两个图分别与K3,3, K5同胚同胚 。 27二、两个判断定理二、两个判断定理 定理定理17.1517.15(库拉图斯基定理库拉图斯基定理1) 图图G是平面图当且仅当是平面图当且仅当G中既不中既不含与含与K5同胚子图，也不含与同胚子图，也不含与K3,3同胚

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

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

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

26、定理可为子图，由库拉图斯基定理可知，它们都是非平面图。知，它们都是非平面图。 在加在加2条、加条、加3条、加条、加4条边时又各产生两个非同构的非平面图，条边时又各产生两个非同构的非平面图，连同连同K3,3本身共有本身共有10个满足要求的非平面图。其中，绿线边表示个满足要求的非平面图。其中，绿线边表示后加的新边。后加的新边。 解答解答小节结束小节结束 3117.4 17.4 平面图的对偶图平面图的对偶图一、对偶图的定义一、对偶图的定义定义定义17.717.7 设设G是某平面图的某个平面嵌入，构造是某平面图的某个平面嵌入，构造G的对偶图的对偶图G*如下：如下：q 在在G的面的面Ri中放置中放置G*

27、的顶点的顶点vi* 。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*)。 32实线边图为平面图，虚线边图为其对偶图。实线边图为平面图，虚线边图为其对偶图。 33从定义不难看出从定义不难看出G的对偶

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

29、G*是连通平面图是连通平面图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) 35q (1)、(2)由由G*的构造可知是显然的。的构造可知是显然的。 q (3)由于由于G与与G*都连通，因而满足欧拉公式都连通，因而满足欧拉公式: n-m+r = 2 n*-m*+r* = 2 由由(1)、(2)可知，可知， r* = 2+m*-n* = 2+m-r = nq (4)设设G的面的面

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

31、*=m（3）r*=n k+1（4）设设G*的顶点的顶点v*i位于位于G的面的面Ri中，则中，则dG*(v*i)=deg(Ri) 37三、自对偶图三、自对偶图定义定义17.817.8 设设G*是平面图是平面图G的对偶图，若的对偶图，若G* G，则称则称G为自对偶为自对偶图。图。 38q 在在n 1(n 4)边形边形Cn 1内放置内放置1个顶点，使这个顶点与个顶点，使这个顶点与Cn 1上的上的所有的顶点均相邻，所得所有的顶点均相邻，所得n阶简单图称为阶简单图称为n阶轮图阶轮图。记为。记为Wn。 q n为奇数的轮图称为为奇数的轮图称为奇阶轮图奇阶轮图。q n为偶数的轮图称为为偶数的轮图称为偶阶轮图偶

32、阶轮图。q 轮图都是自对偶图。轮图都是自对偶图。小节结束小节结束 3917.5 17.5 图中顶点的着色图中顶点的着色规定：规定：点着色都是对无环无向图进行的。点着色都是对无环无向图进行的。一、关于顶点着色的基本概念一、关于顶点着色的基本概念定义定义17.917.9 （1）图）图G的一种着色的一种着色对无环图对无环图G的每个顶点涂上一种颜的每个顶点涂上一种颜 色，使相邻顶点涂不同的颜色。色，使相邻顶点涂不同的颜色。（2）对）对G进行进行k着色（着色（G是是k-可着色的）可着色的）能用能用k种颜色给种颜色给G 的顶点着色。的顶点着色。（3）G的色数的色数 (G)=kG是是k-可着色的，但不是可着

33、色的，但不是(k 1)-可着可着 色的。色的。 40二、关于顶点着色的几个简单结果二、关于顶点着色的几个简单结果定理定理17.1917.19 (G)=1当且仅当当且仅当G为零图。为零图。定理定理17.2017.20 (Kn)=n。 定理定理17.2117.21 奇圈或奇阶轮图的色数均为奇圈或奇阶轮图的色数均为3，偶阶轮图的色数为偶阶轮图的色数为4。定理定理17.2217.22 设设G中至少含有一条边，则中至少含有一条边，则 (G)=2当且仅当当且仅当G为二部为二部图。图。 41三、色数的上界三、色数的上界定理定理17.2317.23 对于任意无向图对于任意无向图G，均有均有 (G) (G)+1

34、。q n=1时，结论成立。时，结论成立。q 设设n=k(k1)时结论成立，则当时结论成立，则当n=k+1时，时， 设设v为为G中任一个顶点，令中任一个顶点，令G=G-v，则则G的阶数为的阶数为k，由假设由假设可知可知 (G) (G)+1 (G)+1。 当将当将G还原成还原成G时，由于时，由于v至多与至多与G中中(G)个顶点相邻，而在个顶点相邻，而在G的点着色中，的点着色中，(G)个顶点至多用了个顶点至多用了(G)种颜色，于是在种颜色，于是在(G)+1种颜色中至少存在一种颜色给种颜色中至少存在一种颜色给v涂色，使涂色，使v与相邻顶点与相邻顶点涂不同颜色。涂不同颜色。 证证明明提示：对提示：对G的

35、阶数的阶数n作归纳法。作归纳法。 42例例17.417.4 求下面各图的色数。求下面各图的色数。 定理定理17.24 17.24 ( (布鲁克斯定理布鲁克斯定理) 若连通无向图若连通无向图G不是不是Kn(n 3)，也不也不是奇数阶的圈，则是奇数阶的圈，则 (G) (G)。q 因为因为(1)为为二部图，由定理二部图，由定理17.22可知，可知， (G) =2。q (2)为为6阶轮图阶轮图W6，由定理由定理17.21可知，可知， (G) =4。q 由定理由定理17.24可知，可知， (G)4，又因为又因为(3)中有奇圈，于是中有奇圈，于是 (G) 3，因而因而 (G)为为3或或4，用，用3种颜色不

36、可能给种颜色不可能给G4着色，于是只能着色，于是只能是是 (G) =4。解答解答小节结束小节结束 4317.6 17.6 地图的着色与平面图的点着色地图的着色与平面图的点着色一、地图与面着色一、地图与面着色1、地图与国家、地图与国家定义定义17.1017.10 （1）地图）地图连通无桥平面图的平面嵌入与所有的面。连通无桥平面图的平面嵌入与所有的面。（2）国家）国家地图的面。地图的面。（3）两个国家相邻）两个国家相邻两个国家的边界至少有一条公共边。两个国家的边界至少有一条公共边。有有5个国家，个国家，1与与2相邻，相邻，1与与4相邻，相邻，2,3,4均与均与5相邻。相邻。54123 442、地图

37、的面着色、地图的面着色定义定义17.1117.11（1）地图）地图G的一种面着色的一种面着色对地图对地图G的每个国家涂上一种的每个国家涂上一种 颜色，使相邻国家涂不同的颜色。颜色，使相邻国家涂不同的颜色。（2）G是是k-面可着色的面可着色的能用能用k种颜色给种颜色给G的面着色，就称的面着色，就称 对对G的面进行了的面进行了k着色。着色。（3）G的面色数的面色数 *(G)=kG是是k-面可着色的，但不是面可着色的，但不是(k-1)- 面可着色的，即最少用面可着色的，即最少用k种颜色给种颜色给G的面着色。的面着色。 q研究地图的着色可以转化成对它的对偶图的点着色研究地图的着色可以转化成对它的对偶图

38、的点着色 。说说明明 45二、地图的面着色转化成对偶图的点着色二、地图的面着色转化成对偶图的点着色定理定理17.2517.25 地图地图G是是k-面可着色的当且仅当它的对偶图面可着色的当且仅当它的对偶图G*是是k-点可着色的。点可着色的。三、五色定理三、五色定理定理定理17.2617.26 任何平面图都是任何平面图都是5-可着色的可着色的 。 四色猜想四色猜想问题，提出来已经近问题，提出来已经近150年了，但时至今日还没有年了，但时至今日还没有得到彻底解决。得到彻底解决。 小节结束小节结束 4617.7 17.7 边着色边着色本节讨论的图是无环的无向图。本节讨论的图是无环的无向图。一、对图一、

39、对图G进行边着色进行边着色定义定义17.1217.12 （1）对图对图G边的一种着色边的一种着色对图对图G的每条边涂上一种颜色，的每条边涂上一种颜色， 使相邻的边涂不同的颜色使相邻的边涂不同的颜色。（2）G是是k-边可着色的边可着色的能用能用k种颜色给种颜色给G的边着色。的边着色。（3）G的边色数的边色数(G)=k若若G是是k-边可着色的，但不是边可着色的，但不是 (k-1)-边可着色的，即边可着色的，即最少用最少用k种颜色给种颜色给G的边着色。的边着色。 47二、关于边着色的一些定理二、关于边着色的一些定理 定理定理17.2717.27 G为简单平面图，则为简单平面图，则 (G) (G) (

40、G)+1。q 该定理是维津定理。该定理是维津定理。q 定理说明，对简单图来说，它的边色数定理说明，对简单图来说，它的边色数只能取它的只能取它的 (G) ，或者是它的或者是它的 (G) +1。q 究竟哪些图的究竟哪些图的 (G)是是 (G) ，哪些是哪些是 (G) +1，至今还是至今还是 一个没有解决的问题。一个没有解决的问题。定理定理17.2817.28 设设G为长度大于或等于为长度大于或等于2的偶圈，则的偶圈，则(G)=(G)=2.设设G为长度大于或等于为长度大于或等于3的奇圈，则的奇圈，则(G)=(G)+1=3. 48q n=4时时，由维津定理可知，结论正确。由维津定理可知，结论正确。q

41、n=5时，由维津定理可知，结论正确。时，由维津定理可知，结论正确。q n6时，时，(Wn)=n-15，Wn中间顶点关联的中间顶点关联的n-1条边必须用条边必须用n-1种颜色着色。种颜色着色。 而外圈而外圈Cn-1上的任何边都准确的与其余的上的任何边都准确的与其余的4条边相邻，于是总条边相邻，于是总可以找到可以找到n-1种色中的一种为它涂色，所以种色中的一种为它涂色，所以(Wn)n-1。 又由维津定理可知，又由维津定理可知，(Wn)n-1，所以所以(Wn)=n-1。定理定理17.2917.29 (Wn) = (Wn) = n 1，其中其中n 4。定理定理17.3017.30 二部图的边色数等于最

42、大度。二部图的边色数等于最大度。证证明明 49定理定理17.3117.31 当当n(n 1)为奇数时，为奇数时， (Kn)=n；当当n为偶数时，为偶数时， (Kn)=n 1。例例17.517.5 证明证明(W4)=(W4)=3，(W5)=(W5)=4。由维津定理可知结论是正确的。由维津定理可知结论是正确的。 解答解答 50例例17.617.6 求下面所示各图的边色数。求下面所示各图的边色数。 小节结束小节结束q (1)中无奇长回路，所以它为二部图，由定理中无奇长回路，所以它为二部图，由定理17.30可知可知=4。q 由维津定理可知，由维津定理可知，(2)中中=4，又存在又存在4种颜色的边着色，

43、种颜色的边着色，所以所以4，因而因而=4。解答解答 51本章主要内容本章主要内容q 平面图及平面嵌入。平面图及平面嵌入。 q 平面图的面与次数。平面图的面与次数。 q 极大平面图及性质。极大平面图及性质。 q 极小非平面图。极小非平面图。 q 欧拉公式及其推广。欧拉公式及其推广。q 平面图的边数平面图的边数m与顶点数与顶点数n的关系。的关系。q 简单平面图简单平面图G中，中，(G)5。q 库拉图斯基的两个定理。库拉图斯基的两个定理。q 平面图的对偶图。平面图的对偶图。 52本章主要内容本章主要内容q 顶点的着色与点色数。顶点的着色与点色数。q 关于点色数的一些定理。关于点色数的一些定理。q 地

44、图及其面着色、面色数。地图及其面着色、面色数。q 平面图的五色定理。平面图的五色定理。q 边着色及边色数。边着色及边色数。q 关于边着色的一些定理。关于边着色的一些定理。 53本章学习要求本章学习要求q 深刻理解本部分的基本概念：平面图、平面嵌入、平面图的深刻理解本部分的基本概念：平面图、平面嵌入、平面图的面、次数、极大平面图、极小非平面图、平面图的对偶图、面、次数、极大平面图、极小非平面图、平面图的对偶图、自对偶图等。自对偶图等。 q 熟练掌握极大平面的性质，特别是充分必要条件。熟练掌握极大平面的性质，特别是充分必要条件。 q 熟练掌握并会应用欧拉公式及其推广形式。熟练掌握并会应用欧拉公式及

45、其推广形式。 q 掌握由欧拉公式及其推广形式所证明的平面的性质。掌握由欧拉公式及其推广形式所证明的平面的性质。 q 会用库拉图斯基定理证明某些图不是平面图。会用库拉图斯基定理证明某些图不是平面图。 q 掌握平面图与其对偶图某些关系的定理。掌握平面图与其对偶图某些关系的定理。 54q 深刻理解点着色、边着色、点色数、边色数的概念。深刻理解点着色、边着色、点色数、边色数的概念。 q 理解并记住地图面着色与它的对偶图点着色的关系的定理解并记住地图面着色与它的对偶图点着色的关系的定理。理。 q 会应用点色数及边色数解决一些简单的实际问题。会应用点色数及边色数解决一些简单的实际问题。 小节结束小节结束 55 1 设 G 是连通的简单的平面图，面数 r12，(G)3. （1）证明 G 中存在次数4 的面 （2）举例说明当 r=12 时， （1）中结论不真. 56解 57 58 59证 60证 61 62 63解 64 65图20 图19 66 67 68解 小节结束小节结束 69作业作业习题十七习题十七： 1 1、3 3、1515、2424、2626、2929结束结束