图论课件第七章图的着色

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论及其应用,应用数学学院,1,第七章 图的着色,一、图的边着色,二、图的顶点着色,主要内容,三、与色数有关的几类图和完美图,四、色多项式,五、,List,着色与全着色,10,学时讲授本章,2,本次课主要内容,(,一,),、相关概念,(,二,),、几类特殊图的边色数,图的边着色,(,三,),、边着色的应用,3,现实生活中很多问题，可以模型为所谓的边着色问题来处理。例如排课表问题。,(,一,),、相关概念,排课表问题：设有,m,位教师，,n,个班级，其中教师,x,i,要给班级,y,j,上,p,ij,节课。求如何在最少节次排完所有课。,建模：令,X=,x,1,x,2,x,m,Y=,y,1,y,2,y,n,x,i,与,y,j,间连,p,ij,条边，得偶图,G=(X,Y).,于是，问题转化为如何在,G,中将边集,E,划分为互不相交的,p,个匹配，且使得,p,最小。,如果每个匹配中的边用同一种颜色染色，不同匹配中的边用不同颜色染色，则问题转化为在,G,中给每条边染色，相邻边染不同色，至少需要的颜色数。,4,这就需要我们研究所谓的边着色问题。,定义,1,设,G,是图，对,G,的边进行染色，若相邻边染不同颜色，则称对,G,进行正常边着色；,如果能用,k,中颜色对图,G,进行正常边着色，称,G,是,k,边可着色的。,正常边着色,定义,2,设,G,是图，对,G,进行正常边着色需要的最少颜色数，称为,G,的边色数，记为：,5,注：对图的正常边着色，实际上是对,G,的边集合的一种划分，使得每个划分块是,G,的一个边独立集,(,无环时是匹配,);,图的边色数对应的是图的最小独立集划分数。,因此，图的边着色，本质上是对应实际问题中的“划分”问题或“分类”问题。,6,在对,G,正常边着色时，着相同颜色的边集称为该正常着色的一个色组。,(,二,),、几类特殊图的边色数,1,、偶图的边色数,定理,1,证明：设,又设,=n,。设颜色集合设为,0,，,1,，,2,，,，,n-1,是,K,m,n,的一种,n,着色方案，满足：,7,我们证明：上面的着色是正常边着色。,对,K,m,n,中任意的两条邻接边,x,i,y,j,和,x,i,y,k,。若,则：,i+j(mod n)=i+k(mod n),得到,j=k,，矛盾！,所以，上面着色是正常作色。所以：,又显然 ，所以，,例,1,用最少的颜色数对,K,3,4,正常边着色。,8,定理,2(,哥尼，,1916),若,G,是偶图，则,x,2,x,1,x,0,y,3,y,2,y,1,y,0,定义,3,设,是,G,的一种正常边着色，若点,u,关联的边的着色没有用到色,i,，则称点,u,缺,i,色。,证明：我们对,G,的边数,m,作数学归纳。,当,m=1,时，,=1,，有,9,设,G,是具有,m,条边的偶图。,设对于小于,m,条边的偶图来说命题成立。,取,uv E(G),考虑,G,1,=G-uv,由归纳假设有：,这说明，,G,1,存在一种,(G),边着色方案,。对于该着色方案，因为,uv,未着色，所以点,u,与,v,均至少缺少一种色。,情形,1,如果,u,与,v,均缺同一种色,i,则在,G,1,+uv,中给,uv,着色,i,而,G,1,其它边，按,方案着色。这样得到,G,的,着色方案，所以：,情形,2,如果,u,缺色,i,而,v,缺色,j,，但不缺色,i,。,10,设,H(i,j),表示,G,1,中由,i,色边与,j,色边导出的子图。显然，该图每个分支是,i,色边和,j,色边交替出现的路或圈。,对于,H(i,j),中含点,v,的分支来说，因,v,缺色,j,但不缺色,i,所以，在,H(i,j),中,点,v,的度数为,1,。这说明，,H(i,j),中含,v,的分支是一条路,P,。,进一步地，我们可以说明，上面的路,P,不含点,u,。,因为，如果,P,含有点,u,那么,P,必然是一条长度为偶数的路，这样，,P+uv,是,G,中的奇圈，这与,G,是偶图矛盾！,既然,P,不含点,u,所以我们可以交换,P,中着色，而不破坏,G,1,的正常边着色。但交换着色后，,u,与,v,均缺色,i,于是由情形,1,可以得到,G,的,正常边着色，即证明：,11,2,、简单图的边色数,引理：设,G,是简单图，,x,与,y,1,是,G,中不相邻的两个顶点，,是,G,的一个正常,k,边着色。若对该着色,，,x,y,1,以及与,x,相邻点均至少缺少一种颜色，则,G+xy,1,是,k,边可着色的。,正常,k,边着色图,G,x,1,y,1,x,x,2,x,k,缺色,缺色,缺色,缺色,缺色,正常,k,边着色图,G,1,x,1,y,1,x,x,2,x,k,12,定理,3(,维津定理，,1964),若,G,是单图，则：,证明：只需要证明 即可。,采用对,G,的边数,m,作数学归纳证明。,当,m=1,时，,=1,，,设当边数少于,m,时，结论成立。下面考虑边数为,m,2,的单图,G,。,设,xy E(G),，令,G,1,=G-xy,。由归纳假设有：,13,于是，存在,G,1,的,(G)+1,正常边作色,。显然,G,1,的每个顶点都至少缺少一种颜色。根据引理知,G,1,+xy,是,(G)+1,可着色的。即证明：,注,:(1),根据维津定理，单图可以按边色数分成两类图，一是色数等于,(G),的单图，二是色数等于,(G)+1,的单图。,(2),维津,(Vizing):1937,年出生于乌克兰的基辅。,1954,年开始在托木斯克大学学习数学，,1959,年大学毕业保送到莫斯科斯特克罗夫研究所攻读博士学位，研究函数逼近论。但这不是他的兴趣所在，因此没有获得学位。,1966,年在季科夫的指导下获得博士学位。和大多数数学家一样，维津在音乐方面具有一定才能。,14,维津在攻读博士学位期间，发现并证明了上面的维津定理。他当时把论文投向一家非常著名的杂志，但由于审稿人认为问题本身没有意义而遭到拒绝。后来在另外一家地方杂志发表时，定理早已出名。,维津认为：一名数学家应该不断研究与发现新结果，然后让时间来检验其重要性。,3,、三类特殊简单图的边色数,定理,4,设,G,是单图且,(G)0,。若,G,中只有一个最大度点或恰有两个相邻的最大度点，则：,15,证明,:(1),若单图,G,恰有一个最大度点,u,，取,u,的一个邻点,v,作,G,1,=G-uv,。,那么，,(G,1,)=,(G)-1,。由维津定理：,于是,G,1,是可,(G),正常边着色的，因为,G,1,的每个顶点都至少缺少一种颜色，所以由引理：,G,1,+uv=G,是可,(G),正常边着色的，即：,(2),若单图,G,恰有,2,个邻接的最大度点,u,与,v,。设,G,1,=G-uv,。,那么，,(G,1,)=,(G)-1,。由维津定理：,16,于是,G,1,是可,(G),正常边着色的，因为,G,1,的每个顶点都至少缺少一种颜色，所以由引理：,G,1,+uv=G,是可,(G),正常边着色的，即：,例,2,确定下图的边色数。,G,1,G,2,解：由定理,4,知道：,G,3,17,定理,5,设,G,是单图。若点数,n=2k+1,且边数,mk,则：,证明：若不然，由维津定理，,设,是,G,的,(G),正常边着色方案，对于,G,的每个色组来说，包含的边数至多,(n-1)/2=k,。这样：，与条件矛盾。,例,3,确定下图的边色数。,G,解：由定理,5,：,18,定理,6,设,G,是奇数阶,正则,单图,若,0,则：,证明：设,n=2k+1,。因,G,是,正则单图，且,0,，所以：,例,4,设,n=2k+1,k0,。求,由定理,5,：,解：由定理,6,知：,19,例,5,求出彼得森图的边色数。,解：一方面，彼得森图中去掉任意一个,1,因子后，剩下两个,5,点圈，所以，不能进行,1,因子分解，所以：,另一方面：通过验证，,G,可以,4,正常作色。所以：,G,20,例,6(1),设,G=(X,Y),是一个最大度为,的偶图，求证，,G,是某个,正则偶图,G,*,的子图。,(2),用,(1),证明：偶图的边色数等于其最大度。,证明,(1),按如下方式构造,G,*,。,如果,G,不是,正则偶图，先将,G,按下图所示方式构造成为,G,1,X,X,Y,Y,G,(1),G,(2),G,1,21,G,(1),与,G,(2),分别是,G,的拷贝。,红色 边表示,x,i,与,x,i,(y,i,与,y,i,),之间的一条连线，要求是,d(x,i,),(d(y,i,)3,5=k,所以由定理,5,知：,28,最优着色为：,F,D,A,G,C,E,B,图,G,29,作业,P187-190,习题,7,：,1-6,30,Thank You!,31,