图论第四章 平面图及着色

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

2、面外部面。包围面的长度最短的闭链称为称为该面的边界该面的边界。面的边界的长度称为称为该面的度数该面的度数。例例2 指出下图所示平面图的面、面的边界及指出下图所示平面图的面、面的边界及面的度数。面的度数。e61234567e1e2e3e4e5e7e8e10e9f1f4f3f2f5解解:面f1,其边界1e15e24e43e72e101,d(f1)=5. 面f2,其边界1e102e87e91,d(f2)=3. 面f3,其边界2e73e67e82,d(f3)=3. 面f4,其边界3e44e57e63,d(f4)=3. 外部面f5, 其边界1e15e24e36e34 e57e91,d(f5)=6.定理定

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

4、 假设公式对n条边的图成立.设设G有有n+1条边条边.若G不含圈,任取一点x,从结点x开始沿路行走.因G不含圈,所以每次沿一边总能达到一个新结点,最后会达到一个度数为1的结点,不妨设为a,在结点a不能再继续前进.删除结点a及其关联的边得图G,G含有n条边.由假设公式对G成立,而G比G多一个结点和一条边,且G与G面数相同,故公式也适合于G. 若G含有圈C,设y是圈C上的一边,则边y一定是两个不同面的边界的一部分.删除边y得图G,则G有n条边.由假设公式对G成立，而G比G多一边和多一面,G与G得顶点数相同.故公式也成立.推论推论1 设设G是带是带v个顶点，个顶点，e条边的连通的平面简条边的连通的平

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

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

7、,2,w)从而有 vi- ei+ ri =2w又 vi=v, ei=e, ri =r+(w-1)(外部面被重复计算了w-1次.).所以有:V-e+r+(w-1)=2w整理即得: v- e+ r=1+w.推论推论4 设设G是任意平面简单图，则是任意平面简单图，则 (G) 5。证明证明:设G有v个顶点e条边.若e6,结论显然成立;若e6,假设G的每个顶点的度数6,则由推论1,有6v 2e 6v-12矛盾,所以 (G)5.例例4 平面上有平面上有n个顶点，其中任意两个点之间的距离个顶点，其中任意两个点之间的距离至少为至少为1.证明证明 在这在这n个点中距离恰好为个点中距离恰好为1的点对数的点对数至多

8、是至多是3n-6。证明证明:首先建立图G=,其中V就取平面上给定的n个点(位置相同),当两个顶点之间的距离为1时,两顶点之间用一条直线段连接.显然,图G是一个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,x,则点a与x之间的距离小于1,与已知矛盾,所以G中的边除端点外不再有其它交点,即G为平面图

9、.再据推论1,知结论成立.ayxbo (a)axby(b)第第2节节 库拉图斯基定理与极大平面库拉图斯基定理与极大平面定义定义1 设G是一个平面图，通过删除G的一条边x、y,并增加一个新结点a和两条边x 、a与a、y（所获得的任何图也是平面图），这样的操作称为初等细分初等细分。若可以从相同的图G通过一系列初等细分来获得图G1和G2，称称G1和和G2是同胚的是同胚的. 如下图G1,G2,G3是同胚的.G1G2G3定理定理1一个图一个图G是非平面的，是非平面的，当且仅当当且仅当它包含一个它包含一个同胚于同胚于K3.3或或K5的子图。（证略）的子图。（证略）例例1 说明彼得森图不是平面图。说明彼得森

10、图不是平面图。解解:删去下图删去下图(a)皮得森图的结点皮得森图的结点b,得其子图得其子图(b)H.而而H胚于胚于K3.3,所以皮得森不是平面图所以皮得森不是平面图.fdjeihabcdefghij(a)faedighjc(b)H(c)K3,3说明说明:库拉图斯基给出了平面图的充要条件库拉图斯基给出了平面图的充要条件,但用它并不能但用它并不能判别一个图是否是平面图的有效算法判别一个图是否是平面图的有效算法.定义定义2 设G是阶大于等于3的简单可平面图，若在任意两个不相邻的结点vi,vj之间加入边vi,vj，就会破坏图的平面性，则称G是极大平面图是极大平面图。极大平面图的平面表示称为表示称为三角

11、剖三角剖分平面图分平面图.定理定理2. 极大平面图的判别定理极大平面图的判别定理:v阶简单平面图G是极大平面图的充要条件是充要条件是:（1）G中每个面的度数都是中每个面的度数都是3（2） G中有中有e条边条边r个面，则个面，则3r=2e（3）设）设G带有带有v个顶点，个顶点，e条边，条边，r个面则个面则 e=3v-6,r=2v-4.证明证明:必要性必要性:因G是简单图,故G中没有环和平行边,故不存在度数为1或2的面.假设G存在度数大于3的面f,不妨设为内部面,如下图G,显然v1与v3不相邻,在面f内加入面v1,v3,图G的平面性显然没有改变,这与图G是极大平面图矛盾.因此图G的每个面的度数为3

12、,所以有3r=2e且e=3v-6,r=2v-4(欧拉公式) 充分性显然充分性显然.v2v1v5v3v4G定理定理2 设设G是简单平面图，则是简单平面图，则G有平面表示有平面表示 ，使使 中每条边都是直线。中每条边都是直线。证明证明:只要对极大平面图G来证明定理即可(简单平面图是极大平面图的子图).当v=3时,G是三角形,定理显然成立.假设定理对所有阶数小于v的极大平面图成立,并设G是三角剖分图.选取xV(G)使x不是外部剖面边界上的点.取边x,y.则边x,y仅是某两个内部三角形的公共边.不妨设这两个三角形分别为z1xy和z2xy.如图(b)所示.收缩边x,y,且结点x和y收缩为P,得图G(图c

13、).显然G是平面图,且有E(G)= E(G)-3=3(V(G)-1)-6= 3V(G)-9= 3V(G)-6,即G是v-1阶极大平面图,由归纳假设,G有平面表示 GGG 使 的每条边都是直线. 考虑 中边Pz1和Pz2,将它分裂成两个三角形(图(b)和图(c).这样得到的图 就是G的平面表示,而且每条边都是直线段.定理得证.GGGz1z2z3xy(a)z1z2z3xy(b)z3z1z2p(c)凸多面体凸多面体 平面图的理论与多面体的研究密切相关平面图的理论与多面体的研究密切相关:事实上事实上,由于每个凸多面体由于每个凸多面体P可以与一个连通可平面图可以与一个连通可平面图G对对应应,G的顶点和边

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

15、度面的数目,则则n 3且且 332nnnnnFnVE多面体的一些性质定理多面体的一些性质定理定理定理3 每个凸多面体都至少有一个每个凸多面体都至少有一个n度面度面,其中其中3 n 5.证明证明:设F3=F4=F5=0,则即有F1/3E,又即V 2/3E,所以E=V+F-2 1/3E+2/3E-2=E-2.矛盾. 所以结论成立.FFFnFEnnnnnn666266633233nnnnEnVVV正多面体：每个面且每个多面角都相等的凸多面体。正多面体：每个面且每个多面角都相等的凸多面体。定理定理4 只有五个正多面体只有五个正多面体:四面体、立方体、十二面四面体、立方体、十二面体、八面体、二十面体体、

16、八面体、二十面体.证明证明:设P是正多面体且G是对应的平面图,对任何凸多面体均有: 因为P是正多面体,所以存在两个正整数h(3)和k(3)使F=Fh且V=Vk,因此,有-8=(h-4)Fh+(k-4)Vk,且hFh=2E=kVk,因3h5.)4()4(4444224448333333nnnnnnnnnnnnVnFnFVnVnFFVEEFVE(1)当h=3时,有12=(6-k)Vk,由3k5.当k=3时,V3=4,F3=4,此时P是四面体.当k=4时,V4=6,F3=8,此时P是八面体当k=5时,V5=12,F3=20,此时P是十二面体(2)当h=4时,有8=(4-k)Vk,所以k=3,V3=8

17、,F4=6,即P是立方体.(3)当h=5时,有20=(10-3k)Vk,所以k=3,V3=20,F5=12,即P是十二面体.例例2 对哪些对哪些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的每个面

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

19、（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. 若H1和H2都是图G的子图，称V(H1) V(H2)为H1和H2在G中的接触点集。记作VG(H1,H2).定义3 设H是可平面图G的子图， 是H的平面表示，若存在G的平面表示 ,使 称 是G容许的。HHGHGGG容许的子图G1非G容许的子图G2 若B是G的H片，f是 的面,而且VG（B,H） ，称B在f内可画出，其中 是f的边界

20、。定理定理1 设设 是是G容许的，则对容许的，则对 的每一个片的每一个片B， 其中其中 证明证明:若若 是是G容许的容许的,则存在则存在G的一个平面表示的一个平面表示 .显然显然,H的片的片B所对应的所对应的 的子图的子图必然限制在 的一个面中,因此 . ( ,)GF B H H)(fBH)(fBHHH,)(, )(),(内可画出在且的面集为fBHHFHFffHBFGHGH),(HBFG, . .G st HG图图G的平面检测的的平面检测的DMP算法算法 DMP算法是由算法是由Demoucron,Malgrange,Pertuiset提供的提供的.在介绍该算法前在介绍该算法前,先对图先对图G进

21、行如下进行如下预处理预处理:(1)若G不连通,分别检测每一个连通分支.当且仅当当且仅当所有的连通分支都是平面图,G就是平面图.(2)若G有割点,分别检测每一块.当且仅当每一块是平面图.(3)删去G中的环.(4)用一条边代替G中2度点和与之相关联的两条边.(5)删去平行边. 反复交错使用(4)与(5),直到不能使用为止. 在做了上述简化后,在简单图G中利用(6)和(7)两个基本判断法:(6)若若e9或或v3v-6或或 5,则则G不是平面图不是平面图.若不满足(6)和(7),则需进一步检测.DMP算法算法（1）设）设G1是是G中的圈，求出中的圈，求出G1 的平面表示的平面表示 。令。令i=1.（2

22、）若）若E(G)-E(Gi)= ，则停止。若，则停止。若E(G)-E(Gi) ,则确则确定定G的所有的所有Gi片，对每个片，对每个Gi片片B，求出集，求出集 （3）若存在）若存在Gi片片B使使 则停止，此时知则停止，此时知G是非平面是非平面图。若存在图。若存在Gi片片B使使 则令则令f= ;若不存若不存在这样的片在这样的片B，则令，则令B是任何一个是任何一个Gi片并任取片并任取 。 (4)选取一条选取一条xy路路Pi B使使x,y VG(B,Gi),令令Gi+1= Gi P,并把并把Pi画在的画在的 面面 f内得内得Gi+1的一个平面表示的一个平面表示 ，用，用i+1代替代替并转入第并转入第2

23、步。步。 1G),(iGGBF),(iGGBF( ,)1GiF BG ),(iGGBF),(iGGBFf iG1iG例1 利用DMP算法检测图G的平面性123456782134875613132661234276134第四节第四节 平面图的着色平面图的着色定义定义1 设G是无孤立结点的连通的平面图，且G有K个面F1，F2，Fk(包括外部面).则按下列过程作G的对偶图G .（1）在G的每个面内设置一个结点vi(1ik)。（2）过Fi与Fj的每一条公共边ek作一条仅作一条边vi,vj与ek相交。（3）当且仅当ek只是Fi的边界时，vi恰有一自回路与ek相交。 这样所得的图G*称为图G的对偶图.若G

24、*与G同构,称G是自对偶的.如下图G的对偶图为图中虚线.12341324定义定义2 图的着色图的着色是是对该图的每个顶点都指定一种颜色，使没有两个相邻的顶点顶点指定为相同的颜色。如果这些顶点选自于一个有k种颜色的集合，而不管k种颜色是否都用到，这样的着色称为称为k着色着色。定义定义3 图图G的色数的色数是是着色这个图G所需要的最少颜色数。记作记作 (G)。 图G的色数也称为也称为图图G的点色数的点色数.从定义可知从定义可知,对于对于G的任何子图H,均有 (H) (G). 若G是n阶完全图,则则 (G)=n;若G是至少有一边的二分图,则则 (G)=2;若G是长为奇数的圈,则则 (G)=3. 当当

25、 (G) 3时时,G的特征至今尚未清楚的特征至今尚未清楚,在下一节在下一节,将给出将给出G的色数的色数 (G)的一个上界的一个上界.定理定理1 设设u和和v是图是图G中两个不相邻的顶点中两个不相邻的顶点,则则 (G)=min (G+u,v), (Gu,v) 其中其中Gu,v是把是把G中结点中结点u与与v重合成一个新结点，重合成一个新结点，且且G中分别与中分别与u与与v关联的边都与该新结点关联。关联的边都与该新结点关联。证明证明:记记e=u,v,（1）设）设 (G)=k,并考虑G的K着色.假设顶点u与v染不同的颜色,则G的k着色也是G+e的k着色.此此时时 (G+e) k= (G).现假设顶点u

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

27、(G+e), (Gu,v). 综合综合(1)(2)所述所述,有有 (G)=min (G+u,v), (Gu,v). 四色问题四色问题:连通简单平面图的色数不超过4. 四色问题四色问题是盖思里于1852年提出,后经众多数学家尝试证明,均以失败告终.1976年,美国数学家阿佩尔和黑肯宣布借助用计算机证明,但时间超过了1000小时,其可靠性仍在置疑之中. 定理定理2（五色定理）连通简单平面图（五色定理）连通简单平面图G的色数为不超过的色数为不超过5.证明证明:对图的顶点数n作归纳. 当n5时,结论显然.若n-1个顶点时结论成立.下证有n个顶点时结论也成立.由于G是平面图,则(G) 5.故在G中至少存

28、在一个顶点v0,其度数d(v0) 5.在图中删去顶点v0得图G,由归纳假设知G的色数为5.然后将v0又加回去,有两种情况:(1)d(v0)5或d(v0)=5但和v0邻接的5个结点的颜色数小于5.则v0极易着色,只要选择与四周顶点不同的颜色着色即可.(2) d(v0)=5且和v0邻接着的5个结点着的颜色的是5种颜色,如下图(a)所示.称G中所有红黄色顶点为红黄红黄集集,称G中所有黑白色顶点为黑白集黑白集.故又有两种可能.(i)v1和v3属于红黄集导出子图的两个不同块中,如下图(b)所示.将v1所在块的红黄色对调,并不影响G的正常着色.然后将v0着上红色,即的图G的正常着色.蓝v3 黑v4v0黄v

29、3白v2红v1(a)(b)(ii)v1和v3属于红黄集导出子图的同一块中,则v1和v3之间必有一条属于红黄集的路P,P加上结点v0可构成圈C:v0v1pv3v0,如下图(c)所示.由于C的存在,将黑白集分成两个子集,一个在C内,一个在C外.于是问题转化为(i)的类型,对黑白集按(i)型的办法处理,即得图G的正常着色.蓝v3 黑v4v0黄v3白v2红v1(b)(c)(a)例例1 求下图求下图G和和H的色数的色数acfgbedGHa:红红,b:蓝蓝,c:绿绿,d:红红,e:绿，绿，f:蓝蓝, g:红红(3色色)例例2. 由n(n3)个顶点v1,v2,vn以及边v1,v2, v2,v3, , vn-

30、1,vn vn,v1 组成的图称为圈图,记作Cn,试问圈图的Cn的色数是多少.(分n为奇数，或偶数）例例3. Kn和和Km,n的色数分别是多少？的色数分别是多少？解解:由于Kn的每两个顶点都相邻,而当两个相邻的顶点必指定不同的颜色,故Kn的色数为n. Km,n的色数为2.用一种颜色着色m个顶点,用另一种颜色着色n个顶点.第五节第五节 图着色的应用图着色的应用 贮藏问题贮藏问题:某工厂生产n种化学制品c1,c2,cn,其中某些制品是互不相容.若它们相互接触,则会发生化学反应甚至引起爆炸,为安全起见,该工厂必须把仓库分成若干隔间,以便把不相容的化学制品储藏在不同的隔间,试问该仓库至少应分成几个隔间

31、?解:构建简单图G=,其中V(G)=c1,c2,cn 边ci,cjE(G)化学制品ci与cj互不相容. 易知,仓库的最少隔间数等于图G的色数x(G).电视频道分配问题 某地区内有n家电视发射台T1,T2,Tn.主管部门为每家电视发射台分配一个频道.为排除干扰,使用同一频道的电视台之间的距离必须大于指定的正数d,试问该地区至少需要多少频道? 构建简单图G=,其中V(G)=T1,T2,Tn 边Ti, TjE(G)Ti与Tj之间距离d. 易知,需要的最少频道等于图G的色数 (G).考试安排问题 某高校有n门选修课程v1,v2,vn需要进行期末考试.同一学生不能在同一天里参加两门课程的考试.问学校的期

32、末考试需要几天? 构建简单图G=,其中V(G)=v1,v2,vn 边vi, vjE(G)vi与vj被同一同学选修. 故考试需要的最小天数等于图G的色数 (G).变址寄存器 在有效的编译器里,当把频繁使用的变量暂时保存在中央处理单元而不是保存在常规内存时,可以加速循环的执行.对于给定的循环来说,需要多少个变址寄存器? 可以这样建立模型:设图里的每个顶点表示循环里的一个变量.若在循环执行期间两个顶点所表示的变量必须同时保存在变址寄存器里,则这两个顶点之间有边.因此,所需要的变址寄存器数就是该图的色数所需要的变址寄存器数就是该图的色数.顺序着色算法顺序着色算法 到目前为止到目前为止,还没有一个有效算

33、法来确定色数还没有一个有效算法来确定色数.顺序着顺序着色算法是一个求色算法是一个求 (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 设设G是简单连通图，顺序着色法产生是简单连通图，顺序着色法产生G的顶点的顶点的一个的一个 (G）+1着色，所以着色，所以

34、(G)（G）+1(不证不证)证明证明:顺序着色法用语言描述就是一次考虑每一顶点,将尚未指定给与其邻接的顶点的最小颜色指定给该顶点,特别是决不能将两个相邻顶点指定为相同的颜色,因此顺序着色算法确实产生一个顶点着色.最多存在个顶点与xi邻接,故在x1,x2,xi-1中最多有个顶点xi邻接.所以,当算法对顶点xi着色时,在颜色1,2, +1中至少有一种颜色尚未指定给与xi邻接的顶点并且算法将这些颜色中最小的指定给xi,于是顺序着色算法产生图G的顶点的一个+1着色.例例1 试用顺序着色法求图试用顺序着色法求图G的色数。的色数。1211212121321211321212132121 定理定理1给出了连

35、通简单图给出了连通简单图G的色数的上界的色数的上界.1941年年R.L.Brooks证明了下面的定理证明了下面的定理.定理定理2. 设G是一个连通简单图,其顶点的最大度为.若G既不是完全图Kn,也不是奇数圈图Cn,则 (G) .第六节第六节 边着色边着色定义定义1 图图G的边着色对的边着色对G的每一条边都的每一条边都指定一个颜色，使得没有两个相邻的边都为同一种颜色。如果这些颜色都取自一个有K种颜色的集合，而不管这K种颜色是否都用掉，这样的边着色称为称为K边着色。边着色。定义定义2 图图G的边着色数是的边着色数是着色这个图G需要的最少颜色数。记为记为 (G).边着色转化为点着色的方法：边着色转化

36、为点着色的方法： 边着色可以转化为相应的点着色,即在边着色图中,将所有的边对应地转化成点着色图中的结点,结点转化成相应的边.因此因此,由点着色性质定理不难得到如下由点着色性质定理不难得到如下定理定理.定理定理1 若若G是非空连通的简单图，是非空连通的简单图，G的最大顶点度为的最大顶点度为 ,则则 (G) +1。（不证）。（不证）图的分类图的分类:根据定理根据定理1,所有非空图集可以分成两类所有非空图集可以分成两类,若若 (G)= (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(ki)种颜色对图G进行着色,每取i种颜色时,共有miCki种不同的着色方案,故有:f(G,k)=m1Ck