图论课件第7章图的着色.ppt

图论及其应用 应用数学学院 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第七章 图的着色 一、图的边着色 二、图的顶点着色 主要内容 三、与色数有关的几类图和完美图 四、色多项式 五、List着色与全着色 10学时讲授本章 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 本次课主要内容 (一)、相关概念 (二)、几类特殊图的边色数 图的边着色 (三)、边着色的应用 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 现实生活中很多问题，可以模型为所谓的边着色问题来处理。例如排课表问题。 (一)、相关概念 排课表问题：设有m位教师，n个班级，其中教师xi要给班级yj上pij节课。求如何在最少节次排完所有课。 建模：令X=｛x1,x2,…,xm｝, Y=｛y1,y2,…,yn｝,xi与yj间连pij条边，得偶图G=(X, Y). 于是，问题转化为如何在G中将边集E划分为互不相交的p个匹配，且使得p最小。 如果每个匹配中的边用同一种颜色染色，不同匹配中的边用不同颜色染色，则问题转化为在G中给每条边染色，相邻边染不同色，至少需要的颜色数。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 这就需要我们研究所谓的边着色问题。 定义1 设G是图，对G的边进行染色，若相邻边染不同颜色，则称对G进行正常边着色； 如果能用k中颜色对图G进行正常边着色，称G是k边可着色的。 定义2 设G是图，对G进行正常边着色需要的最少颜色数，称为G的边色数，记为： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 注：对图的正常边着色，实际上是对G的边集合的一种划分，使得每个划分块是G的一个边独立集(无环时是匹配);图的边色数对应的是图的最小独立集划分数。 因此，图的边着色，本质上是对应实际问题中的“划分”问题或“分类”问题。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 在对G正常边着色时，着相同颜色的边集称为该正常着色的一个色组。 (二)、几类特殊图的边色数 1、偶图的边色数 定理1 证明：设 又设Δ=n。设颜色集合设为｛0，1，2，…，n-1｝, п是Km,n的一种n着色方案，满足： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 我们证明：上面的着色是正常边着色。 对K m, n中任意的两条邻接边xiyj和xiyk。若 则：i+ j ( mod n)=i +k ( mod n),得到j=k，矛盾！ 所以，上面着色是正常作色。所以： 又显然 ，所以， 例1 用最少的颜色数对K3,4正常边着色。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定理2 (哥尼，1916)若G是偶图，则 定义3 设п是