1、1/图的着色/一、图的边着色/二、图的顶点着色/主要内容/2/现实生活中很多问题，可以模型为所谓的边着色问题来处理。例如排课表问题。/(一)、边着色/排课表问题：设有m位教师，n个班级，其中教师xi要给班级yj上pij节课。求如何在最少节次排完所有课。/建模：令X=x1/x2/xm/ Y=y1/y2/yn/xi与yj间连pij条边，得偶图G=(X/ Y)//于是，问题转化为如何在G中将边集E划分为互不相交的p个匹配，且使得p最小。/如果每个匹配中的边用同一种颜色染色，不同匹配中的边用不同颜色染色，则问题转化为在G中给每条边染色，相邻边染不同色，至少需要的颜色数。/3/这就需要我们研究所谓的边着
2、色问题。/定义1 设G是图，对G的边进行染色，若相邻边染不同颜色，则称对G进行正常边着色；/如果能用k中颜色对图G进行正常边着色，称G是k边可着色的。/定义2 设G是图，对G进行正常边着色需要的最少颜色数，称为G的边色数，记为：/4/注：对图的正常边着色，实际上是对G的边***的一种划分，使得每个划分块是G的一个边***集(无环时是匹配)/图的边色数对应的是图的最少***集划分数。/因此，图的边着色，本质上是对应实际问题中的“划分”问题或“分类”问题。/5/(二)、几类特殊图的边色数/1、偶图的边色数/定理1/证明：设/又设=n。设颜色***设为0，1，2，n-1/ 是Km/n的一种n着色方案，满足：
3、/6/我们证明：上面的着色是正常边着色。/对K m/ n中任意的两条邻接边xiyj和xiyk。若/则：i+ j ( mod n)=i +k ( mod n)/得到j=k，矛盾！/所以，上面着色是正常着色。所以：/又显然 ，所以，/例1 用最少的颜色数对K3/4正常边着色。/7/定理2 (哥尼，1916)若G是偶图，则/8/定理3 (维津定理，1964) 若G是单图，则：/注： 根据这个定理， 如果我们要证明某一个图的边染色数是， 只要我们找到了一种染色方式用的色数是就可以了。 如果要证明是 +1， 我们只需要证明用色不能正常染色。一般用反证法， 假设能用 染色， 得到矛盾。/9/注/ (1)
4、根据维津定理，单图可以按边色数分成两类图，一是色数等于(G)的单图，二是色数等于(G)+1的单图。/(2) 维津(Vizing) / 1937年出生于乌克兰的基辅。1954年开始在托木斯克大学学习数学，1959年大学毕业保送到莫斯科斯特克罗夫研究所攻读博士学位，研究函数逼近论。但这不是他的兴趣所在，因此没有获得学位。1966年在季科夫的指导下获得博士学位。和大多数数学家一样，维津在音乐方***有一定才能。/10/维津在攻读博士学位期间，发现并证明了上面的维津定理。他当时把论文投向一家非常著名的杂志，但由于审稿人认为问题本身没有意义而遭到拒绝。后来在另外一家地方杂志发表时，定理早已出名。/维津认为
5、：一名数学家应该不断研究与发现新结果，然后让时间来检验其重要性。/11/定理 设G是单图。若点数n=2k+1且边数mk/则：/证明：若不然，由维津定理，/设是G的(G)正常边着色方案，对于G的每个色组来说，包含的边数至多(n-1)/2=k。这样： ，与条件矛盾。/例3 确定下图的边色数。/解：由定理5：/12/定理6 设G是奇数阶正则单图/若0/则：/证明：设n=2k+1。因G是正则单图，且0，所以：/例4 设n=2k+1/k0。求/由定理5：/解：由定理6知：/13/例5 求出彼得森图的边色数。/解：一方面，彼得森图中去掉任意一个1因子后，剩下两个5点圈，所以，不能进行1因子分解，所以：/另
6、一方面：G的最大度数 =3， 所以：/14/例6 (1) 设G=(X/ Y)是一个最大度为的偶图，求证，G是某个正则偶图 G*的子图。/(2) 用(1) 证明：偶图的边色数等于其最大度。/证明 (1) 按如下方式构造G*。/如果G不是正则偶图，先将G按下图所示方式构造成为G1/15/G (1)与G (2)分别是G的拷贝。/红色 边表示xi与xi(yi与yi)之间的一条连线，要求是d(xi)(d(yi)/这样得到的新偶图就是G1。/如果G1是正则偶图，则G*=G1/否则，在G1的基础上，重复上面的过程，可得到G2/这样不断下去，最终得到包含G的正则偶图G*。/(2) 由(1) 对于任意最大度为的
7、偶图G/均存在G的正则母图G*。又由于正则偶图存在1因子分解，所以，G*可以划分为个1因子，从而其边色数为。这样G的边色数也为。/16/（二） 图的顶点着色/17/定义1 设G是一个图，对G的每个顶点着色，使得相邻顶点着不同颜色，称为对G的正常顶点着色；/如果用k种颜色可以对G进行正常顶点着色，称G可k正常顶点着色；/对图G正常顶点着色需要的最少颜色数，称为图G的***数。图G的***数用 表示。/例1 说明下图的***数是4。/下列命题成立：/G是有边的两分图的充要条件是=2 G是无边图的充要条件是=1 G是完全图的充要条件是=|V(G)| (轮）=3 （轮的顶点数是奇数）； 4（否则）/定理/对
8、任意的图G 均有/顶点着色/定理/设G是连通图。假定G既不是完全图又不是奇圈，则/一个着色算法/Welsh-Powell算法/顶点着色/（1）将图G的节点按度数递减排列； （2）对第一个节点及其不邻接的节点着第一个颜色； （3）对常未着色的第一个及其不邻接的节点着第二个颜色；续行此法， 直到全部节点着色完为止。/用Welsh-Powell算法对下例中的点着色，结果如下图所示。/顶点着色/22/1、四色定理/(三)、四色与五色定理/1852年，刚毕业于伦敦大学的格斯里(18311899)发现：给一张平面地图正常着色，至少需要4种颜色。这就是著名的4色定理。/格斯里把他的证明通过他弟弟转交给著名数
9、学家摩尔根，引起摩尔根极大兴趣并于当天给数学家哈密尔顿写了封相关信件。但没有引起哈密尔顿的注意。/直到1878年，在英国数学会议上，数学家凯莱才再一次提到4色问题。/23/1879年7月，业余数学家肯普(1849-1922）在英国自然杂志上宣称证明了4色定理。肯普是凯莱在剑桥大学的学生。/1890年，英国数学家希五德发表文章地图染色定理，通过构***例，指出了肯普证明中的***。后来，西五德一直研究4色问题60年。/泰特在此期间也研究4色问题，但其证明被托特否定。/希五德文章之后，4色问题研究进程开始走向停滞。/到了20世纪，美国数学家比尔荷夫提出可约性概念，在此基础上，德国数学家Heesch(1
10、9061995)认为，可以通过寻找所谓的不可约构形来证明4色定理。/24/Heesch估计不可约构形***可能包含10000个元素，手工验证是不太可能。于是他给出了一种可用计算机来验证的方法。/20世纪70年代，Haken和他的学生Appel着力用计算机方法证明4色定理，借助于Appel在编程方面的深厚功底。他们于1976年6月终于成功解决了寻找不可约构形***中的元素，宣告4色定理的成功证明。数学家托特在图论***刊物图论杂志上写了一首诗：/Wolfgang Haken/重重打击着巨妖/一次！两次！三次！四次！/他说：“妖怪已经不存在了/”/25/2、五色定理/定理4 (希五德) 每个平面图是5可
11、着色的。/根据平面图和其对偶图的关系，上面定理等价于每个平面图是5可顶点正常着色的。/证明：我们对图的顶点作数学归纳证明。 （不做要求）/当n=1时，结论显然。/设n=k时，结论成立。考虑n=k+1的平面图G。/因G是平面图，所以(G)5/设d(u)=(G)5。/26/令G1=G u。由归纳假设，G1是5可顶点正常着色的。设是G1的5着色方案。/(1) 如果d(u)=(G)5/ 显然可以扩充为G的5正常顶点着色；/(2) 如果d(u)=(G) = 5/ 分两种情况讨论。/情形1 在下，如果u的邻接点中，至少有两个顶点着相同颜色，则容易知道，可以扩充为G的5正常顶点着色；/情形2 在下，设u的邻接点中，5个顶点着了5种不同颜色。/27/不失一般性，设(xi)=i (1i5)。/设H (i/ j)表示着i和j色的点在G1中的点导出子图。/如果x1与x3属于H(1/ 3
郑重声明：
1. 《new-图着色》内容来源于互联网，版权归原著者或相关公司所有。
2. 若《86561825文库网》收录的文本内容侵犯了您的权益或隐私，请立即通知我们删除。