new-图着色.ppt

《new-图着色.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1图的着色一、图的边着色二、图的顶点着色主要内容2现实生活中很多问题，可以模型为所谓的边着色问题来处理。例如排课表问题。(一)、边着色排课表问题：设有m位教师，n个班级，其中教师xi要给班级yj上pij节课。求如何在最少节次排完所有课。建模：令X=｛x1,x2,…,xm｝,Y=｛y1,y2,…,yn｝,xi与yj间连pij条边，得偶图G=(X,Y).于是，问题转化为如何在G中将边集E划分为互不相交的p个匹配，且使得p最小。如果每个匹配中的边用同一种颜色染色，不同匹配中的边用不同颜色染色，则问题转化为在G中给每条边染色，相邻边染不同色，至少需要的颜色数。3

2、这就需要我们研究所谓的边着色问题。定义1设G是图，对G的边进行染色，若相邻边染不同颜色，则称对G进行正常边着色；如果能用k中颜色对图G进行正常边着色，称G是k边可着色的。正常边着色定义2设G是图，对G进行正常边着色需要的最少颜色数，称为G的边色数，记为：4注：对图的正常边着色，实际上是对G的边集合的一种划分，使得每个划分块是G的一个边独立集(无环时是匹配);图的边色数对应的是图的最少独立集划分数。因此，图的边着色，本质上是对应实际问题中的“划分”问题或“分类”问题。5(二)、几类特殊图的边色数1、偶图的边色数定理1证明：设又设Δ=n。设颜色集合设为｛0，

3、1，2，…，n-1｝,п是Km,n的一种n着色方案，满足：6我们证明：上面的着色是正常边着色。对Km,n中任意的两条邻接边xiyj和xiyk。若则：i+j(modn)=i+k(modn),得到j=k，矛盾！所以，上面着色是正常着色。所以：又显然，所以，例1用最少的颜色数对K3,4正常边着色。7定理2(哥尼，1916)若G是偶图，则x2x1x0y3y2y1y08定理3(维津定理，1964)若G是单图，则：注：根据这个定理，如果我们要证明某一个图的边染色数是Δ，只要我们找到了一种染色方式用的色数是Δ就可以了。如果要证明是Δ+1，我们只需要证明用Δ色不能正常染

4、色。一般用反证法，假设能用Δ染色，得到矛盾。9注:(1)根据维津定理，单图可以按边色数分成两类图，一是色数等于Δ(G)的单图，二是色数等于Δ(G)+1的单图。(2)维津(Vizing):1937年出生于乌克兰的基辅。1954年开始在托木斯克大学学习数学，1959年大学毕业保送到莫斯科斯特克罗夫研究所攻读博士学位，研究函数逼近论。但这不是他的兴趣所在，因此没有获得学位。1966年在季科夫的指导下获得博士学位。和大多数数学家一样，维津在音乐方面具有一定才能。10维津在攻读博士学位期间，发现并证明了上面的维津定理。他当时把论文投向一家非常著名的杂志，但由于审稿

5、人认为问题本身没有意义而遭到拒绝。后来在另外一家地方杂志发表时，定理早已出名。维津认为：一名数学家应该不断研究与发现新结果，然后让时间来检验其重要性。11定理设G是单图。若点数n=2k+1且边数m>kΔ,则：证明：若不然，由维津定理，设п是G的Δ(G)正常边着色方案，对于G的每个色组来说，包含的边数至多(n-1)/2=k。这样：，与条件矛盾。例3确定下图的边色数。G解：由定理5：12定理6设G是奇数阶Δ正则单图,若Δ>0,则：证明：设n=2k+1。因G是Δ正则单图，且Δ>0，所以：例4设n=2k+1,k>0。求由定理5：解：由定理6知：13例5求出彼得森

6、图的边色数。解：一方面，彼得森图中去掉任意一个1因子后，剩下两个5点圈，所以，不能进行1因子分解，所以：另一方面：G的最大度数Δ=3，所以：G14例6(1)设G=(X,Y)是一个最大度为Δ的偶图，求证，G是某个Δ正则偶图G*的子图。(2)用(1)证明：偶图的边色数等于其最大度。证明(1)按如下方式构造G*。如果G不是Δ正则偶图，先将G按下图所示方式构造成为G1XXYYG(1)G(2)G115G(1)与G(2)分别是G的拷贝。红色边表示xi与xi(yi与yi)之间的一条连线，要求是d(xi)<Δ(d(yi)<Δ),这样得到的新偶图就是G1。XXYYG(1)

7、G(2)G1如果G1是Δ正则偶图，则G*=G1否则，在G1的基础上，重复上面的过程，可得到G2,这样不断下去，最终得到包含G的Δ正则偶图G*。(2)由(1)对于任意最大度为Δ的偶图G,均存在G的Δ正则母图G*。又由于正则偶图存在1因子分解，所以，G*可以划分为Δ个1因子，从而其边色数为Δ。这样G的边色数也为Δ。16（二）图的顶点着色17定义1设G是一个图，对G的每个顶点着色，使得相邻顶点着不同颜色，称为对G的正常顶点着色；如果用k种颜色可以对G进行正常顶点着色，称G可k正常顶点着色；对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图G的点色数用表示

8、。例1说明下图的点色数是4。GTMAGACLAS下列命题成立：G是有边的两分图的