本次课主要内容 图的边着色 (一)、相关概念 (二)、几类特殊图的边色数 (三)、边着色的应用
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 本次课主要内容 (一)、相关概念 (二)、几类特殊图的边色数 图的边着色 (三)、边着色的应用
(一)、相关概念 现实生活中很多问题，可以模型为所谓的边着色问题 来处理。例如排课表问题。 排课表问题：设有m位教师，n个班级，其中教师x要 给班级y,上P节课。求如何在最少节次排完所有课。 建模：令X三(x1x2xm),Y={y1N2y},X与y,间 连P条边，得偶图G=(X,Y), 于是，问题转化为如何在G中将边集E划分为互不相交 的p个匹配，且使得p最小。 如果每个匹配中的边用同一种颜色染色，不同匹配中 的边用不同颜色染色，则问题转化为在G中给每条边染 色，相邻边染不同色，至少需要的颜色数
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 现实生活中很多问题，可以模型为所谓的边着色问题 来处理。例如排课表问题。 (一)、相关概念 排课表问题：设有m位教师，n个班级，其中教师xi要 给班级yj上pij节课。求如何在最少节次排完所有课。 建模：令X=｛x1,x2,…,xm｝, Y=｛y1,y2,…,yn｝,xi与yj间 连pij条边，得偶图G=(X, Y). 于是，问题转化为如何在G中将边集E划分为互不相交 的p个匹配，且使得p最小。 如果每个匹配中的边用同一种颜色染色，不同匹配中 的边用不同颜色染色，则问题转化为在G中给每条边染 色，相邻边染不同色，至少需要的颜色数
这就需要我们研究所谓的边着色问题。 定义1设G是图，对G的边进行染色，若相邻边染不同 颜色，则称对G进行正常边着色； 如果能用k种颜色对图G进行正常边着色，称G是k边 可着色的。 正常边着色 定义2设G是图，对G进行正常边着色需要的最少颜色 数，称为G的边色数，记为：z©)
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 这就需要我们研究所谓的边着色问题。 定义1 设G是图，对G的边进行染色，若相邻边染不同 颜色，则称对G进行正常边着色； 如果能用k种颜色对图G进行正常边着色，称G是k边 可着色的。 正常边着色 定义2 设G是图，对G进行正常边着色需要的最少颜色 数，称为G的边色数，记为： ( ) G
x'(G)=3 注：对图的正常边着色，实际上是对G的边集合的一 种划分，使得每个划分块是G的一个边独立集（无环时是 匹配)；图的边色数对应的是图的最小独立集划分数。 因此，图的边着色，本质上是对应实际问题中的“划 分”问题或“分类”问题。 6
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 注：对图的正常边着色，实际上是对G的边集合的一 种划分，使得每个划分块是G的一个边独立集(无环时是 匹配);图的边色数对应的是图的最小独立集划分数。 () 3 G 因此，图的边着色，本质上是对应实际问题中的“划 分”问题或“分类”问题
在对G正常边着色时，着相同颜色的边集称为该正常 着色的一个色组。 (二)、几类特殊图的边色数 1、偶图的边色数 定理1 X(Kmn)=△ 证明：设 X={xo,x,,xm-} Y=oys..n1 又设△=n。设颜色集合为{0,1,2，…， n-1),Π是 Kn的一种n着色方案，满足： Vx,y,∈E(Km.m),π(x,y,)=(i+j)(modn)
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 在对G正常边着色时，着相同颜色的边集称为该正常 着色的一个色组。 (二)、几类特殊图的边色数 1、偶图的边色数 定理1 , ( ) K m n 证明：设 01 1 , ,..., X xx x m 01 1 , ,..., Y yy y n 又设Δ=n。设颜色集合为｛0，1，2，…，n-1｝, п是 Km,n的一种n着色方案，满足： , ( ), ( ) ( )(mod ) i j mn i j x y EK x y i j n