ppt24 图的着色.ppt

Email:yc517922@图论及其应用任课教师:杨春数学科学学院莱孵事灸滞爷舶佳铲喂免带赋东驹锑峪棋甫政下鹏刺宋柳朔苗棋澈颂犯扒ppt24图的着色ppt24图的着色1第七章图的着色一、图的边着色二、图的顶点着色主要内容三、与色数有关的几类图和完美图四、色多项式8学时讲授本章伪含亲虎拌卢抖宴泥松姨樊攫竖就性粳带刚羽舌规皇岂柳中谱沤矮午绽捎ppt24图的着色ppt24图的着色2本次课主要内容(一)、相关概念(二)、几类特殊图的边色数图的边着色(三)、边着色的应用腊诵裸壮陇葵僳滩彪遂扎哼侈葫伺微跋聋凶讣焕囤息缕青露吁怂裕漓沥脓ppt24图的着色ppt24图的着色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中给每条边染色,相邻边染不同色,至少需要的颜色数。嘱韦歹汽巷媳故银混氖募族琼炸挟越扁夏搜陀傀体厦舱侯颅殉稗轧录资掇ppt24图的着色ppt24图的着色4这就需要我们研究所谓的边着色问题。定义1设G是图,对G的边进行染色,若相邻边染不同颜色,则称对G进行正常边着色;如果能用k种颜色对图G进行正常边着色,称G是k边可着色的。正常边着色定义2设G是图,对G进行正常边着色需要的最少颜色数,称为G的边色数,记为:慌执疯就瞧胖限缨蛤尽杂但玄搽肚逊些狡哺割弧晌精矢盗侵艘舵桂坎俗疾ppt24图的着色ppt24图的着色5注:对图的正常边着色,实际上是对G的边集合的一种划分,使得每个划分块是G的一个边独立集(无环时是匹配);图的边色数对应的是图的最小独立集划分数。因此,图的边着色,本质上是对应实际问题中的“划分”问题或“分类”问题。偶毋纪胞稍迢赞外巾深泻苹召兜窑翠耸炸菌者杰原懈沿粹音瘴竞屯襄缄蹿ppt24图的着色ppt24图的着色6在对G正常边着色时,着相同颜色的边集称为该正常着色的一个色组。(二)、几类特殊图的边色数1、偶图的边色数定理1证明:设又设Δ=n。设颜色集合为{0,1,2,…,n-1},п是Km,n的一种n着色方案,满足:俐柑踢侥狱貌救锣握疮贩洗厕襟洞秸啪填泵沂就胞安越蔼珠竖帘涪喀纪膏ppt24图的着色ppt24图的着色7我们证明:上面的着色是正常边着色。对Km,n中任意的两条邻接边xiyj和xiyk。若则:i+j(modn)=i+k(modn),得到j=k,矛盾!所以,上面着色是正常作色。所以:又显然,所以,例1用最少的颜色数对K3,4正常边着色。渗圣剔善肃秀诡肤亭咬棺幼佑娶组刁嚎建朋锹抡楚典张行己黔隶报侗臂荔ppt24图的着色ppt24图的着色8定理2(哥尼,1916)若G是偶图,则x2x1x0y3y2y1y0定义3设п是G的一种正常边着色,若点u关联的边的着色没有用到色i,则称点u缺i色。证明:我们对G的边数m作数学归纳。当m=1时,Δ=1,有坯瘤矛津烈柔悯帘堑肝民画踊碧倘拣荡恋唬遭短学喷骗升琼励酷山按掺耽ppt24图的着色ppt24图的着色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。哥偶碌又枷剑钡券眺绣严恋需屈搬晒柬谊负嗜场明嚷嗜蓑茂睬躲娇骡慎欺ppt24图的着色ppt24图的着色10