《平面图及图的着色》PPT课件.ppt

《《平面图及图的着色》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《平面图及图的着色》PPT课件.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

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

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

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

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

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

10、v4)相交于相交于Ri的外部，这又矛盾于的外部，这又矛盾于G是平面图，是平面图，所以必有所以必有s3，即即G中不存在次数大于或等于中不存在次数大于或等于4的面，所以的面，所以G的的每个面为每个面为3条边所围，也就是各面次数均为条边所围，也就是各面次数均为3。sS-1只有右边的图为极大平面图。只有右边的图为极大平面图。因为只有该图每个面的次数都为因为只有该图每个面的次数都为3。四、极小非平面图四、极小非平面图若若在在非非平平面面图图G中中任任意意删删除除一一条条边边，所所得得图图G 为为平平面面图图，则则称称G为极小非平面图。为极小非平面图。由定义不难看出：由定义不难看出：qK5,K3,3都是极

11、小非平面图。都是极小非平面图。q极小非平面图必为简单图。极小非平面图必为简单图。例如：例如：以下各图均为极小非平面图。以下各图均为极小非平面图。小节结束小节结束17.2 17.2 欧拉公式欧拉公式 一、欧拉公式相关定理一、欧拉公式相关定理1、欧拉公式欧拉公式定理定理17.8 17.8 对于任意的连通的平面图对于任意的连通的平面图G，有有n-m+r=2其中，其中，n、m、r分别为分别为G的顶点数、边数和面数。的顶点数、边数和面数。证明证明对边数对边数m作归纳法。作归纳法。(1)m0时，由于时，由于G为连通图，所以为连通图，所以G只能是由一个孤立顶只能是由一个孤立顶点组成的平凡图，即点组成的平凡图

12、，即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仍然是连通图，且仍然是连通图，且G的边数的边数m=m-1=k，n=n-1，r=r。由假设可知由假设可知n-m+r=2，式中式中n，m，r分别为分别为G的顶点数，的顶点数，边数和面数。边数和面数。于是于是n

13、-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定理定理17.9 17.9 对于具有对于具有k(k2)个连通分支的平面图个连通分支的平面图G，有有n-m+r=k+1其中其中n，m，r分别为分别为G的顶点数，边数和面数。的顶点数，边数和面数。证明证明设设G的连通分支分别为的连通分支分别为G1、G2、Gk，并设并设Gi的顶点数、边的顶点数、边数

14、、面数分别为数、面数分别为ni、mi、ri、i=1，2，k。由欧拉公式可知由欧拉公式可知:ni-mi+ri=2，i=1，2，k(17.1)易知，易知，由于每个由于每个Gi有一个外部面，而有一个外部面，而G只有一个外部面，所以只有一个外部面，所以G的面数的面数于是，于是，对对(17.1)的两边同时求和得的两边同时求和得经整理得经整理得n-m+r=k+1。2、与欧拉公式有关的定理与欧拉公式有关的定理设设G为为连连通通的的平平面面图图，且且每每个个面面的的次次数数至至少少为为l(l3)，则则G的边数与顶点数有如下关系：的边数与顶点数有如下关系：由定理由定理17.4（面的次数之和等于边数的（面的次数之

15、和等于边数的2倍）及欧拉公式得倍）及欧拉公式得证明证明解得解得推论推论K5,K3,3不是平面图。不是平面图。证明证明q若若K5是平面图，由于是平面图，由于K5中无环和平行边，所以每个面的次数中无环和平行边，所以每个面的次数均大于或等于均大于或等于l3，由由可知边数可知边数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也不是平面图。也不是平面

16、图。设设G是有是有k(k2)个连通分支的平面图，各面的次数至少为个连通分支的平面图，各面的次数至少为l(l3)，则边数则边数m与顶点数与顶点数n应有如下关系：应有如下关系：设设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证明证明设设G为为n(n 3)阶

17、阶m条边的极大平面图，则条边的极大平面图，则m=3n 6。证明证明由于极大平面图是连通图，由欧拉公式得由于极大平面图是连通图，由欧拉公式得:r=2+m-n(17.4)又因为又因为G必要性可知，必要性可知，G的每个面的次数均为的每个面的次数均为3，所以：，所以：将将(17.4)代入代入(17.5)，整理后得，整理后得m=3n-6。二、一个意义重大的定理二、一个意义重大的定理 设设G为简单平面图，则为简单平面图，则G的最小度的最小度(G)5。q若阶数若阶数n 6，结论显然成立。结论显然成立。q若阶数若阶数n 7时，用反证法。时，用反证法。假设假设(G)6，由握手定理可知：由握手定理可知：证明证明因

18、而因而m 3n，这与定理这与定理17.12矛盾。矛盾。所以，假设不成立，即所以，假设不成立，即G的最小度的最小度(G)5。q本定理在图着色理论中占重要地位。本定理在图着色理论中占重要地位。说明说明设设G为为n(n 3)阶简单连通的平面图，阶简单连通的平面图，G为极大平面图当且仅为极大平面图当且仅当当G的每个面的次数均为的每个面的次数均为3。（仅证。（仅证充分性充分性）由定理由定理17.4可知，可知，证证明明又因为又因为G是连通的，由欧拉公式可知是连通的，由欧拉公式可知将将(17.7)代入代入(17.6)，经过整理得，经过整理得m=3n-6。(17.8)若若G不是极大平面图，则不是极大平面图，则

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

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

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

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

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

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

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

26、应的边e*为环。为环。q在多数情况下，在多数情况下，G*为多重图（含平行边的图）。为多重图（含平行边的图）。q同构的平面图（平面嵌入）的对偶图不一定是同构的。同构的平面图（平面嵌入）的对偶图不一定是同构的。二、平面图与对偶图的阶数、边数与面数之间的关系。二、平面图与对偶图的阶数、边数与面数之间的关系。设设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)q(1

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

28、设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)三、自对偶图三、自对偶图设设G*是平面图是平面图G的对偶图，若的对偶图，若G*G，则称则称G为自对偶图。为自对偶图。q在在n 1(n 4)边边形形Cn 1内内放放置置1个个顶顶点点，使使这这个个顶顶点点与与Cn 1上上的的所所有有的的顶顶点点均均相相邻邻，所所得得n阶阶简

29、简单单图图称称为为n阶阶轮轮图图。记记为为Wn。qn为奇数的轮图称为为奇数的轮图称为奇阶轮图奇阶轮图。qn为偶数的轮图称为为偶数的轮图称为偶阶轮图偶阶轮图。q轮图都是自对偶图。轮图都是自对偶图。小节结束小节结束图着色图着色17.5 17.5 图中顶点的着色图中顶点的着色规定：规定：点着色都是对无环无向图进行的。点着色都是对无环无向图进行的。一、关于顶点着色的基本概念一、关于顶点着色的基本概念（1）图图G的的一一种种着着色色对对无无环环图图G的的每每个个顶顶点点涂涂上上一一种种颜颜色，使相邻顶点涂不同的颜色。色，使相邻顶点涂不同的颜色。（2）对对G进进行行k着着色色（G是是k-可可着着色色的的）

30、能能用用k种种颜颜色色给给G 的顶点着色。的顶点着色。（3）G的色数的色数(G)=kG是是k-可着色的，但不是可着色的，但不是(k 1)-可可着着色的。色的。二、关于顶点着色的几个简单结果二、关于顶点着色的几个简单结果(G)=1当且仅当当且仅当G为零图。为零图。(Kn)=n。奇圈或奇阶轮图的色数均为奇圈或奇阶轮图的色数均为3，偶阶轮图的色数为偶阶轮图的色数为4。设设G中至少含有一条边，则中至少含有一条边，则(G)=2当且仅当当且仅当G为二部图。为二部图。三、色数的上界三、色数的上界对于任意无向图对于任意无向图G，均有均有(G)(G)+1。qn=1时，结论成立。时，结论成立。q设设n=k(k1)

31、时结论成立，则当时结论成立，则当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的阶数的阶数n作归纳法。作归纳法。求下面各图的色数。求下面各图的色数。定理定理17.24

32、 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种颜色不可能给种颜色不可能给G4着色，于是只能着色，于是只能是是(G)=4。解答解答小节结束小节结束17.6 17.6 地图的着色与平面图的点着色地图的着色

33、与平面图的点着色一、地图与面着色一、地图与面着色1、地图与国家、地图与国家（1）地图）地图连通无桥平面图的平面嵌入与所有的面。连通无桥平面图的平面嵌入与所有的面。（2）国家）国家地图的面。地图的面。（3）两个国家相邻）两个国家相邻两个国家的边界至少有一条公共边。两个国家的边界至少有一条公共边。有有5个国家，个国家，1与与2相邻，相邻，1与与4相邻，相邻，2,3,4均与均与5相邻。相邻。541232、地图的面着色、地图的面着色（1）地地图图G的的一一种种面面着着色色对对地地图图G的的每每个个国国家家涂涂上上一一种种颜色，使相邻国家涂不同的颜色。颜色，使相邻国家涂不同的颜色。（2）G是是k-面面可

34、可着着色色的的能能用用k种种颜颜色色给给G的的面面着着色色，就就称称对对G的面进行了的面进行了k着色。着色。（3）G的的面面色色数数*(G)=kG是是k-面面可可着着色色的的，但但不不是是(k-1)-面可着色的，即最少用面可着色的，即最少用k种颜色给种颜色给G的面着色。的面着色。q研究地图的着色可以转化成对它的对偶图的点着色研究地图的着色可以转化成对它的对偶图的点着色 。说明说明二、地图的面着色转化成对偶图的点着色二、地图的面着色转化成对偶图的点着色地图地图G是是k-面可着色的当且仅当它的对偶图面可着色的当且仅当它的对偶图G*是是k-点可着色的。点可着色的。三、五色定理三、五色定理任何平面图都

35、是任何平面图都是5-可着色的可着色的。四四色色猜猜想想问问题题，提提出出来来已已经经近近150年年了了，但但时时至至今今日日还还没没有有得到彻底解决。得到彻底解决。q证明证明:(:(归纳法归纳法)(1)(1)n n 5:5:结论为真结论为真.(2)(2)设设n=k(n=k(5)5)时结论为真时结论为真.n=k+1n=k+1时时,v v V(G),V(G),d(v)d(v)5 5.令令G G1 1=G-v,=G-v,对对G G1 1用归纳假设用归纳假设,G G1 1可可5-5-着色着色.模仿模仿G G1 1对对G G着色着色,当当d(v)5d(v)5,与与v v相邻的点用了少于相邻的点用了少于5

36、 5种颜色时种颜色时,至少剩至少剩1 1种颜色给种颜色给v v着色着色.q当当d(v)=5d(v)=5且与且与v v相邻的点用了相邻的点用了5 5种颜色时种颜色时,设设v vi i与与v v相相邻且着颜色邻且着颜色C Ci i,i=1,2,5.,i=1,2,5.设设W W1 1为为G-vG-v中着色中着色为为C C1 1，C C3 3的节点组成的集，的节点组成的集，W W2 2为为G-vG-v中着色为中着色为C C2 2，C C4 4的节点组成的集。的节点组成的集。?q证明证明:(:(续续)（a a）若）若v v1 1，v v3 3分别在分别在W1W1所导出子图的不所导出子图的不同连通分支中，

37、将同连通分支中，将v v1 1所在连通分支中的颜色所在连通分支中的颜色C C1 1，C C3 3对对调，不影响调，不影响G-vG-v的着色，再对的着色，再对v v着色着色C1C1，得图，得图G G的着的着色。色。（b b）若）若v v1 1，v v3 3在在W1W1所导出子图的同一个连通分支中，所导出子图的同一个连通分支中，则从则从v v1 1到到v v3 3存在一条通路存在一条通路L L，L L上的各点都着上的各点都着C C1 1，C C3 3色色的，通路与边的，通路与边vvvv1 1和和vvvv3 3构成回路构成回路C C，它包围了，它包围了v v2 2和和v v4 4，但不能同时包含，于

38、是，但不能同时包含，于是v v2 2和和v v4 4分别属于节点集分别属于节点集W W2 2所所导出子图的两个连通分支中。因此，在包含导出子图的两个连通分支中。因此，在包含v v2 2的连的连通分支中，将颜色通分支中，将颜色C C2 2，C C4 4对调，不影响对调，不影响G-vG-v的着色，的着色，再对再对v v着色着色C C2 2，得图，得图G G的着色。的着色。小节结束小节结束17.7 17.7 边着色边着色本节讨论的图是无环的无向图。本节讨论的图是无环的无向图。一、对图一、对图G进行边着色进行边着色（1）对对图图G边边的的一一种种着着色色对对图图G的的每每条条边边涂涂上上一一种种颜颜色

39、色，使相邻的边涂不同的颜色使相邻的边涂不同的颜色。（2）G是是k-边可着色的边可着色的能用能用k种颜色给种颜色给G的边着色。的边着色。（3）G的的边边色色数数(G)=k若若G是是k-边边可可着着色色的的，但但不不是是 (k-1)-边可着色的，即边可着色的，即最少用最少用k种颜色给种颜色给G的边着色。的边着色。二、关于边着色的一些定理二、关于边着色的一些定理G为简单平面图，则为简单平面图，则(G)(G)(G)+1。q该定理是维津定理。该定理是维津定理。q定理说明，对简单图来说，它的边色数定理说明，对简单图来说，它的边色数只能取它的只能取它的(G)，或者是它的或者是它的(G)+1。q究竟哪些图的究

40、竟哪些图的(G)是是(G)，哪些是哪些是(G)+1，至今还是至今还是一个没有解决的问题。一个没有解决的问题。设设G为长度大于或等于为长度大于或等于2的偶圈，则的偶圈，则(G)=(G)=2.设设G为长度大于或等于为长度大于或等于3的奇圈，则的奇圈，则(G)=(G)+1=3.qn=4时时，由维津定理可知，结论正确。由维津定理可知，结论正确。qn=5时，由维津定理可知，结论正确。时，由维津定理可知，结论正确。qn6时时，(Wn)=n-15，Wn中中间间顶顶点点关关联联的的n-1条条边边必必须须用用n-1种颜色着色。种颜色着色。而而外外圈圈Cn-1上上的的任任何何边边都都准准确确的的与与其其余余的的4

41、条条边边相相邻邻，于于是是总总可以找到可以找到n-1种色中的一种为它涂色，所以种色中的一种为它涂色，所以(Wn)n-1。又由维津定理可知，又由维津定理可知，(Wn)n-1，所以所以(Wn)=n-1。(Wn)=(Wn)=n 1，其中其中n 4。二部图的边色数等于最大度。二部图的边色数等于最大度。证证明明当当n(n 1)为奇数时，为奇数时，(Kn)=n；当当n为偶数时，为偶数时，(Kn)=n 1。证明证明(W4)=(W4)=3，(W5)=(W5)=4。由维津定理可知结论是正确的。由维津定理可知结论是正确的。解答解答求下面所示各图的边色数。求下面所示各图的边色数。小节结束小节结束q=4。q由维津定理

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

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

44、掌握由欧拉公式及其推广形式所证明的平面的性质。掌握由欧拉公式及其推广形式所证明的平面的性质。q会用库拉图斯基定理证明某些图不是平面图。会用库拉图斯基定理证明某些图不是平面图。q掌握平面图与其对偶图某些关系的定理。掌握平面图与其对偶图某些关系的定理。q深刻理解点着色、边着色、点色数、边色数的概念。深刻理解点着色、边着色、点色数、边色数的概念。q理理解解并并记记住住地地图图面面着着色色与与它它的的对对偶偶图图点点着着色色的的关关系系的的定定理。理。q会应用点色数及边色数解决一些简单的实际问题。会应用点色数及边色数解决一些简单的实际问题。小节结束小节结束解 证 证 解 图20 图19 解 小节结束小节结束作业作业习题十七习题十七：1 1、3 3、1515、2424、2626、2929结束结束