10二部图与染色

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,图着色,四色定理,k-(,点,面,边,),着色,k-(,点,面,边,),色图,点色数,(G),面色数,*,(G),边,色数,(G),五色定理,2,四色问题,(Four Color Problem),1852,Francis Guthrie,注意到英格兰地图可以用,4,种颜色染色,使得相邻区域,(,有一段公共边界,不只是有一个公共点,),有不同颜色,;,他问其弟,Frederick,是否任意地图都有此性质,?Frederick Guthrie,DeMorgan,Hamilton,.,1878,Cayley,提交伦敦数学会,.,3,四色问题,(Four Color Problem),4,四色问题,(Four Color Problem),1879,Kempe,第一次,“,证明,”,1880,Tait,另一个,“,证明,”,1890,Heawood,发现,Kempe,证明的错误,1891,Petersen,发现,Tait,证明的漏洞,(Tait,猜想,),1946,Tutte,发现,Tait,证明的错误,(Tait,猜想反例,),5,四色问题,(Four Color Problem),1913,Birkhoff,一个大贡献,1922,Franklin,证明不超过,22,个区域的地图四色猜想成立,1950,不超过,35,个区域,1960,不超过,39,个区域,其他人取得其他形式进展,:1974,52,区域,6,四色问题,(Four Color Problem),1936-50,Heesch,最终解决问题的两个要素,:10000,个情形,100,年,约化,(reducibility),放电,(discharging).,1972-76,Appel,Haken,1482,个情形,IBM360,1200,小时,论文,139,页,+400,页程序,conjectureagnogramstheorem,7,四色问题,(Four Color Problem),8,四色定理的意义,“,四色问题,”,的被证明仅解决了一个历时,100,多年的难题，而且成为数学史上一系列新思维的起点。在,“,四色问题,”,的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，,“,四色问题,”,在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。,9,着色的应用意义,在有冲突的情况下分配资源时：,有,n,项工作（或课程），有些工作需要同样的人员或设备不能同时进行（或有同一人选课），问需要几天才能完成所有的工作（如何安排教室、课程）？,10,着色,(coloring),着色,:,给图的某类元素,(,点,边,面,),中每个指定,1,种颜色,使得相邻元素有不同颜色,(,点,),着色,边着色,面着色,:X=V(,无环,),E,R,相邻,:V,有边相连,(x,y)E;E,有公共端点,(x,y),(y,z);R,有公共边界,11,着色,(,例,),12,着色,(coloring),用颜色集,C,给,X,中顶点（边、面）着色,:,f:XC,xy(x,yXx,与,y,相邻,f(x),f(y),若,|C|=k(,如,C=1,2,k),则称,k-,可着色（,k-,可边着色、,k-,可面着色）。,13,色数,(chromatic number),k-,色图,:,可,k-,着色,但不可,(k-1)-,着色,色数,:,着色所需最少颜色数,点,色数,(G),边,色数,(G),面,色数,*,(G),例,:(G)=2,(G)=4,*(G)=,3,14,二部图,设无向图,G=,，若能将,V,划分成,V,1,和,V,2,，使得,G,中的每条边的两个端点都是一个属于,V,1,，另一个属于,V,2,，则称,G,为二部图（二分图，偶图），称,V,1,和,V,2,为互补顶点子集，常记为,.,完全二部图：,V,1,中的每个顶点均与,V,2,中的所有顶点相邻。,K,r,s,15,二部图判定,n(n=2),阶无向图,G,是二部图当且仅当,G,中无奇圈当且仅当,G,是,2-,可着色,。,16,点色数性质,(G)=1 G,是零图,(K,n,)=n,(G)=2 G,是非零图二部图,G,是,2-,可着色,G,是二部图,G,无奇圈,(C,n,)=2,n,偶数 ,(W,n,)=3,n,奇,数,3,n,奇数,4,n,偶,数,17,(G),上界,定理,18.7:,(G)(G)+1,证明,:vV(G),G,(v)=u|(u,v)E(G),|,G,(v)|(G),给,G,(v),中顶点着色至多需要,(G),种颜色,所以至少还剩一种颜色可用来给,v,着色,.#,18,(G),上界,定理,18.8(Brooks):,若,G,连通非完全图,K,n,(n,3,),非奇圈,则,(G)(G).#,说明,:,n=1G=K,1,n=2:,连通,G=K,2,(K,n,)=n=(G)+1,19,例,(Petersen,图,),例,:Petersen,图,=3.,解,1,:,由,Brooks,定理,=3.,又图中有奇圈,3.,所以,=3.#,解,2,:,存在如下,3-,着色,=3.,又图中有奇圈,3.,所以,=3.#,20,应用示例,1,某大学计算机专业三年级有,5,门选修课，其中课程,1,与,2,，,1,与,3,，,1,与,4,，,2,与,4,，,2,与,5,，,3,与,4,，,3,与,5,均有人同时选修，问安排这,5,门课考试至少需要几个时间段？,1,2,3,4,5,1,2,3,4,5,21,面着色与对偶图点着色,定理,9:,地图,G,可,k-,面着色,对偶图,G*,可,k-,着色,.,定理,9,:,连通无环平面图,G,可,k-,面着色,对偶图,G*,可,k-,着色,.,研究平面图,面,着色研究平面图,点,着色,22,五色定理,定理,(Heawood,1890):,任何平面图都可,5-,着色,v,1,v,2,v,3,v,4,v,5,u,23,定理,17.12,定理,17.12:,设,G,是简单平面图,则,(,G),5.,证明,:n 3n-6,与,m3n-6,矛盾,.,24,边着色,边色数,:,(G),定理,11(Vizing):G,是简单图,则,(G),(G)(G)+1.#,G=,是二部图,则,(G)=(G),n1,时,(K,n,)=n,n,为奇数,n-1,n,为偶数,25,应用示例,2,某一天内有,n,个教师给,m,个班上课,.,每个教师在同课时只能给一个班上课,.,(1),这一天内至少排多少节课,?,(2),不增加节数情况下至少需要几个教室,?,(3),若,n=4,m=5.,教师是,t,1,t,2,t,3,t,4,班是,c,1,c,2,c,3,c,4,c,5,.,已知,t,1,给,c,1,c,2,c,3,上,2,节,1,节,1,节课,t,2,给,c,2,c,3,各上,1,节课,t,3,给,c,2,c,3,c,4,各上,1,节课,t,4,给,c,4,c,5,上,1,节,2,节课,.,求最省教室的课表,.,26,应用示例,2(,解,),解,:,令,G=,T=t,1,t,2,t,m,C=c,1,c,2,c,n,E=(t,i,c,j,)|t,i,给,c,j,上一节课,.,给,G,进行边着色,同色边代表的教学可以同时进行,所以颜色数就是节数,同色边数就是教室数,.,(1)k=,(G)=(G),时,节数最少,.,(2)min max k,1,k,2,k,教室数最少,.,其中,k,i,是着颜色,i,的边数,.(,“,平衡,”,着色,),27,应用示例,2(,解,续,),解,:(,续,)(3),已知条件得出下图,G,T=t,1,t,2,t,4,C=c,1,c,2,c,5,.,(G)=4,节数最少是,4.,min max k,1,k,2,k,4,=3,教室数最少是,3.,课表如下,.#,t,1,t,2,t,3,t,4,c,1,c,2,c,3,c,4,c,5,28,应用示例,2(,解,续,),节,t,1,t,2,t,3,t,4,1,c,1,c,2,c,4,-,2,c,1,-,c,3,c,4,3,c,2,c,3,-,c,5,4,c,3,-,c,2,c,5,29,作业,P346 20,，,28,，,33,