图论第四章 平面图及着色.ppt

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

1、第四章第四章 平面图平面图第一节 平面图定义1 如果图G能示画在曲面S(如球面，环面)上且使得它的边仅在端点处相交，则称G可嵌入曲面S。如果G可嵌入平面上，则称G是是可平面可平面图图，已经嵌入平面上的图，称为G的平面表示的平面表示。可平面图G与G的平面表示 同构，都简称为平面图平面图。(球极投影)定理定理1 1 图图G G可嵌入球面可嵌入球面图图G G可嵌入平面。可嵌入平面。例例1 Q1 Q3 3是否可平面性？是否可平面性？定义定义2(2(平面图的面平面图的面,边界和度数边界和度数).).设设G G是一个平面图，由是一个平面图，由G G中的边所包围的区域，中的边所包围的区域，在区域内既不包含在

2、区域内既不包含G G的结点，也不包含的结点，也不包含G G的边，的边，这样的区域称为这样的区域称为G G的一个面。有界区域称为有界区域称为内部面，无界区域称为，无界区域称为外部面。包围面的长度最包围面的长度最短的闭链称为短的闭链称为该面的边界。面的边界的长度称。面的边界的长度称为为该面的度数。例例2 2 指出下图所示平面图的面、面的边界及指出下图所示平面图的面、面的边界及面的度数。面的度数。e61234567e1e2e3e4e5e7e8e10e9f1f4f3f2f5解解:面面f f1 1,其边界其边界1e1e1 15e5e2 24e4e4 43e3e7 72e2e10101,d(f1,d(f1

3、 1)=5.)=5.面面f f2 2,其边界其边界1e1e10102e2e8 87e7e9 91,d(f1,d(f2 2)=3.)=3.面面f f3 3,其边界其边界2e2e7 73e3e6 67e7e8 82,d(f2,d(f3 3)=3.)=3.面面f f4 4,其边界其边界3e3e4 44e4e5 57e7e6 63,d(f3,d(f4 4)=3.)=3.外部面外部面f f5 5,其边界其边界1e1e1 15e5e2 24e4e3 36e6e3 34 e4 e5 57e7e9 91,d(f1,d(f5 5)=6.)=6.定理定理2 2 对任何平面图对任何平面图G G，面的度数之和是是边数

4、的二倍。证明证明:对内部面而言对内部面而言,因为其任何一条非因为其任何一条非割割边同时在两个边同时在两个面中面中,故每增加一条边图的度数必增加故每增加一条边图的度数必增加2.2.对外部面的边对外部面的边界界,若某条边不同时在两个面中若某条边不同时在两个面中,边必为割边边必为割边,由于边界由于边界是闭链是闭链,则该边也为图的度数贡献则该边也为图的度数贡献2.2.从而结论成立从而结论成立.定理定理3 3 设设G G是带是带v v个顶点，个顶点，e e条边，条边，r r个面的连通的平面个面的连通的平面图，则图，则 v-e+rv-e+r=2=2。（欧拉公式）。（欧拉公式）证明证明:(1):(1)当当n

5、=e=1n=e=1时时,如下图如下图,结论显然成立结论显然成立.v=2,e=1,r=1v=1,e=1,r=2(2)下用下用数学归纳法证明证明.假设公式对假设公式对n条边的图成立条边的图成立.设设G有有n+1条边条边.若若G不含圈,任取一点任取一点x,从结点从结点x开始沿路行走开始沿路行走.因因G不含圈不含圈,所以每次沿一边总能达到一个新结点所以每次沿一边总能达到一个新结点,最后会最后会达到一个度数为达到一个度数为1的结点的结点,不妨设为不妨设为a,在结点在结点a不能再继不能再继续前进续前进.删除结点删除结点a及其关联的边得图及其关联的边得图G,G含有含有n条边条边.由假设公式对由假设公式对G成

6、立成立,而而G比比G多一个结点和一条边多一个结点和一条边,且且G与与G面数相同面数相同,故公式也适合于故公式也适合于G.若若G含有圈C,设设y是圈是圈C上的一边上的一边,则边则边y一定是两个一定是两个不同面的边界的一部分不同面的边界的一部分.删除边删除边y得图得图G,则则G有有n条边条边.由假设公式对由假设公式对G成立而成立而G比比G多一边和和多一面,G与与G得顶点数相同得顶点数相同.故公式也成立故公式也成立.推论推论1 1 设设G G是带是带v v个顶点，个顶点，e e条边的连通的平面简条边的连通的平面简单图，其中单图，其中v v 3 3，则，则e e 3 3v-6v-6。证明证明:由于由于

7、G G是简单图是简单图,则则G G中无环和无平行边中无环和无平行边.因此因此G G的的任何面的度数至少为任何面的度数至少为3.3.故故2e=2e=d(f)d(f)3r (1)3r (1)其中其中r r为为G G的面数的面数.由欧拉公式由欧拉公式v-e+r=2v-e+r=2所以所以r=2-v+e,r=2-v+e,代入代入(1)(1)中有中有:2e2e 3(3(2-v+e2-v+e)即即e e 3 3v-6v-6。推论推论2 2 设设G G是带是带v v个顶点，个顶点，e e条边的连通的平面简单图，其条边的连通的平面简单图，其中中v v 3 3且且没有长度为没有长度为3 3的圈，则的圈，则e e

8、2 2v-4v-4。证明证明:因为图因为图G G中没有长度为中没有长度为3 3的圈的圈,从而从而G G的的每个面的度数至少为至少为4.4.因此有因此有2e=2e=d(f)d(f)4r (1)4r (1)其中其中r r为为G G的面数的面数.由欧拉公式由欧拉公式v-e+r=2v-e+r=2所以所以r=2-v+e,r=2-v+e,代入代入(1)(1)中有中有:2e2e 4(4(2-v+e2-v+e)即即e e 2 2v-4v-4。例例3 K3 K5 5和和K K3.33.3都是非平面图。都是非平面图。解解:图图K K5 5有有5 5个顶点个顶点1010条边条边,而而3*5-6=9,3*5-6=9,

9、即即109,109,由由推论推论1 1知知,K,K5 5是非平面图是非平面图.显然显然K K3,33,3没有长度为没有长度为3 3的圈的圈,且有且有6 6个顶点个顶点9 9条边条边,因而因而92*6-4,92*6-4,由推论由推论2 2知知K K3,33,3是非平面图是非平面图.推论推论3 3 设设G G是带是带v v个顶点，个顶点，e e条边，条边，r r个面的平面图，个面的平面图，则则 v-e+r=1+wv-e+r=1+w。其中其中w w为为G G的连通分支数。的连通分支数。证明证明:由欧拉公式有由欧拉公式有:v:vi i-e ei i+r ri i=2(i=1,2,w)=2(i=1,2,

10、w)从而有从而有 v vi i-e ei i+r ri i =2w=2w又又 v vi i=v,=v,e ei i=e,=e,r ri i =r+(w-1)(=r+(w-1)(外部面被重外部面被重复计算了复计算了w-1w-1次次.).).所以有所以有:V-e+r+(w-1)=2wV-e+r+(w-1)=2w整理即得整理即得:v-e+r=1+w.:v-e+r=1+w.推论推论4 4 设设G G是任意平面简单图，则是任意平面简单图，则(G)(G)5 5。证明证明:设设G G有有v v个顶点个顶点e e条边条边.若若e e 6,6,结论显然成立结论显然成立;若若e6,e6,假设假设G G的的每个顶点

11、的度数每个顶点的度数 6,6,则由推论则由推论1,1,有有6v 6v 2e 2e 2(3v-6)2(3v-6)矛盾矛盾,所以所以(G)(G)5.5.例例4 4 平面上有平面上有n n个顶点，其中任两个点之间的距离个顶点，其中任两个点之间的距离至少为至少为1 1，证明：在这，证明：在这n n个点中距离恰好为个点中距离恰好为1 1的的的的点对数至多是点对数至多是3n-63n-6。证明证明:首先建立图首先建立图G=,G=,其中其中V V就取平面上给定的就取平面上给定的n n个个点点(位置相同),),当两个顶点之间的距离为当两个顶点之间的距离为1 1时时,两顶点两顶点之间用一条直线段连接之间用一条直线

12、段连接,显然图显然图G G是一个是一个n n阶简单图阶简单图.由由推论推论1,只要证明只要证明G为一平面图时为一平面图时,即知结论成立即知结论成立.反设反设 G中存在两条不同的边中存在两条不同的边a,b和和x,y相交于相交于非端点处处o,如下图如下图(a)所示所示,其夹角为其夹角为(0 ).若若 =,这时如下图这时如下图(b),显然存在两点距离小于显然存在两点距离小于1,与已知矛盾矛盾,从而从而0 .由于由于a到到b的距离为的距离为1,x到到y的距离的距离为为1,因此因此a,b,x,y中至少有两个点中至少有两个点,从交点从交点o到这两点的距到这两点的距离不超过离不超过1/2,不妨设为不妨设为a

13、,x,则点则点a与与x之间的距离小于之间的距离小于1,与已知矛盾,所以所以G中的边除端点外不再有其它交点中的边除端点外不再有其它交点,即即G为平面图为平面图.再据推论再据推论1知知,结论成立结论成立.ayxbo(a)axby(b)第第2 2节节 库拉图斯基定理与极大平面库拉图斯基定理与极大平面定义定义1 1 设G是一个平面图，通过删除G的一条边x、y,并增加一个新结点a和两条边x、a与a、y（所获得的任何图也是平面图），这样的操作称为初等细分初等细分。若可以从相同的图G通过一系列初等细分来获得图G1和G2，称称G G1 1和和G G2 2是同胚的是同胚的.如下图G1,G2,G3是同胚的.G1G

14、2G3定理定理1 1 一个图一个图G G是非平面的，是非平面的，当且仅当当且仅当它包含一个同它包含一个同胚于胚于K K3.33.3或或K K5 5的子图。（证略）的子图。（证略）例例1 1 说明彼得森图不是平面图。说明彼得森图不是平面图。解解:删去下图删去下图(a)(a)皮得森图的结点皮得森图的结点b,b,得其子图得其子图(b)H.(b)H.而而H H胚于胚于K K3.33.3,所以皮得森不是平面图所以皮得森不是平面图.fdjeihabcdefghij(a)faedighjc(b)H(c)K3,3说明说明:库拉图斯基给出了平面图的充要条件库拉图斯基给出了平面图的充要条件,但用它并不能但用它并不

15、能判别一个图是否是平面图的有效算法判别一个图是否是平面图的有效算法.定义定义2 2 设设G G是阶大于等于是阶大于等于3 3的简单可平面图，若在任意两的简单可平面图，若在任意两个不相邻的结点个不相邻的结点v vi i,v,vj j之间加入边之间加入边 v vi i,v,vj j，就会破坏图的就会破坏图的平面性，则称平面性，则称G G是是极大平面图。极大平面图的平面表示称。极大平面图的平面表示称为为三角剖分平面图.定理定理2.2.极大平面图的判别定理极大平面图的判别定理:v:v阶简单平面图阶简单平面图G G是极大平是极大平面图的面图的充要条件是是:（1 1）G G中每个面的度数都是中每个面的度数

16、都是3 3（2 2）G G中有中有e e条边条边r r个面，则个面，则3r=2e3r=2e（3 3）设）设G G带有带有v v个顶点，个顶点，e e条边，条边，r r个面则个面则 e=3v-6,r=2v-4.e=3v-6,r=2v-4.证明证明:必要性必要性:因因G G是简单图是简单图,故故G G中没有环和平行边中没有环和平行边,故不故不存在度数为存在度数为1 1或或2 2的面的面.假设假设G G存在度数大于存在度数大于3 3的面的面f,f,不妨不妨设设f为内部面为内部面,如下图如下图G,G,显然显然v v1 1与与v v3 3不相邻不相邻,在面在面f f内加入内加入面面vv1 1,v,v3

17、3,图图G G的平面性显然没有改变的平面性显然没有改变,这与图这与图G G是极大平是极大平面图矛盾面图矛盾.因此图因此图G G的每个面的度数为的每个面的度数为3,3,所以有所以有3r=2e3r=2e且且e=3v-6,r=2v-4(e=3v-6,r=2v-4(欧拉公式欧拉公式)充分性显然充分性显然.v2v1v5v3v4G定理定理2 2 设设G G是简单平面图，则是简单平面图，则G G有平面表示有平面表示 ，使使 中每条边都是直线。中每条边都是直线。证明证明:只要对极大平面图只要对极大平面图G来证明定理即可来证明定理即可(简单平面图是极大平面图的子图).当当v=3时时,G是三角形是三角形,定理显然

18、成立定理显然成立.假设定理对所有阶数小于v的极大平面图成立,并设G是三角剖分图三角剖分图.选取选取x V(G)使使x不是外部剖面边界上的点不是外部剖面边界上的点.取取边边x,y.则边则边x,y仅是某两个内部三角形的公共边仅是某两个内部三角形的公共边.不妨不妨设这两个三角形分别为设这两个三角形分别为z1xy和和z2xy.如图如图(b)所示所示.收缩边收缩边x,y,且结点且结点x和和y收缩为收缩为P,得图得图G(图图c).显然显然G是平面图是平面图,且有且有 E(G)=E(G)-3=3(V(G)-1)-6=3 V(G)-9=3 V(G)-6,即即G是是v-1阶极大平面图阶极大平面图,由归纳假设由归

19、纳假设,G有平面表示 ,使 的每条边都是直线.考虑 中边Pz1和Pz2,将它分裂成两个三角形(图(b)和图(c).这样得到的图 就是G的平面表示,而且每条边都是直线段.定理得证.z1z2z3xy(a)z1z2z3xy(b)z3z1z2p(c)凸多面体凸多面体 平面图的理论与多面体的研究密切相关平面图的理论与多面体的研究密切相关:事实上事实上,由由于每个凸多面体于每个凸多面体P可以与一个连通可平面图可以与一个连通可平面图G对应对应,G的顶点和边是P的顶点和棱,那么那么G的每个顶点的度至的每个顶点的度至少为少为3.由于由于G是一个平面图是一个平面图,则则P的面就是的面就是G的面的面,并且并且G的每

20、一条边落在两个不同面的边界上的每一条边落在两个不同面的边界上.一个多面体一个多面体P的的顶点,棱和面的数目分别用的数目分别用V,E和F来来表示表示,而且而且,这些分别是连通图这些分别是连通图G的顶点的顶点,边和面的数目边和面的数目.故欧拉公式可写成故欧拉公式可写成V-E+F=2,这就是著名的这就是著名的Euler凸多面凸多面体公式体公式.为方便起见为方便起见,用用Vn和和Fn分别表示凸多面体分别表示凸多面体P的的n度度点和点和n度面的数目度面的数目,则则n 3且且 多面体的一些性质定理多面体的一些性质定理定理定理3 3 每个凸多面体都至少有一个每个凸多面体都至少有一个n n度面度面,其中其中3

21、 3 n n 5.5.证明证明:设设F F3 3=F=F4 4=F=F5 5=0,=0,则则即有即有F F 1/3E,1/3E,又又即即V V 2/3E,2/3E,所以所以E=V+F-2 E=V+F-2 1/3E+2/3E-2=E-2.1/3E+2/3E-2=E-2.矛盾矛盾.所以结论成立所以结论成立.正多面体正多面体 每个面且每个多面角都相等的凸多面体。每个面且每个多面角都相等的凸多面体。定理定理4 4 只有五个正多面体只有五个正多面体:四面体、立方体、十二面体、四面体、立方体、十二面体、八面体、二十面体八面体、二十面体.证明证明:设设P P是正多面体且是正多面体且G G是对应的平面图是对应

22、的平面图,对任何对任何凸多面体均有凸多面体均有:因为因为P P是正多面体是正多面体,所以存在两个正整数所以存在两个正整数h(h(3)3)和和k(k(3)3)使使F=F=F Fh h且且V=V=V Vk k,因此因此,有有-8=(h-4)F-8=(h-4)Fh h+(k-4)V+(k-4)Vk k,且且hFhFh h=2E=2E=kVkVk k,因因3 3 h h 5.5.(1)(1)当当h=3h=3时时,有有12=(6-k)V12=(6-k)Vk k,由由3 3 k k 5.5.当当k=3k=3时时,V,V3 3=4,F=4,F3 3=4,=4,此时此时P P是四面体是四面体.当当k=4k=4

23、时时,V,V4 4=6,F=6,F3 3=8,=8,此时此时P P是八面体是八面体当当k=5k=5时时,V,V5 5=12,F=12,F3 3=20,=20,此时此时P P是十二面体是十二面体(2)(2)当当h=4h=4时时,有有8=(4-k)V8=(4-k)Vk k,所以所以k=3,Vk=3,V3 3=8,F=8,F4 4=6,=6,即即P P是立方体是立方体.(3)(3)当当h=5h=5时时,有有20=(10-3k)V20=(10-3k)Vk k,所以所以k=3,Vk=3,V3 3=20,=20,F F5 5=12,=12,即即P P是十二面体是十二面体.例例2 2 对哪些对哪些n,n,存

24、在存在n n条棱的凸多面体？条棱的凸多面体？解:以多面体的顶点为图的顶点,以多面体的棱为图的边,得到一个平面图G,若p(G),q(G),f(G)分别表示G的顶点数,边数和面数,则p(G)4,f(G)4,且且每个面的每个面的度数是度数是3,由Euler公式易得q(G)6,即没有棱小于6的凸多面体.四面体是棱数为6的凸多面体.若有7条棱的凸多面体,则存在满足上述条件,q(G)=7的平面图,由Euler公式p(G)+f(G)=q(G)+2=9,但G的每个面的度数至少是3,故q(G)=G(m)3f(G)(m为G的面),即f(G)(2/3)*q(G)=14/3又f(G)为整数,所以f(G)4,同理p(G

25、)4,所以p(G)+f(G)8,矛盾.所以7条棱的凸多面体不存在.现对现对k 4,以以k边形为底的棱锥即有边形为底的棱锥即有2k条棱的凸条棱的凸多面体进行讨论多面体进行讨论.若把底为若把底为k-1边形的棱锥中边形的棱锥中,底底角角处的一个三角面处的一个三角面“锯掉一个尖儿锯掉一个尖儿”,得到的是一得到的是一个有个有2k+1条棱的凸多面体条棱的凸多面体,总之总之,当当n 6,n 7时时,才有才有n条条棱的凸多面体棱的凸多面体.第三节第三节 图的平面性检测图的平面性检测定义定义1 图图G的的H片片:设设H是是G的子图，在的子图，在E(G)-E(H)上定义二元关系上定义二元关系R如下：如下：xRy在

26、在G-E(H)中存在中存在一条链一条链W使得使得:（1）W的第一条边为的第一条边为x，最后一最后一条边为条边为y；（2）W中只有两个端点属于中只有两个端点属于H(即即W的内部点不的内部点不属于属于H).R是是E(G)-E(H)上的等价关系。上的等价关系。R确定确定E(G)-E(H)上的一个划分设为上的一个划分设为S=S1、S2、Sm由由Si导出的导出的 G-E(H)的子图的子图 B1、B2、Bm 称为称为G的的H片。片。定义定义2 2.若若H1和和H2都是图都是图G的子图，称的子图，称V（H1）V（H2）为为H1和和H2在在G中的接触点集。记作中的接触点集。记作VG(H1,H2).定义定义3

27、3 设设H H是可平面图是可平面图G G的子图，的子图，是是H H的平面表示，若存的平面表示，若存在在G G的平面表示的平面表示 ,使使 称称 是是G G容许的。容许的。GG容许的子图G1非G容许的子图G2若若B是是G的的H片，片，f是是 的面而且的面而且VG（B,H），称，称B在在f内可画出，其中内可画出，其中 是是f的边界。的边界。定理定理1设设 是是G容许的，则对容许的，则对 的每一个片的每一个片B，其其 中中 证明证明:若若 是是G G容许的容许的,则存在则存在G G的一个平面表示的一个平面表示 .显然显然,H,H的片的片B B所对应的所对应的 的子图的子图必然限制在 的一个面中,因此

28、 .图图G的平面检测的的平面检测的DMP算法算法DMP算法是由算法是由Demoucron,Malgrange,Pertuiset提供的提供的.在介绍该算法前在介绍该算法前,先对图先对图G进行如下预处理进行如下预处理:(1)若若G不连通不连通,分别检测每一个连通分支分别检测每一个连通分支.当且仅当当且仅当所所有的连通分支都是平面图有的连通分支都是平面图,G就是平面图就是平面图.(2)若若G有割点有割点,分别检测每一块分别检测每一块.当且仅当当且仅当每一块是平每一块是平面图面图.(3)删去删去G中的环中的环.(4)用一条边代替用一条边代替G中中2度点和度点和与与之相关联的两条边之相关联的两条边.(

29、5)删去平行边删去平行边.反复交错使用反复交错使用(4)与与(5),直到不能使用为止直到不能使用为止.在做在做了了上述简化后上述简化后,在简单图在简单图G中利用中利用(6)和和(7)两个基本判断两个基本判断法法:(6)若若e9或或v3v-6或或 5,则则G不是不是平面图平面图.若不满足若不满足(6)和和(7),则需进一步检测则需进一步检测.DMPDMP算法算法（1 1）设）设G G1 1是是G G中的圈，求出中的圈，求出G G1 1 的平面表示的平面表示 。令。令i=1.i=1.（2 2）若）若E E（G G）-E-E（G Gi i）=，则停止。若则停止。若E E（G G）-E-E（G Gi

30、i），则确定则确定G G的所有的所有G Gi i片片，对每个，对每个G Gi i片片B B，求出集求出集 （3 3）若存在）若存在G Gi i片片B B使使 则停止，此时知则停止，此时知G G是非平是非平面图面图 。若存在。若存在G Gi i片片B B使使 则令则令f=;f=;若若不存在这样的片不存在这样的片B B，则令，则令B B是任何一个是任何一个G Gi i片并任取片并任取 。(4)(4)选取一条选取一条xyxy路路P Pi i B B使使x,yx,y V VG G（B B，G Gi i）,令令G Gi+1i+1=G Gi i P P,并把并把P Pi i画在的画在的 面面 f f内得内

31、得G Gi+1i+1的一个平面表示的一个平面表示 ，用，用i+1i+1代替并转入第代替并转入第2 2步。步。例1利用DMP算法检测图G的平面性123456782134875613132661234276134第四节第四节 平面图的着色平面图的着色定义定义1 1设设G G是无孤立结点的连通的平面图，且是无孤立结点的连通的平面图，且G G有有K K个面个面F F1 1，F F2 2，F Fk k(包括外部面包括外部面).).则按下列过则按下列过程作程作G G的对偶图的对偶图G G .（1 1）在）在G G的每个面内设置一个结点的每个面内设置一个结点v vi i(1(1 i i k)k)。（2 2）

32、过过F Fi i与与F Fj j的每一条公共边的每一条公共边e ek k作一条仅作一作一条仅作一条边条边 v vi i,v,vj j 与与e ek k相交。相交。（3 3）当且仅当）当且仅当e ek k只是只是F Fi i的边界时，的边界时，v vi i恰恰有一自有一自回路与回路与e ek k相交。相交。这样所得的图这样所得的图G*G*称为图称为图G G的对偶图的对偶图.若若G*G*与与G G同构同构,称称G G是自对偶的是自对偶的.如下图如下图G G的对偶图为图中的对偶图为图中虚线虚线.12341324定义定义2 2 图的着色图的着色是对该图的每个顶点都指定一种颜是对该图的每个顶点都指定一种

33、颜色，使没有两个相邻的顶点指定为相同的颜色。如果色，使没有两个相邻的顶点指定为相同的颜色。如果这些顶点选自于一个有这些顶点选自于一个有k k种颜色的集合，而不管种颜色的集合，而不管k k种颜种颜色是否都用到，这样的着色色是否都用到，这样的着色称为称为k k着色着色。定义定义3 3 图图G G的色数的色数是着色这个图是着色这个图G G所需要的最少颜色数。所需要的最少颜色数。记作记作(G)(G)。图图G的色素也称为的色素也称为图图G的点色素的点色素.从定义可知从定义可知,对于对于G的任何子图的任何子图H,均有均有(H)(G).若若G是是n阶完全图阶完全图,若若G是是n阶完全图阶完全图,则则(G)=

34、n;若若G是至少有一边的二分是至少有一边的二分图图,则则(G)=2;若若G是长为奇数的圈是长为奇数的圈,则则(G)=3.当当(G)3时时,G的特征至今尚未清楚的特征至今尚未清楚,在下一节在下一节,将给出将给出G的色素的色素(G)的一个上界的一个上界.定理定理1 1 设设u u和和v v是图是图G G中两个不相邻的顶点中两个不相邻的顶点,则则(G)=min(G)=min(G+u,v),(G+u,v),(G(Gu,v),u,v),其中其中G Gu,vu,v是把是把G G中结点中结点u u与与v v重合成一个新结点，且重合成一个新结点，且G G中分别与中分别与u u与与v v关联的边都与该新结点关联

35、。关联的边都与该新结点关联。证明证明:记记e=e=u,vu,v,（1 1）设）设(G)=k,(G)=k,并考虑并考虑G G的的K K着色着色.假设假设顶点顶点u u与与v v染不同的颜色染不同的颜色,则则G G的的k k着色也是着色也是G+eG+e的的k k着色着色.此时此时(G+e)G+e)k k=(G).(G).现假设顶点现假设顶点u u和和v v的染色相同的染色相同,则则G G的一个的一个k k染色可得到染色可得到G Ge e的一个染色的一个染色.故故(G Ge)e)k k=(G).(G).又在又在G G的的k k染色中染色中,或者或者u u与与v v染为不同染为不同的颜色的颜色,或者为

36、相同的颜色或者为相同的颜色,故故minmin(G+u,v),(G+u,v),(G(Gu,v)u,v)(G).(G).（2）G是G+e的子图,显然(G)(G+e).设(G(Ge)=ke)=k1 1,并把并把结点结点u u和和v v重合所得的新结点记重合所得的新结点记为为y,y,则在则在G Ge e的的k k1 1着色中着色中,把分配给把分配给y y的颜色分配给的颜色分配给G G中中u u和和v(u,vv(u,v不相邻不相邻),),即可得到即可得到G G的一个的一个k k1 1着色着色.故故 (G)(G)k1=(G(Ge)e)所以所以(G)(G)minmin(G+e),(G+e),(G(Gu,v)

37、.u,v).综（综（1 1）（）（2 2）所述）所述,有有 (G)=min(G)=min(G+u,v),(G+u,v),(G(Gu,v).u,v).四色问题四色问题:连通简单平面图的色素不超过连通简单平面图的色素不超过4.4.四色问题是盖思里于四色问题是盖思里于18521852年提出年提出,后经众多数后经众多数学家尝试证明学家尝试证明,均以失败告终均以失败告终.1976.1976年年,美国数学家美国数学家阿佩尔和黑肯宣布借助用计算机证明阿佩尔和黑肯宣布借助用计算机证明,但时间超过但时间超过了了10001000小时小时,其可靠性仍在置疑之中其可靠性仍在置疑之中.定理定理2 2（五色定理）连通简单

38、平面图（五色定理）连通简单平面图G G的色数为不超过的色数为不超过5.5.证明证明:对图的顶点数对图的顶点数n作归纳作归纳.n 5时时,结论显然结论显然.若若n-1个顶点时结论成立个顶点时结论成立.下下证有证有n个顶点时结论也成立个顶点时结论也成立.由于由于G是平面图是平面图,则则(G)5.故在故在G中至少存在一个顶点中至少存在一个顶点v0,其度数其度数d(v0)5.在图中删去顶点在图中删去顶点v0得图得图G,由归纳假设知由归纳假设知G的的色素为色素为5.然后将然后将v0又加回去又加回去,有两种情况有两种情况:(1)d(v0)5或或d(v0)=5但和但和v0邻接的邻接的5个结点的颜色数个结点的

39、颜色数小于小于5.则则v0极易着色极易着色,只要选择与四周顶点不同的只要选择与四周顶点不同的颜色着色即可颜色着色即可.(2)d(v0)=5且和且和v0邻接着的邻接着的5个结点着的颜色的是个结点着的颜色的是5种颜色种颜色,如下图如下图(a)所示所示.称称G中所有红黄色顶点中所有红黄色顶点为红黄集为红黄集,称称GG中所有黑白色顶点为黑白集中所有黑白色顶点为黑白集.故故又有两种可能又有两种可能.(i)v(i)v1 1和和v v3 3属于红黄集导出子图的两个不同块中属于红黄集导出子图的两个不同块中,如如下图下图(b)(b)所示所示.将将v v1 1所在块的红黄色对调所在块的红黄色对调,并不影并不影响响

40、GG的正常着色的正常着色.然后将然后将v v0 0着上红色着上红色,即得图即得图G G的的正常着色正常着色.蓝v3 黑v4v0黄v3白v2红v1(a)(b)(ii)v(ii)v1 1和和v v3 3属于红黄集导出子图的同一块中属于红黄集导出子图的同一块中,则则v1和和v v3 3之间必有一条属于红黄集的路之间必有一条属于红黄集的路P,P加上结点加上结点v0可可构成圈构成圈C:v0v1pv3v0,如下图如下图所示所示.由于由于C的存在的存在,将黑白集分成两个子集将黑白集分成两个子集,一个在一个在C内内,一个在一个在C外外.于是问题转化为于是问题转化为(i)(i)的类型的类型,对黑白集按对黑白集按

41、(i)(i)型的办型的办法处理法处理,即得图即得图G G的的正常着色正常着色.蓝v3 黑v4v0黄v3白v2红v1(b)(c)(a)例例1 1求下图求下图G G和和H H的色数的色数acfgbedGHa:a:红红,b:,b:蓝蓝,c:,c:绿绿,d:,d:红红,e:e:绿，绿，f:f:蓝蓝,g:g:红红(3色色)例例2.2.由由n(nn(n 3)3)个顶点个顶点v v1 1,v,v2 2,v vn n以及边以及边vv1 1,v,v2 2,vv2 2,v,v3 3,v,vn-1n-1,v,vn n v vn n,v,v1 1 组成的图称为圈组成的图称为圈图图,记作记作C Cn n,试问圈图的试问

42、圈图的C Cn n的色数是多少。（分的色数是多少。（分n n为为奇数，或偶数）奇数，或偶数）例例3.K3.Kn n和和K Km,nm,n的色数分别是多少？的色数分别是多少？解解:由于由于K Kn n的每两个顶点都相邻的每两个顶点都相邻,而当两个相邻的顶而当两个相邻的顶点必指定不同的颜色点必指定不同的颜色,故故K Kn n的色素为的色素为n.n.K Km,nm,n的色数为的色数为2.2.用一种颜色着色用一种颜色着色m m个顶点个顶点,用另用另一种颜色着色一种颜色着色n n个顶点个顶点.第五节 图着色的应用贮藏问题:某工厂生产n种化学制品c1,c2,cn,其中某些制品是互不相容.若它们相互接触,则

43、会发生化学反应甚至引起爆炸,为安全起见,该工厂必须把仓库分成若干隔间,以便把不相容的化学制品储藏在不同的隔间,试问该仓库至少应分成几个隔间?解:构建简单图G=,其中V(G)=c1,c2,cn 边ci,cjE(G)化学制品ci与cj互不相容.易知,仓库的最少隔间数等于图G的色素(G).电视频道分配问题 某地区内有n家电视发射台T1,T2,Tn.主管部门为每家电视发射台分配一个频道.为排除干扰,使用同一频道的电视台之间的距离必须大于指定的正数d,试问该地区至少需要多少频道?构建简单图G=,其中V(G)=T1,T2,Tn 边Ti,TjE(G)Ti与Tj之间距离d.易知,需要的最少频道等于图G的色素(

44、G).考试安排问题 某高校有n门选修课程v1,v2,vn需要进行期末考试.同一学生不能在同一天里参加两门课程的考试.问学校的期末考试需要几天?构建简单图G=,其中V(G)=v1,v2,vn 边vi,vjE(G)vi与vj被同一同学选修.故考试需要的最小天数等于图G的色素(G).变址寄存器 在有效的编译器里,当把频繁使用的变量暂时保存在中央处理单元而不是保存在常规内存时,可以加速循环的执行.对于给定的循环来说,需要多少个变址寄存器?可以这样建立模型:设图里的每个顶点表示循环里的一个变量.若在循环执行期间两个顶点所表示的变量必须同时保存在变址寄存器里,则这两个顶点之间有边.因此,所需要的变址寄存器

45、数就是该该图的色数图的色数.顺序着色算法 到目前为止,还没有一个有效算法来确定色素.顺序着色算法是一个求x(G)的有效算法:设G=是简单无向图，V=x1,x2xn用N(xi)表示与xi相邻的全部顶点集合；对顶点xi着色C，记为(xi)=C.(1)i:=1(2)c:=1(3)若对yN(xi),(y)C,则令(xi)=C并转入第5步。(4)C:=C+1并转入第3步。(5)若in，则i:=i+1并转回第2步，否则停止.定理定理1 1设设G G是简单连通图，顺序着色法产生是简单连通图，顺序着色法产生G G的顶点的一个的顶点的一个(G(G）+1+1着色，所以着色，所以(G)(G)（G G）+1(+1(不

46、证不证)证明证明:顺序着色法用语言描述就是一次考虑每一顶点顺序着色法用语言描述就是一次考虑每一顶点,将将尚未指定给与其邻接的顶点的最小颜色指定给该顶点尚未指定给与其邻接的顶点的最小颜色指定给该顶点,特特别是决不能将两个相邻顶点指定为相同的颜色别是决不能将两个相邻顶点指定为相同的颜色,因此顺序因此顺序着色算法确实产生一个顶点着色着色算法确实产生一个顶点着色.最多存在最多存在 个顶点与个顶点与x xi i邻接邻接,故在故在x x1 1,x,x2 2,x,xi-1i-1中最多有中最多有 个顶点个顶点x xi i邻接邻接.所以所以,当算法对顶点当算法对顶点x xi i着色时着色时,在颜色在颜色1,2,

47、1,2,+1+1中中至少有一至少有一种颜色尚未指定给与种颜色尚未指定给与x xi i邻接的顶点并且算法将这些颜色邻接的顶点并且算法将这些颜色中最小的指定给中最小的指定给x xi i,于是顺序着色算法产生图于是顺序着色算法产生图G G的顶点的的顶点的一个一个+1+1着色着色.例例1 1试用顺序着色法求图试用顺序着色法求图G G的色数。的色数。1211212121321211321212132121 定理定理1给出了连通简单图给出了连通简单图G的色数的上界的色数的上界.1941年年R.L.Brooks证明了下面的定理证明了下面的定理.定理定理2.设设G是一个连通简单图是一个连通简单图,其顶点的其顶

48、点的最大度最大度为为.若若G既不是完全图既不是完全图Kn,也不是奇数圈图也不是奇数圈图Cn,则则(G).第六节第六节 边着色边着色定义定义1 1 图图G的边着色对的边着色对G的每一条边都指定一的每一条边都指定一个颜色，使得没有两个相邻的边都为同一种个颜色，使得没有两个相邻的边都为同一种颜色。如果这些颜色都取自一个有颜色。如果这些颜色都取自一个有K种颜色的种颜色的集合，而不管这集合，而不管这K种颜色是否都用掉，这样的种颜色是否都用掉，这样的边着色称为边着色称为K边着色边着色。定义定义2 2 图图G的边着色数是着色这个图的边着色数是着色这个图G需要的需要的最少颜色数。记为最少颜色数。记为(G).边

49、着色转化为点着色的方法：边着色转化为点着色的方法：边边着色可以转化为相应的点着色着色可以转化为相应的点着色,即在边着色即在边着色图中图中,将所有的边对应地转化成点着色图中的结将所有的边对应地转化成点着色图中的结点点,结点转化成相应的边结点转化成相应的边.因此因此,由点着色性质定由点着色性质定理不难得到如下定理理不难得到如下定理.定理定理1 1 若若G G是非空连通的简单图，是非空连通的简单图，G G的最大顶点的最大顶点度为度为 ,则则 (G)(G)+1+1。（不证）。（不证）图的图的分类分类:据定理据定理1,1,所有非空图集可以分成两类所有非空图集可以分成两类,若若(G)=(G)=(G),(G

50、),则则G G为为第一类图第一类图,否则称为否则称为第二第二类图类图.定理定理2 任意二分图任意二分图G是第一类图。（不证）是第一类图。（不证）K着色问题着色问题:已知一个图已知一个图G和和k种颜色的集合种颜色的集合:1,2,k,则存在图则存在图G的多少的多少k-着色着色?定义定义3 图图G的不同的不同k着色的数目，称为图着色的数目，称为图G的色的色多项式。记作多项式。记作f(G,k).说明说明:(1)若若k0的的最小最小k 即为即为G的的色数色数.(2)设设mi是是i种颜色对图种颜色对图G的顶点进行着色的不同方的顶点进行着色的不同方案数案数.用用k(k i)种颜色对图种颜色对图G进行着色进行