图论第七章 图的着色精品文稿.ppt

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

1、图论课件第七章 图的着色1 1第1页，本讲稿共31页第七章第七章 图的着色图的着色一、图的边着色一、图的边着色二、图的顶点着色二、图的顶点着色主要内容主要内容三、与色数有关的几类图和完美图三、与色数有关的几类图和完美图四、色多项式四、色多项式五、五、List着色与全着色着色与全着色10学时讲授本章学时讲授本章2第2页，本讲稿共31页本次课主要内容本次课主要内容(一一)、相关概念、相关概念(二二)、几类特殊图的边色数、几类特殊图的边色数图的边着色图的边着色(三三)、边着色的应用、边着色的应用3第3页，本讲稿共31页 现实生活中很多问题，可以模型为所谓的边着色问题现实生活中很多问题，可以模型为所谓

2、的边着色问题来处理。例如排课表问题。来处理。例如排课表问题。(一一)、相关概念、相关概念 排课表问题：设有排课表问题：设有m位教师，位教师，n个班级，其中教师个班级，其中教师xi要要给班级给班级yj上上pij节课。求如何在最少节次排完所有课。节课。求如何在最少节次排完所有课。建模：令建模：令X=x1,x2,xm,Y=y1,y2,yn,xi与与yj间间连连pij条边，得偶图条边，得偶图G=(X,Y).于是，问题转化为如何在于是，问题转化为如何在G中将边集中将边集E划分为互不相交划分为互不相交的的p个匹配，且使得个匹配，且使得p最小。最小。如果每个匹配中的边用同一种颜色染色，不同匹配中如果每个匹配

3、中的边用同一种颜色染色，不同匹配中的边用不同颜色染色，则问题转化为在的边用不同颜色染色，则问题转化为在G中给每条边染色，中给每条边染色，相邻边染不同色，至少需要的颜色数。相邻边染不同色，至少需要的颜色数。4第4页，本讲稿共31页 这就需要我们研究所谓的边着色问题。这就需要我们研究所谓的边着色问题。定义定义1 设设G是图，对是图，对G的边进行染色，若相邻边染不同的边进行染色，若相邻边染不同颜色，则称对颜色，则称对G进行正常边着色；进行正常边着色；如果能用如果能用k中颜色对图中颜色对图G进行正常边着色，称进行正常边着色，称G是是k边边可着色的。可着色的。正常边着色正常边着色 定义定义2 设设G是图

4、，对是图，对G进行正常边着色需要的最少颜色进行正常边着色需要的最少颜色数，称为数，称为G的边色数，记为：的边色数，记为：5第5页，本讲稿共31页 注：对图的正常边着色，实际上是对注：对图的正常边着色，实际上是对G的边集合的一的边集合的一种划分，使得每个划分块是种划分，使得每个划分块是G的一个边独立集的一个边独立集(无环时是无环时是匹配匹配);图的边色数对应的是图的最小独立集划分数。图的边色数对应的是图的最小独立集划分数。因此，图的边着色，本质上是对应实际问题中的因此，图的边着色，本质上是对应实际问题中的“划划分分”问题或问题或“分类分类”问题。问题。6第6页，本讲稿共31页 在对在对G正常边着

5、色时，着相同颜色的边集称为该正常正常边着色时，着相同颜色的边集称为该正常着色的一个色组。着色的一个色组。(二二)、几类特殊图的边色数、几类特殊图的边色数 1、偶图的边色数、偶图的边色数 定理定理1 证明：设证明：设 又设又设=n=n。设颜色集合设为。设颜色集合设为0，1，2，n-1,是是K Km,nm,n的一种的一种n n着色方案，满足：着色方案，满足：7第7页，本讲稿共31页 我们证明：上面的着色是正常边着色。我们证明：上面的着色是正常边着色。对对K m,n中任意的两条邻接边中任意的两条邻接边xiyj和和xiyk。若。若 则：则：i+j(mod n)=i+k(mod n),得到得到j=k，矛

6、盾！，矛盾！所以，上面着色是正常作色。所以：所以，上面着色是正常作色。所以：又显然又显然 ，所以，所以，例例1 用最少的颜色数对用最少的颜色数对K3,4正常边着色。正常边着色。8第8页，本讲稿共31页 定理定理2(哥尼，哥尼，1916)若若G是偶图，则是偶图，则x2x1x0y3y2y1y0 定义定义3 设设是是G G的一种正常边着色，若点的一种正常边着色，若点u u关联的边的关联的边的着色没有用到色着色没有用到色i i，则称点，则称点u u缺缺i i色。色。证明：我们对证明：我们对G的边数的边数m作数学归纳。作数学归纳。当当m=1时，时，=1=1，有，有9第9页，本讲稿共31页 设设G是具有是

7、具有m条边的偶图。条边的偶图。设对于小于设对于小于m条边的偶图来说命题成立。条边的偶图来说命题成立。取取uv E(G),考虑考虑G1=G-uv,由归纳假设有：由归纳假设有：这说明，这说明，G1存在一种存在一种(G)(G)边着色方案边着色方案。对于该着色。对于该着色方案，因为方案，因为uvuv未着色，所以点未着色，所以点u u与与v v均至少缺少一种色。均至少缺少一种色。情形情形1 如果如果u与与v均缺同一种色均缺同一种色i,则在则在G1+uv中给中给uv着色着色i,而而G1其它边，按其它边，按方案着色。这样得到方案着色。这样得到G G的的着色方案，着色方案，所以：所以：情形情形2 如果如果u缺

8、色缺色i,而而v缺色缺色j，但不缺色，但不缺色i。10第10页，本讲稿共31页 设设H(i,j)表示表示G1中由中由i色边与色边与j色边导出的子图。显然，色边导出的子图。显然，该图每个分支是该图每个分支是i色边和色边和j色边交替出现的路或圈。色边交替出现的路或圈。对于对于H(i,j)中含点中含点v的分支来说，因的分支来说，因v缺色缺色j,但不缺色但不缺色i,所以，在所以，在H(i,j)中中,点点v的度数为的度数为1。这说明，。这说明，H(i,j)中含中含v的的分支是一条路分支是一条路P。进一步地，我们可以说明，上面的路进一步地，我们可以说明，上面的路P不含点不含点u。因为，如果因为，如果P含有

9、点含有点u,那么那么P必然是一条长度为偶数的必然是一条长度为偶数的路，这样，路，这样，P+uv是是G中的奇圈，这与中的奇圈，这与G是偶图矛盾！是偶图矛盾！既然既然P不含点不含点u,所以我们可以交换所以我们可以交换P中着色，而不破坏中着色，而不破坏G1的正常边着色。但交换着色后，的正常边着色。但交换着色后，u与与v均缺色均缺色i,于是由于是由情形情形1,可以得到可以得到G的的正常边着色，即证明：正常边着色，即证明：11第11页，本讲稿共31页 2、简单图的边色数、简单图的边色数 引理：设引理：设G是简单图，是简单图，x与与y1是是G中不相邻的两个顶点，中不相邻的两个顶点，是是G G的一个正常的一

10、个正常k k边着色。若对该着色边着色。若对该着色，x,yx,y1 1以及与以及与x x相邻点相邻点均至少缺少一种颜色，则均至少缺少一种颜色，则G+xyG+xy1 1是是k k边可着色的。边可着色的。正常正常k边着色图边着色图Gx1y1xx2xk缺色缺色缺色缺色缺色缺色缺色缺色缺色缺色正常正常k边着色图边着色图G1x1y1xx2xk12第12页，本讲稿共31页 定理定理3(维津定理，维津定理，1964)若若G是单图，则：是单图，则：证明：只需要证明证明：只需要证明 即可。即可。采用对采用对G的边数的边数m作数学归纳证明。作数学归纳证明。当当m=1时，时，=1=1，设当边数少于设当边数少于m时，结

11、论成立。下面考虑边数为时，结论成立。下面考虑边数为m2的的单图单图G。设设xy E(G)，令，令G1=G-xy。由归纳假设有：。由归纳假设有：13第13页，本讲稿共31页 于是，存在于是，存在G1的的(G)+1(G)+1正常边作色正常边作色。显然。显然G G1 1的每个顶的每个顶点都至少缺少一种颜色。根据引理知点都至少缺少一种颜色。根据引理知G G1 1+xy+xy是是(G)+1可着色可着色的。即证明：的。即证明：注注:(1)根据维津定理，单图可以按边色数分成两类图，一根据维津定理，单图可以按边色数分成两类图，一是色数等于是色数等于(G)的单图，二是色数等于的单图，二是色数等于(G)+1的单图

12、。的单图。(2)维津维津(Vizing):1937年出生于乌克兰的基辅。年出生于乌克兰的基辅。1954年年开始在托木斯克大学学习数学，开始在托木斯克大学学习数学，1959年大学毕业保送到莫年大学毕业保送到莫斯科斯特克罗夫研究所攻读博士学位，研究函数逼近论。斯科斯特克罗夫研究所攻读博士学位，研究函数逼近论。但这不是他的兴趣所在，因此没有获得学位。但这不是他的兴趣所在，因此没有获得学位。1966年在季年在季科夫的指导下获得博士学位。和大多数数学家一样，维津科夫的指导下获得博士学位。和大多数数学家一样，维津在音乐方面具有一定才能。在音乐方面具有一定才能。14第14页，本讲稿共31页 维津在攻读博士学

13、位期间，发现并证明了上面的维津维津在攻读博士学位期间，发现并证明了上面的维津定理。他当时把论文投向一家非常著名的杂志，但由于定理。他当时把论文投向一家非常著名的杂志，但由于审稿人认为问题本身没有意义而遭到拒绝。后来在另外审稿人认为问题本身没有意义而遭到拒绝。后来在另外一家地方杂志发表时，定理早已出名。一家地方杂志发表时，定理早已出名。维津认为：一名数学家应该不断研究与发现新结果，然维津认为：一名数学家应该不断研究与发现新结果，然后让时间来检验其重要性。后让时间来检验其重要性。3、三类特殊简单图的边色数、三类特殊简单图的边色数 定理定理4 设设G是单图且是单图且(G)0(G)0。若。若G G中只

14、有一个最大度点中只有一个最大度点或恰有两个相邻的最大度点，则：或恰有两个相邻的最大度点，则：15第15页，本讲稿共31页 证明证明:(1)若单图若单图G恰有一个最大度点恰有一个最大度点u，取，取u的一个邻点的一个邻点v,作作G1=G-uv。那么，那么，(G(G1 1)=)=(G)-1(G)-1。由维津定理：。由维津定理：于是于是G1是可是可(G)正常边着色的，因为正常边着色的，因为G1的每个顶点都的每个顶点都至少缺少一种颜色，所以由引理：至少缺少一种颜色，所以由引理：G1+uv=G是可是可(G)正常正常边着色的，即：边着色的，即：(2)若单图若单图G恰有恰有2个邻接的最大度点个邻接的最大度点u

15、与与v。设。设G1=G-uv。那么，那么，(G(G1 1)=)=(G)-1(G)-1。由维津定理：。由维津定理：16第16页，本讲稿共31页 于是于是G1是可是可(G)正常边着色的，因为正常边着色的，因为G1的每个顶点都的每个顶点都至少缺少一种颜色，所以由引理：至少缺少一种颜色，所以由引理：G1+uv=G是可是可(G)正常正常边着色的，即：边着色的，即：例例2 确定下图的边色数。确定下图的边色数。G1G2 解：由定理解：由定理4知道：知道：G317第17页，本讲稿共31页 定理定理5 设设G是单图。若点数是单图。若点数n=2k+1且边数且边数mk,则：则：证明：若不然，由维津定理，证明：若不然

16、，由维津定理，设设是是G G的的(G)(G)正常边着色方案，对于正常边着色方案，对于G G的每个色组来的每个色组来说，包含的边数至多说，包含的边数至多(n-1)/2=k(n-1)/2=k。这样：。这样：，与，与条件矛盾。条件矛盾。例例3 确定下图的边色数。确定下图的边色数。G 解：由定理解：由定理5：18第18页，本讲稿共31页 定理定理6 设设G是奇数阶是奇数阶正则正则单图单图,若若0,0,则：则：证明：设证明：设n=2k+1。因。因G是是正则单图，且正则单图，且0，所以：，所以：例例4 设设n=2k+1,k0。求。求 由定理由定理5：解：由定理解：由定理6知：知：19第19页，本讲稿共31

17、页 例例5 求出彼得森图的边色数。求出彼得森图的边色数。解：一方面，彼得森图中去掉任意一个解：一方面，彼得森图中去掉任意一个1因子后，剩因子后，剩下两个下两个5点圈，所以，不能进行点圈，所以，不能进行1因子分解，所以：因子分解，所以：另一方面：通过验证，另一方面：通过验证，G可以可以4正常作色。所以：正常作色。所以：G20第20页，本讲稿共31页 例例6(1)设设G=(X,Y)是一个最大度为是一个最大度为的偶图，求证，的偶图，求证，G G是某个是某个正则偶图正则偶图 G G*的子图。的子图。(2)用用(1)证明：偶图的边色数等于其最大度。证明：偶图的边色数等于其最大度。证明证明(1)按如下方式

18、构造按如下方式构造G*。如果如果G不是不是正则偶图，先将正则偶图，先将G按下图所示方式构造按下图所示方式构造成为成为G1XXYYG(1)G(2)G121第21页，本讲稿共31页 G(1)与与G(2)分别是分别是G的拷贝。的拷贝。红色红色 边表示边表示xi与与xi(yi与与yi)之间的一条连线，之间的一条连线，要求是要求是d(xi)(d(y(d(yi i)3m=1635=k,所以由所以由定理定理5 5知：知：28第28页，本讲稿共31页 最优着色为：最优着色为：FDAGCEB图图G29第29页，本讲稿共31页 作业作业 P187-190 习题习题7：1-630第30页，本讲稿共31页Thank You!31第31页，本讲稿共31页