第七章 图的着色 图论及其应用课件[精].ppt

Email: yc517922@
图论及其应用
任课教师:杨春
应用数学学院
1
第七章图的着色
一、图的边着色
二、图的顶点着色
主要内容
三、与色数有关的几类图和完美图
四、色多项式
五、List着色与全着色
10学时讲授本章
2
本次课主要内容
(一)、相关概念
(二)、几类特殊图的边色数
图的边着色
(三)、边着色的应用
3
现实生活中很多问题,可以模型为所谓的边着色问题来处理。例如排课表问题。
(一)、相关概念
排课表问题:设有m位教师,n个班级,其中教师xi要给班级yj上pij节课。求如何在最少节次排完所有课。
建模:令X={x1,x2,…,xm}, Y={y1,y2,…,yn},xi与yj间连pij条边,得偶图G=(X, Y).
于是,问题转化为如何在G中将边集E划分为互不相交的p个匹配,且使得p最小。
如果每个匹配中的边用同一种颜色染色,不同匹配中的边用不同颜色染色,则问题转化为在G中给每条边染色,相邻边染不同色,至少需要的颜色数。
4
这就需要我们研究所谓的边着色问题。
定义1 设G是图,对G的边进行染色,若相邻边染不同颜色,则称对G进行正常边着色;
如果能用k中颜色对图G进行正常边着色,称G是k边可着色的。
正常边着色
定义2 设G是图,对G进行正常边着色需要的最少颜色数,称为G的边色数,记为:
5
在对G正常边着色时,着相同颜色的边集称为该正常着色的一个色组。
(二)、几类特殊图的边色数
1、偶图的边色数
定理1
证明:设
又设Δ=n。设颜色集合设为{0,1,2,…,n-1}, п是Km,n的一种n着色方案,满足:
7
我们证明:上面的着色是正常边着色。
对K m, n中任意的两条邻接边xiyj和xiyk。若
则:i+ j ( mod n)=i +k ( mod n),得到j=k,矛盾!
所以,上面着色是正常作色。所以:
又显然,所以,
例1 用最少的颜色数对K3,4正常边着色。
8
定理2 (哥尼,1916)若G是偶图,则
x2
x1
x0
y3
y2
y1
y0
定义3 设п是G的一种正常边着色,若点u关联的边的着色没有用到色i,则称点u缺i色。
证明:我们对G的边数m作数学归纳。
当m=1时,Δ=1,有
9
设G是具有m条边的偶图。
设对于小于m条边的偶图来说命题成立。
取uv∈ E(G), 考虑G1=G-uv,由归纳假设有:
这说明,G1存在一种Δ(G)边着色方案п。对于该着色方案,因为uv未着色,所以点u与v均至少缺少一种色。
情形1 如果u与v均缺同一种色i, 则在G1+uv中给uv着色i, 而G1其它边,按п方案着色。这样得到G的Δ着色方案,所以:
情形2 如果u缺色i, 而v缺色j,但不缺色i。
10