平面图和图的着色精.ppt

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

1、平面图和图的着色1第1页，本讲稿共55页 9.1 平面图及欧拉公式平面图及欧拉公式 u uv v u uv v 定义定义9.1.1 图图G称为称为被嵌入平面被嵌入平面S内内，如果，如果G的图解的图解已画在平面已画在平面S上，而且任何两条边均不相交上，而且任何两条边均不相交(除顶点外除顶点外)。已嵌入平面的图称为已嵌入平面的图称为平面图平面图。如果一个图可以嵌入平面，则称此如果一个图可以嵌入平面，则称此图是可平面的图是可平面的。2第2页，本讲稿共55页几点说明及一些简单结论几点说明及一些简单结论 一般所谈平面图不一定是指平面嵌入。但讨论一般所谈平面图不一定是指平面嵌入。但讨论某些性质时，是指平面

2、嵌入某些性质时，是指平面嵌入.结论：结论：(1)K5,K3,3都不是平面图都不是平面图(待证待证).(2)设设GG，若，若G为平面图，则为平面图，则G 也是平面图也是平面图.由此可知，由此可知，Kn(n4)，K2,n(n 1)都是平面图都是平面图.(3)设设GG，若，若G 为非平面图，则为非平面图，则G也是非平面图也是非平面图.由此可知，由此可知，Kn(n 5)，Km,n(m,n 3)都是非平面图都是非平面图.(4)平行边与环不影响平面性平行边与环不影响平面性.3第3页，本讲稿共55页 u uv vf f1 1f f2 2f f3 3f f4 4 定义定义9.1.2 平面图把平面分成了若干个区

3、域，这平面图把平面分成了若干个区域，这些区域都是单连通的，称之为些区域都是单连通的，称之为G的面的面，其中无界的那，其中无界的那个连通区域称为个连通区域称为G的外部面的外部面，其余的单连通区域称为，其余的单连通区域称为G的内部面的内部面。平面图的内部面与外部面平面图的内部面与外部面4第4页，本讲稿共55页 平面图的每个内部面都是平面图的每个内部面都是G的某个圈围成的单连的某个圈围成的单连通区域。通区域。没有圈的图没有内部面，只有一个外部面。没有圈的图没有内部面，只有一个外部面。u uv vf f1 1f f2 2f f3 3f f4 4 图图1 15第5页，本讲稿共55页(2)面面 Ri 的边

4、界的边界包围包围Ri的闭通道组的闭通道组(3)面面 Ri 的次数的次数Ri边界的长度边界的长度 几点补充几点补充(1)若平面图若平面图G有有k个面，可用个面，可用R1,R2,Rk表示表示.(4)闭通道组是指：边界可能是闭通道组是指：边界可能是 圈，也可能是闭通圈，也可能是闭通道道.特别地，还可能是非连通的闭通道之并特别地，还可能是非连通的闭通道之并.定理定理 平面图各面次数之和等于边数的两倍平面图各面次数之和等于边数的两倍.6第6页，本讲稿共55页 如果用如果用V表示多面体的顶点，用表示多面体的顶点，用E表示棱，用表示棱，用F表示表示面数，则面数，则V-E+F=2。定理定理9.1.1(欧拉公式

5、欧拉公式)如果一个平面连通图有如果一个平面连通图有p个个顶点、顶点、q条边、条边、f个面，则个面，则p-q+f=2。证证 对面数用归纳法对面数用归纳法当当f=1时，时，G没有内部面，所以没有内部面，所以G中无圈，中无圈，G是树。是树。p-q+f=1+1=2 假如对一切不超过假如对一切不超过f-1个面的平面连通图欧拉公式个面的平面连通图欧拉公式成立，现证成立，现证f个面时的情况。个面时的情况。7第7页，本讲稿共55页f2，G至少有一个内部面，从而至少有一个内部面，从而G中有一个圈。中有一个圈。这个内部面是由这个圈围成的，从这个圈上去掉一这个内部面是由这个圈围成的，从这个圈上去掉一条边条边x，则打

6、通了两个面。，则打通了两个面。G-x有有p个顶点，个顶点，q-1条边，条边，f-1个面。个面。由归纳假设由归纳假设p-(q-1)+(f-1)=2p-q+f=2因此面数是因此面数是f时也成立。时也成立。u uv vf f1 1f f2 2f f3 3f f4 4 u uv vf f1 1f f2 2f f3 3f f4 48第8页，本讲稿共55页 定理定理9.1.2（欧拉公式的推广）设（欧拉公式的推广）设G是具有是具有k(k 2)个连通分支的平面图，则个连通分支的平面图，则n m+r=k+1.9第9页，本讲稿共55页 推论推论9.1.1 若平面连通图若平面连通图G有有p个顶点个顶点q条边且每个条

7、边且每个面都是由长为面都是由长为n的圈围成的，则的圈围成的，则q=n(p-2)/(n-2)。证证 因为因为G的每个面都是长为的每个面都是长为n的圈围成的，所的圈围成的，所以以G的每条边都在的每条边都在G的两个面上。的两个面上。q=f n/2f=2q/np-q+2q/n=2q=n(p-2)/(n-2)10第10页，本讲稿共55页最大最大(极大极大)可平面图可平面图 一个图称为一个图称为最大可平面图最大可平面图，如果这个可平面图再加，如果这个可平面图再加入一条边，新图必然是不可平面的。入一条边，新图必然是不可平面的。图图1再加一条边就是再加一条边就是k5，可证，可证k5是不可平面图。是不可平面图。

8、图图1是最大可平面图。是最大可平面图。11第11页，本讲稿共55页 最大最大(极大极大)平面图的性质平面图的性质 u uv v最大最大(极大极大)平面图的主要性质：平面图的主要性质：定理定理 最大最大(极大极大)平面图是连通的平面图是连通的.定理定理 n(n 3)阶阶最大最大(极大极大)平面图中不可能有割点和桥平面图中不可能有割点和桥.12第12页，本讲稿共55页 推论推论9.1.2 设设G是一个有是一个有p个顶点个顶点q条边的最大可平条边的最大可平面图，则面图，则G的每个面都是三角形，的每个面都是三角形，q=3p-6，p3。证证 若若G的一个面不是三角形的一个面不是三角形,.v v1 1v

9、v2 2v v3 3v v4 4 1、假如有两点不相邻，则在此面中把不相邻的两、假如有两点不相邻，则在此面中把不相邻的两顶点连接起来，不影响平面性。顶点连接起来，不影响平面性。矛盾，因此不可能有两点不相邻。矛盾，因此不可能有两点不相邻。13第13页，本讲稿共55页2、假如圈上每两点都相邻、假如圈上每两点都相邻;.v v1 1v v2 2v v3 3v v4 4 若若v1,v2和和v2,v4在在G中都邻接中都邻接,我们可以看到这两个我们可以看到这两个边不可能不相交边不可能不相交;综合以上情况，最大平面图的每个面都是三角形。综合以上情况，最大平面图的每个面都是三角形。14第14页，本讲稿共55页

10、推论推论9.1.3 设设G是一个是一个(p,q)可平面连通图，而且可平面连通图，而且G的每个面都是一个长为的每个面都是一个长为4的圈围成的，则的圈围成的，则q=2p-4。推论推论9.1.4 若若G是任一有是任一有p个顶点个顶点q条边的可平面图条边的可平面图p3，则，则q3p-6。若若G是是2-连通的且没有三角形，则连通的且没有三角形，则q2p-4。1、因为当平面图中每个面都是三角形时其边数最、因为当平面图中每个面都是三角形时其边数最多，由推论多，由推论9.1.2，则，则q3p-6。2、若、若G是是2-连通的且没有三角形连通的且没有三角形,则则G中任意两个中任意两个顶点都在同一个圈上。顶点都在同

11、一个圈上。已知没有三角形，所以圈的长都是已知没有三角形，所以圈的长都是4时边数最多。时边数最多。所以所以q2p-4。15第15页，本讲稿共55页推论推论9.1.5 K5与与K3,3都不是可平面图都不是可平面图 证证 如果如果K5是平是平面图，则面图，则5-10+f=2，即即f=7。每个面至少三条边，每个面至少三条边，7个面至少需要个面至少需要21条边。条边。考虑到每条边在两个面上，考虑到每条边在两个面上，2q3f，即，即 2021。矛盾。矛盾。其实直接利用推论其实直接利用推论9.1.4，任意，任意(p,q)平面图都满足平面图都满足q3p-6，这里，这里p3。q=103p-6=9，这是不成立的。

12、，这是不成立的。所以所以K5不是可平面图。不是可平面图。16第16页，本讲稿共55页 如果如果K3,3是平面图，则是平面图，则p-q+f=2，即即6-9+f=2，亦即，亦即f=5。在偶图在偶图K3,3中每个圈的长至少为中每个圈的长至少为4，所以，所以2q4f=20，q10，但，但q=9，矛盾。矛盾。所以所以K3,3不是平面图。不是平面图。17第17页，本讲稿共55页 推论推论9.1.6 每个平面图每个平面图G中顶点度的最小值不超中顶点度的最小值不超过过5，即即(G)5。如果如果G的每个顶点的度大于的每个顶点的度大于5，也就是，也就是6，由欧拉定理，由欧拉定理，2q6p，即，即q3p。仍然用推论

13、仍然用推论9.1.4，q3p-6。那么所有顶点的度数和大于或等于那么所有顶点的度数和大于或等于6p。不满足推论不满足推论9.1.4，q3p-6。因此，每个平面图因此，每个平面图G中顶点度的最小值不超过中顶点度的最小值不超过5，即，即(G)5。18第18页，本讲稿共55页例例9.1.1 顶点数顶点数p4的最大平面图，的最大平面图，(G)3。证证 设设G是最大平面图，其最小度顶点为是最大平面图，其最小度顶点为v。设设G-v也是一个平面图，也是一个平面图，v在在G-v的一个面内。的一个面内。在这个面内，边界上至少有三个顶点。在这个面内，边界上至少有三个顶点。由极大性，由极大性，v必然与这些顶点都相连

14、。必然与这些顶点都相连。因此，因此，(G)3。v v19第19页，本讲稿共55页 定理定理9.2.1 设设G=(V,E)是一个是一个(p,q)平面哈密顿图平面哈密顿图,C是是G的哈密顿圈，令的哈密顿圈，令fi为为C的内部由的内部由i条边围成的面条边围成的面的个数，的个数，gi为为C的外部的外部i条边围成的面的个数，则条边围成的面的个数，则9.2 非哈密顿平面图非哈密顿平面图(1)1 f3+2 f4+3 f5+.+(p-2)fp=(2)1 g3+2 g4+3 g5+.+(p-2)gp=(3)1(f3-g3)+2(f4-g4)+3(f5-g5)+.=v v1 1v v2 2v v3 3v v4 4

15、v v5 5v v6 6v v7 7v v8 8有哈密顿圈有哈密顿圈v1v2v3v4v8v7v6v5v1圈内有圈内有3条边围成的面条边围成的面2个个圈内有圈内有4条边围成的面条边围成的面2个个圈外有圈外有8条边围成的面条边围成的面1个个20第20页，本讲稿共55页 证证 因为因为C是是G的哈密顿圈，所以的哈密顿圈，所以G的所有顶点都的所有顶点都在圈在圈C上。因此上。因此C的内部与外部不再含有的内部与外部不再含有G的顶点。的顶点。C的内部的每个面都是由的内部的每个面都是由C上的某边及上的某边及C上两顶点上两顶点间的间的“连线连线”围成的区域。围成的区域。v v1 1v v2 2v v3 3v v

16、4 4v v5 5v v6 6v v7 7v v8 8 设设q 是是C的内部的内部(不含不含C)边的条边的条数，这些边之集记为数，这些边之集记为E。先把先把C内部的边都去掉，这时内部的边都去掉，这时C里只有一个面。里只有一个面。把把E 的一条边加入的一条边加入C中。就把中。就把C分成两个面。分成两个面。再加入再加入E 的另一条边就把这两个面之一分为两个的另一条边就把这两个面之一分为两个面，如此进行，直到把面，如此进行，直到把E 的边都加入为止。的边都加入为止。这样，这样，C的内部就有的内部就有q+1个面。个面。21第21页，本讲稿共55页f1+f2+f3+.=其次，由其次，由j条边围成面共条边

17、围成面共fj个，这个，这些面上的边的总数为些面上的边的总数为j fj，所以，所以，C内内部的部的q+1个面上的边数共有个面上的边数共有 。其中其中C上的每条边在每个内部面上至多出现一次且不上的每条边在每个内部面上至多出现一次且不是两个内部面的公共边，所以在上述计数中是两个内部面的公共边，所以在上述计数中C上每条上每条边各计数一次。边各计数一次。但但E 中的每条边是两个面之公共边，所以每条边中的每条边是两个面之公共边，所以每条边计数两次，因此计数两次，因此 。v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 822第22页，本讲稿共55页 从从(2)式

18、两边分别减去式两边分别减去(1)式两边的两倍便得到式两边的两倍便得到f1+f2+f3+.=(1)(2)用同样的方法可得用同样的方法可得:(3)(4)(3)式两边分别减去式两边分别减去(4)式的两边得式的两边得23第23页，本讲稿共55页 例例9.2.2 下图是一个哈密顿图，证明：任一哈密顿下图是一个哈密顿图，证明：任一哈密顿圈上如果包含边圈上如果包含边x，那么这个哈密顿圈上就一定不包含，那么这个哈密顿圈上就一定不包含边边y。x xy y 证证 右图右图G是哈密顿平面图，是哈密顿平面图，它的面或由它的面或由4条边围成，或由条边围成，或由5条条边围成，由定理边围成，由定理9.2.1有有:2(f4-

19、g4)+3(f5-g5)=0所以所以f4-g4能被能被3整除，即五个由整除，即五个由4条边围成的面中有条边围成的面中有四个面在四个面在G的哈密顿圈的哈密顿圈C外，一个在外，一个在C内；或相反内；或相反即一个在即一个在C外，四个在外，四个在C的内部。的内部。1 12 23 34 45 56 67 724第24页，本讲稿共55页 同样，以同样，以y为公共边的两侧的四条边围成的两个面为公共边的两侧的四条边围成的两个面中，必一个在中，必一个在C的内部，另一个在的内部，另一个在C的外部。的外部。这就得到矛盾，故这就得到矛盾，故C不能同时含边不能同时含边x与与y。x xy y 因此，因此，C的内部与的内部

20、与C的的外部均至少有两个四条边外部均至少有两个四条边围成的面。围成的面。假如假如C既含边既含边x又含边又含边y，则以，则以x为公共边的两侧的为公共边的两侧的四条边围成的两面中必有一个在四条边围成的两面中必有一个在C的内部，另一个在的内部，另一个在C的外部。的外部。25第25页，本讲稿共55页K5和和K3,3不是平面图。不是平面图。9.3 库拉托斯基定理、对偶图库拉托斯基定理、对偶图 平面图的每个子图都是平面图，因此，平面图中不平面图的每个子图都是平面图，因此，平面图中不含子图含子图K5和和K3,3。定义定义9.3.1 设设x=uv是图是图G=(V,E)的一条边，的一条边，w不是不是G的顶点，则

21、当用边的顶点，则当用边uw和和wv代替边代替边x时，就称时，就称x被被细分细分。如果如果G的某些边被细分，产生的图称为的某些边被细分，产生的图称为G的的细分图细分图。u uv v图图Gx x u uv vw wG的细分的细分图图26第26页，本讲稿共55页 定义定义9.3.2 两个图称为两个图称为同胚同胚的，如果它们都可以的，如果它们都可以从同一个图通过一系列的边细分得到。从同一个图通过一系列的边细分得到。下面几个图是同胚的。下面几个图是同胚的。u uv v图图Gx x u uv vw wG的细分图的细分图 图与图之间同胚图与图之间同胚27第27页，本讲稿共55页 定义定义9.3.1 所定义的

22、的细分也称为所定义的的细分也称为插入插入2度顶点度顶点。与之相对应的还有一种方法：与之相对应的还有一种方法：消去消去2度顶点度顶点。补充补充(1)消去消去2度顶点度顶点v，见下图中，由，见下图中，由(1)到到(2)；(2)插入插入2度顶点度顶点v，见下图中，从，见下图中，从(2)到到(1).定义定义 若若G1 G2，或经过反复插入或消去，或经过反复插入或消去2度顶点后所得度顶点后所得G 1 G 2，则称，则称G1与与G2同胚同胚.28第28页，本讲稿共55页 定理定理9.3.1（库拉托斯基（库拉托斯基,1930）一个图是可平面）一个图是可平面的充分必要条件是它没有同胚于的充分必要条件是它没有同

23、胚于K5和和K3,3的子图。的子图。例例9.3.1 证明左下图不是可平面图。证明左下图不是可平面图。因为它含有与因为它含有与K5同胚的子图。同胚的子图。u uv v库拉托斯基定理库拉托斯基定理29第29页，本讲稿共55页例例9.3.2 证明所示证明所示图图(1)与与(2)均为非均为非平面图平面图.(1)(2)右图右图(1),(2)分别为分别为原图原图(1),(2)的子图的子图与与K3,3,K5同胚同胚.子图子图 (1)子图子图(2)30第30页，本讲稿共55页 定义定义9.3.3 一个图一个图G的一个的一个初等收缩初等收缩由合并两个邻由合并两个邻接的顶点接的顶点u和和v得到，即从得到，即从G中

24、去掉中去掉u和和v，然后再加上，然后再加上一个新顶点一个新顶点w，使得，使得w相邻所有与相邻所有与u或或v相相邻的顶点。邻的顶点。u uv v w w 一个图一个图G可收缩到图可收缩到图H，如果，如果H可以从可以从G经一系列经一系列的初等收缩得到。的初等收缩得到。图图G的初等收缩的初等收缩31第31页，本讲稿共55页 定理定理9.3.2 一个图是可平面的当且仅当它没有一个一个图是可平面的当且仅当它没有一个可以收缩到可以收缩到K5或或K3,3的子图。的子图。例例9.3.1 证明左下图不是可平面图。证明左下图不是可平面图。因为它可以收缩因为它可以收缩到到K5 。32第32页，本讲稿共55页 定义定

25、义9.3.4 设设G=(V,E)是一个平面图，由是一个平面图，由G按如下方按如下方法构造一个图法构造一个图G*，G*称为称为G的的对偶图对偶图。3、如果某条边、如果某条边x仅在一仅在一个面中出现而不是两个面的个面中出现而不是两个面的公共边公共边(是不是桥？是不是桥？)，则在，则在G*中这个面对应的顶点有一中这个面对应的顶点有一个环。个环。1、对、对G的每个面的每个面f对应地有对应地有G*的一个顶点的一个顶点f*；2、对、对G的每条边的每条边e对应地有对应地有G*的一条边的一条边e*：G*的两的两个顶点个顶点f*与与g*由边由边e*联结，当且仅当联结，当且仅当G中与顶点中与顶点f*与与g*对对应

26、的面应的面f与与g有公共边有公共边e。平面图的对偶图平面图的对偶图33第33页，本讲稿共55页 下面两图中，实线边图为平面图，虚线边图为下面两图中，实线边图为平面图，虚线边图为其对偶图其对偶图.实例实例34第34页，本讲稿共55页对偶图的性质对偶图的性质G 的对偶图的对偶图G*有以下性质：有以下性质：(1)G*是平面图，而且是平面嵌入是平面图，而且是平面嵌入.(2)G*是连通图是连通图.(3)若边若边e为为G中的环，则中的环，则G*与与e对应的边对应的边e*为桥，为桥，若若e为桥，则为桥，则G*中与中与e对应的边对应的边e*为环为环.(4)在多数情况下，在多数情况下，G*为多重图为多重图(含平

27、行边的图含平行边的图).(5)同构的平面图同构的平面图(平面嵌入平面嵌入)的对偶图不一定是同构的对偶图不一定是同构 的的.35第35页，本讲稿共55页(6)设设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中，则中，则 degG*(v*i)=面面 Ri的次数的次数.对偶图的性质对偶图的性质只证明只证明(3)r*=n。由图由图G与与G*都是连通平面图，所以都是连通平面图，所以n*-m*+r*=2 得

28、得 r*=m*-n*+2=m-r+2n-m+r=2 可得可得 n=m-r+2因此因此r*=n。36第36页，本讲稿共55页9.4 图的顶点着色图的顶点着色 定义定义9.4.1 图的一种图的一种(顶点顶点)着色着色是指对图的每个顶点是指对图的每个顶点指定一种颜色，使得没有两个相邻的顶点有同一颜色。指定一种颜色，使得没有两个相邻的顶点有同一颜色。若图若图G=(V,E)的顶点已着色，则着同一颜色的那些的顶点已着色，则着同一颜色的那些顶点之集称为顶点之集称为G的一个的一个色组色组。同一色组内的各顶点不相邻，这样的顶点集合称为同一色组内的各顶点不相邻，这样的顶点集合称为G的一个的一个顶点独立集顶点独立集

29、。如果如果G有一个有一个n着色，则着色，则G的顶点集的顶点集V被这种被这种n着色着色划分为划分为n个色组。个色组。图图G的一个的一个n着色着色是用是用n种颜色对种颜色对G的顶点着色。的顶点着色。1 12 21 12 23 32 21 12 21 137第37页，本讲稿共55页 定义定义9.4.2 图图G的的色数色数是使是使G为为n着色的数的最小值，着色的数的最小值，图图G的色数记为的色数记为(G)。若若(G)n，则称，则称G是是n可着色的可着色的。若若(G)=n，则称，则称G是是n色的色的。(Kp)=p(Kpc)=1(Km,n)=2,图图G的色数的概念的色数的概念38第38页，本讲稿共55页

30、定理定理9.4.1 一个图是可双色的当且仅当它没有奇数一个图是可双色的当且仅当它没有奇数长的圈。长的圈。一个图是可双色的当且仅当是偶图。一个图是可双色的当且仅当是偶图。偶图的充分必要条件是它的圈的长度都是偶数。偶图的充分必要条件是它的圈的长度都是偶数。若若G是偶数个顶点的圈是偶数个顶点的圈C2n，则，则(C2n)=2。若若G是奇数个顶点的圈是奇数个顶点的圈C2n+1，则，则(C2n+1)=3。1 12 21 12 23 32 21 12 21 1 1 12 21 12 22 21 12 21 139第39页，本讲稿共55页 定理定理9.4.2 设设=(G)为为图图G的顶点度的最大值，的顶点度的

31、最大值，则则G是是(+1)可着色的。可着色的。证证 对顶点数对顶点数p用归纳法。用归纳法。当当p=1时，结论成立。时，结论成立。假设对顶点数为假设对顶点数为p-1的图定理成立，今设的图定理成立，今设G是一个是一个有有p个顶点的图。个顶点的图。从从G中去掉一个顶点中去掉一个顶点v，则，则G-v有有p-1个顶点，个顶点，(G-v)(G)由归纳假设由归纳假设G-v是是(+1)可着色的可着色的。但在但在G中与中与v相邻的顶点最多有相邻的顶点最多有 个，与个，与v相邻的顶相邻的顶点最多用去点最多用去 种颜色，剩下一种给顶点种颜色，剩下一种给顶点v着色即可。着色即可。40第40页，本讲稿共55页 定理定理

32、9.4.3 如果如果G是一个连通图且不是完全图也不是一个连通图且不是完全图也不是奇数长的圈，则是奇数长的圈，则G是是(G)可着色的可着色的。41第41页，本讲稿共55页定理定理9.4.4 每个平面图都是每个平面图都是6可着色的。可着色的。如果顶点数小于如果顶点数小于7，显然是，显然是6可着色的。可着色的。证证 对平面图的顶点数对平面图的顶点数p用归纳法。用归纳法。设设G是一个有是一个有p个顶点的平面图，由推论个顶点的平面图，由推论9.1.6知知G有顶点有顶点v，degv5，G-v是一个是一个p-1个顶点的平面图。个顶点的平面图。假设对假设对p-1个顶点的平面图是个顶点的平面图是6可着色的，只需

33、证可着色的，只需证对有对有p个顶点的平面图也是个顶点的平面图也是6可着色的即可。可着色的即可。由归纳假设，由归纳假设，G-v是是6可着色的可着色的,与与v相邻的顶点至相邻的顶点至多多5个，所以与个，所以与v相邻的顶点着色时至多用了相邻的顶点着色时至多用了5种色。种色。用另一种未用的颜色对用另一种未用的颜色对v着色即得着色即得G的一个的一个6着色。着色。因此因此,G是是6可着色的。可着色的。42第42页，本讲稿共55页定理定理9.4.5 每个可平面图是每个可平面图是5可着色的可着色的证证 对可平面图的顶点数进行归纳证明。对可平面图的顶点数进行归纳证明。当当p5时。定理显然成立。时。定理显然成立。

34、假设所有假设所有p个顶点的可平面图都是个顶点的可平面图都是5可着色的，可着色的，需证所有需证所有p+1个顶点的可平面图也是个顶点的可平面图也是5可着色的。可着色的。设设G是一个有是一个有p+1个顶点可平面图，由推论个顶点可平面图，由推论9.1.6知知G中有一个顶点中有一个顶点v使使degv5。于是，。于是，G-v是一个有是一个有p个个顶点的可平面图，由归纳假设，顶点的可平面图，由归纳假设，G-v是是5可着色的。可着色的。1、如果、如果degv4,则必有一种颜色，在则必有一种颜色，在G-v的一种的一种5-着色时，对与着色时，对与v相邻的顶点着色中未用此色，于是，用相邻的顶点着色中未用此色，于是，

35、用此色对顶点此色对顶点v着色便得到着色便得到G的的5-着色。着色。43第43页，本讲稿共55页 2、degv=5且对且对G-v的的5-着色中，与着色中，与v相邻的相邻的5个顶个顶点点v1,v2,v3,v4,v5分别着分别着5种颜色种颜色c1,c2,c3,c4,c5。v v1 1v vv v2 2v v3 3v v4 4v v5 5 令令G13为为G-v的一个子图，其顶点的一个子图，其顶点为着为着c1色或色或c3色的顶点之集色的顶点之集V13,G13就就是是V13导出的子图。导出的子图。(1)若若v1和和v3在在G13的不同的不同支中，则在含支中，则在含v1的支中的支中交换两种色，即原着交换两种

36、色，即原着c1色顶点改着色顶点改着c3色，原着色，原着c3色的顶点改着色的顶点改着c1色。色。c3c3c1c1c3c3c1c1 c3c3c1c1c3c3c1c1 c1c1c3c3c1c1c3c3 c c3 3然后用然后用c1给顶点给顶点v着色，着色，于是得到于是得到G的一种的一种5着色。着色。44第44页，本讲稿共55页 (2)若若v1和和v3在在G13的同一个支中，则在的同一个支中，则在G13中有一条中有一条从从v1到到v3的路，于是，在的路，于是，在G中中v1vv3与这条路合起来形成与这条路合起来形成一个圈。一个圈。v v1 1v vv v2 2v v3 3v v4 4v v5 5 3 3

37、1 13 31 1 这个圈或把这个圈或把v2圈在圈在圈内或把圈内或把v4和和v5圈在内。圈在内。若令若令G24表示表示G-v的由着的由着c2或或c4色的顶点导出的子图，则色的顶点导出的子图，则v2与与v4属于属于G24的不同支里。的不同支里。4 4 2 2 4 4 2 2 4 4 2 2 交换交换G24的含的含v2支中着支中着c2色顶点与着色顶点与着c4色顶点的颜色顶点的颜色，然后，用色，然后，用c2色为色为v着色得到着色得到G的一个的一个5着色。着色。任何情况下，不存在任何情况下，不存在联结联结v2和和v4的路且路上各的路且路上各顶点或着顶点或着c2或着或着c4色。色。45第45页，本讲稿共

38、55页4色猜想色猜想 每个可平面图是每个可平面图是4可着色的。可着色的。定理定理9.4.6 每个可平面图是每个可平面图是4可着色的。可着色的。1852年，刚从伦敦大学毕业的哥斯尼从事地图染年，刚从伦敦大学毕业的哥斯尼从事地图染色工作，他发现在一幅正规地图中，最多只用四种颜色工作，他发现在一幅正规地图中，最多只用四种颜色着色，就能把这些国家区别开来。色着色，就能把这些国家区别开来。如果国家用图的顶点来表示，两个顶点相邻当且如果国家用图的顶点来表示，两个顶点相邻当且仅当两个国家相邻，就形成一个平面图。仅当两个国家相邻，就形成一个平面图。46第46页，本讲稿共55页9.5 图的边着色图的边着色 定义

39、定义9.5.1 图图G的一个的一个k边着色边着色是对是对G的每条边指的每条边指定定k种色之一，使得任何两条相邻的边被指定色是不种色之一，使得任何两条相邻的边被指定色是不同的。同的。如果图如果图G是是k边着色的，但不边着色的，但不(k-1)边着色的，边着色的，则称则称G的的边色数边色数为为k，G的边色数记为的边色数记为 (G)。1 12 23 31 14 42 23 34 4 如果如果=(G)是是图图G的顶点的最大度数，则显然有的顶点的最大度数，则显然有 (G)。右图存在一个右图存在一个4边着色边着色不存在不存在3边着色边着色 (G)=447第47页，本讲稿共55页 对某些特殊类型的图，我们能容

40、易确定它的边色对某些特殊类型的图，我们能容易确定它的边色数。数。例如：例如：偶数长的圈偶数长的圈C2n的边色数是的边色数是 (C2n)=2。1 12 21 12 23 32 21 12 21 1 1 12 21 12 22 21 12 21 1对奇数长的圈对奇数长的圈C2n+1有有 (C2n+1)=3。48第48页，本讲稿共55页 定理定理9.5.1 如果如果p是不为是不为1的奇数，则的奇数，则 (Kp)=p。如果如果p是偶数，则是偶数，则 (Kp)=p-1。证证 设设p是奇数，把是奇数，把Kp的的p个顶点安放在正个顶点安放在正p边形的顶边形的顶点上，对正点上，对正p边形的边形的p个边分别着个

41、边分别着p个不同色。个不同色。而平行于而平行于p边形的对角线的边着与这条边同一颜边形的对角线的边着与这条边同一颜色，这就得到色，这就得到Kp的一个的一个p边着色。边着色。1、证明当、证明当p是奇数时，是奇数时，Kp是是p边着边着色的。色的。49第49页，本讲稿共55页Kp最多有最多有(p-1)(Kp)/2条边条边;(p-1)/2条平行边已关联了条平行边已关联了(p-1)个顶点，个顶点，所以在所以在Kp的边着色中至多有的边着色中至多有(p-1)/2条同色边。条同色边。Kp最多有最多有(p-1)(Kp)/2p(p-1/2)条边条边;(Kp)p;所以所以 (Kp)=p。所以每组平行边共有所以每组平行

42、边共有(p-1)/2条边。条边。2、其次，证明、其次，证明Kp不是不是(p-1)边着色的。边着色的。Kp中共有中共有p组平行边，组平行边，Kp的总边数为的总边数为p(p-1)/2，50第50页，本讲稿共55页 若若p(4)是偶数，则是偶数，则Kp-1中加一顶点中加一顶点v且且v与与Kp-1的每的每一顶点联结一条边而得到一顶点联结一条边而得到Kp。v v5 54 43 32 21 11 12 23 34 45 51 12 23 34 45 5于是用上述方法对于是用上述方法对Kp-1的边着色需的边着色需p-1种色。种色。与与Kp-1每个顶点关联的边用去每个顶点关联的边用去p-2个色，剩下的那个个色

43、，剩下的那个色留给该点与色留给该点与v的边即可得到的边即可得到Kp的一个的一个(p-1)边着色。边着色。51第51页，本讲稿共55页 定理定理9.5.2 如果如果G是偶图，则是偶图，则 (G)=(G)，即偶图的，即偶图的边色数等于它的顶点的最大度。边色数等于它的顶点的最大度。对对G的边数的边数q用归纳法。用归纳法。2、设当、设当q=k时结论成立。当时结论成立。当q=k+1时时,1、当、当q=1时定理成立。时定理成立。证证 设设w的度为的度为(G),则给则给w所关联的边至少得用所关联的边至少得用(G)种颜色，所以种颜色，所以 (G)(G)。只需证只需证 (G)(G)。设设e=uv E(G)，令，

44、令G1=G-e，则，则G1中有中有k条边，由归条边，由归纳假设纳假设 (G1)(G1)(G)。52第52页，本讲稿共55页 、若不出现在、若不出现在u和不出现在和不出现在v的颜色有如下特点：的颜色有如下特点：、若存在颜色、若存在颜色 既不出现在既不出现在u也不出现在也不出现在v，将，将G1还原成还原成G时，将边时，将边e=(u,v)涂颜色涂颜色 即可。即可。因此因此G1存在着存在着(G)着色着色,G1=G-e。u和和v在在G1中的度都小于中的度都小于(G)，所以在对，所以在对G1进行着进行着色时，至少有一种颜色不出现在色时，至少有一种颜色不出现在u中，同时也有一种中，同时也有一种颜色不出现在颜

45、色不出现在v中。中。这样就完成了这样就完成了G的的(G)着色，因而着色，因而(G)(G)。不出现在不出现在u的颜色在的颜色在v中都出现，反之不出现在中都出现，反之不出现在v中中的颜色在的颜色在u中都出现。中都出现。53第53页，本讲稿共55页 设设 不出现在不出现在u，则，则 一定出现在一定出现在v，不出现在不出现在v，一定出现在一定出现在u。u uv v 令令H是是G的这样的一个连通子图：的这样的一个连通子图：H的顶点和的顶点和边是这样的，即从边是这样的，即从v可经一条着可经一条着 或或 色的边的路可达色的边的路可达到的顶点和边组成的。到的顶点和边组成的。由于由于G是偶图，所以是偶图，所以u不在不在H中，所以，在中，所以，在H中中交换颜色交换颜色 和和。u uv v 从而可用色从而可用色 为为uv着色，因此着色，因此G是是(G)边着色的。边着色的。54第54页，本讲稿共55页55第55页，本讲稿共55页