离散数学-图论7省名师优质课赛课获奖课件市赛课一等奖课件.ppt

点击,Second level,Third level,Fourth level,Fifth level,School of Information Science and Engineering,*,Click to edit Master title style,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,第十八章 匹配与着色,主要内容,二部图,二部图中匹配,点着色,地图着色与平面图点着色,边着色,1/26,School of Information Science and Engineering,18.1 二部图,定义1,设,G,=为一个无向图，若能将,V,分成,V,1,和,V,2,(,V,1,V,2,=,V,，,V,1,V,2,=,),，使得,G,中每条边两个端点都是,一个属于,V,1,，另一个属于,V,2,，则称,G,为,二部图,(或称,二分,图,、,偶图,等)，称,V,1,和,V,2,为,互补顶点子集,，常将二部图,G,记为.,又若,G,是简单二部图，,V,1,中每个顶点均与,V,2,中全部顶点相,邻，则称,G,为,完全二部图,，记为,K,r,s,，其中,r,=|,V,1,|，,s,=|,V,2,|.,注意，,n,阶零图为二部图.,2/26,School of Information Science and Engineering,二部图判别法,判定定理,无向图,G,=是,二部图,当且仅当,G,中无长度为奇数圈。,由定理可知图9中各图都是二部图，哪些是完全二部图？哪些图是同构？,3/26,School of Information Science and Engineering,定义2,设,G,=,E,*,E,，,(1),匹配,(边独立集),E,*,E,*中各边均不相邻,(2),极大匹配,E,*,E,*中不能再加其它边了,(3),最大匹配,边数最多匹配,(4),匹配数,最大匹配中边数，记为,1,上图中各图匹配数依次为3,3,4.,18.2 二部图中匹配,4/26,School of Information Science and Engineering,关于匹配中其它概念,定义3,设,M,为,G,中一个匹配.,(1),v,i,与,v,j,被,M,匹配,(,v,i,v,j,),M,(2),v,为,M,饱和点,有,M,中边与,v,关联,(3),v,为,M,非饱和点,无,M,中边与,v,关联,(4),M,为,完美匹配,G,中无,M,非饱和点,(5),M,交织路径,从,M,与,E,M,中交替取边组成,G,中路径,(6),M,可增广交织路径,起、终点都是,M,非饱和点交织路径,(7),M,交织圈,由,M,与,E,M,中边交替出现组成,G,中圈,上图中，只有第一个图存在完美匹配,5/26,School of Information Science and Engineering,18.2 二部图中匹配,定义4,设,G,=为二部图，|,V,1,|,|,V,2,|，,M,是,G,中最大匹配，若,V,1,中顶点全是,M,饱和点，则称,M,为,G,中,完备匹配.,|,V,1,|=|,V,2,|时完备匹配变成,完美匹配,.,图中，红边组成各图一个匹配，(1)中为完备匹配，(2)中匹配不是完备，(2)中无完备匹配，(3)中匹配是完备，也是完美.,(1)(2)(3),6/26,School of Information Science and Engineering,18.2 二部图中匹配,求匹配算法：,设,G,0,=,是二部图,置初值:,V,1,=,V,0,E,1,=,G,1,=,G,0,假如,G,1,是零图,则结束,得,E,1,.,不然在,V,1,中选取度最小结点,不妨设这个结点是,a,且与,a,相邻接一个结点为,b,取边(,a,b,),E,1,=,E,1,(,a,b,),从图,G,1,中删去结点,a,b,.(,即,V,1,=,V,1,-,a,b,),得到图,G,1,转到.,试对右图执行以上算法,7/26,School of Information Science and Engineering,18.2 二部图中匹配,执行算法:,a)度数最小结点是,c,E,1,=(,B,c,),b),度数最小结点是,d,E,1,=(,B,c,),(,A,d,),c),度数最小结点是,a,E,1,=(,B,c,),(,A,d,)(,C,a,),d),度数最小结点是,b,E,1,=(,B,c,),(,A,d,),(,C,a,),(,D,b,),当然执行此算法,不一定得到全部匹配.,8/26,School of Information Science and Engineering,Hall,定理,定理18.5,（,Hall定理,）设二部图,G,=中，|,V,1,|,|,V,2,|.,G,中存在从,V,1,到,V,2,完备匹配当且仅当,V,1,中任意,k,(,k,=1,2,|,V,1,|),个顶点最少与,V,2,中,k,个顶点相邻.,本定理中条件常称为“,相异性条件,”.,由Hall定理立刻可知，上图中(2)为何没有完备匹配.,定理18.6,设二部图,G,=中，,V,1,中每个顶点最少关联,t,(,t,1)条边，而,V,2,中每个顶点至多关联,t,条边，则,G,中存在,V,1,到,V,2,完备匹配。,证实关键点：满足相异性条件.定理18.6中条件称为,t,（,t,1）,条件,.,9/26,School of Information Science and Engineering,一个应用实例,某课题组要从,a,b,c,d,e,5人中派3人分别到上海、广州、香港去开会.已知,a,只想去上海，,b,只想去广州，,c,d,e,都表示想去广州或香港.问该课题组在满足个人要求条件下，共有几个派遣方案？,解 用二部图中匹配理论解本题方便.,令,G,=，其中,V,1,=,s,g,x,，,s,g,x,分别表示上海、广州和香港.,V,2,=,a,b,c,d,e,E,=(,u,v,)|,u,V,1,v,V,2,v,想去,u,.,G,如图所表示.,G,满足相异性条件，因而可派遣，共有9种派遣方案(请给出这9种方案).,10/26,School of Information Science and Engineering,18.3 点着色,定义5,(1)图,G,一个,点着色,给图,G,每个顶点涂上一个颜色，使相邻顶点含有不一样颜色,(2)对,G,进行,k,着色,（,G,是,k,-可着色）能用,k,种颜色给,G,顶点着色,(3),G,色数,(,G,)=,k,G,是,k,-可着色，但不是(,k,1)-可着色.,11/26,School of Information Science and Engineering,关于顶点着色几个简单结果,说明,:,(1),(,G,)=1当且仅当,G,为零图,(2),(,K,n,)=,n,(3)若,G,为奇阶轮图，则,(,G,)=3，若,G,为偶阶轮图，则,(,G,)=4.,(4)若,G,边集非空，则,(,G,)=2当且仅当,G,为二部图.,上述各图中，色数分别为,3，3，4，5，,为何？,12/26,School of Information Science and Engineering,对G着色方法(韦尔奇.鲍威尔法 Welch.Powell):,将G中结点按照度数递减次序排序，(此排序可能不唯一,因为可能有些结点度数相同)。,用第一个颜色对第一个结点着色，并按照排序,对与,前面,着色点,不邻接,每一个点着上相同颜色。,用另一个颜色对还未着色点,重复执行和，直到全部结点都着上颜色为止。,例:结点排序:A,B,E,F,H,D,G,C,结点度数:5,5,4,4,3,3,2,A,B,H,G,E,D,F,C,着色方法,13/26,School of Information Science and Engineering,图着色应用,1、,考试安排,：安排一所大学里期末考试，使得没有学生在同一时间有两门考试。,2、,频道分配,：把频道2到13分配给国内电视台，使得没有在200之内两家电视台在相同频道上播出。,3、,变址存放器,：在有效编译器里，当把频繁地使用变量暂时地保留在CPU中而不是常规内存，能够加速循环执行。对于给定循环来说，需要多少个存放器？,14/26,School of Information Science and Engineering,色数上界,定理18.7,对于任意无向图,G,，都有,(,G,),(,G,)+1,证实线索：对,G,阶数,n,做归纳.,定理18.8,若连通无向图,G,不是,K,n,（,n,3），也不含长度为奇数圈，则,(,G,),(,G,),定理18.8称为Brooks定理.,15/26,School of Information Science and Engineering,18.4 地图着色与平面图点着色,定义6,(1),地图,连通无桥平面图（嵌入）与全部面,(2),国家,地图面,(3)两个国家,相邻,它们边界最少有一条公共边,在上图地图中，有5个国家，其中1与2相邻，1与4相邻，2,3,4均与5相邻.,16/26,School of Information Science and Engineering,地图面着色,定义7,(1)地图,G,面着色,对,G,每个国家涂上一个颜色，相邻国家涂不一样颜色,(2),G,是,k,-面可着色,能用,k,种颜色给,G,面着色,(3),G,面色数,*(,G,)=,k,最少用,k,种颜色给,G,面着色.,地图面着色转化成对偶图点着色,定理18.9,地图,G,是,k,-面可着色当且仅当它对偶图,G,*是,k,-点可着色.,证实简单,五色定理,定理18.10,任何平面图都是5-可着色.,剩下大问题：四色猜测是否为真,17/26,School of Information Science and Engineering,18.5 边着色(无环无向图),定义8,(1)对,G,边着色,每条边着一个颜色，相邻边不一样色,(2),G,是,k,-边可着色,能用,k,种颜色给,G,边着色,(3),G,边色数,(,G,)最少用,k,种颜色给G边着色,定理18.11,(Vizing定理),G,为简单平面图，则,(,G,),(,G,),(,G,)+1.,定理18.12,(,W,n,)=,n,1,n,4.,定理18.13,二部图边色数等于最大度.,定理18.14,n,为奇数（,n,1）时，,(,K,n,)=,n,；,n,为偶数时，,(,K,n,)=,n,1.,18/26,School of Information Science and Engineering,第十八章 习题课,主要内容,二部图、匹配（边独立集）,二部图中完备匹配,图点着色、边着色、地图着色,基本要求,深刻了解匹配、点着色、边着色、面着色、色数等概念,会用二部图中匹配理论解简单问题,了解并记住地图面着色与它对偶图点着色之间关系,会用点色数及边色数处理一些实际问题.,19/26,School of Information Science and Engineering,练习,1,问：,G,中有完美匹配吗？为何？求匹配数,1,1无向图,G,以下所表示.,20/26,School of Information Science and Engineering,练习,2,2.彼得松图以下列图所表示：,在图上给出一个最大匹配，从而求出,1,21/26,School of Information Science and Engineering,练习,3,3.求图点色数,边色数,以及面色数,*.,解(1)因为,G,中含奇圈，所以,3,，由布鲁克斯定理知,=4,又轻易证实不能用3种颜色涂色：因为,a,b,c,彼此相邻，因而最少用3种颜色涂色，设用颜色,分别给,a,b,c,涂色.此时最少还用这三种颜色给,d,e,f,涂色，而且,d,e,f,也只能用颜色,和,，这么,g,只能用另一个颜色，比如,涂色，所以,=4.,22/26,School of Information Science and Engineering,(2)由维津（Vizing）定理可知,=4或5，但可用4种颜色给边,涂色，如图所表示.,练习,3,23/26,School of Information Science and Engineering,图20,图19,(3)易知图对偶图为图(1)所表示，轻易证实它点色数为4，所以图17面色数,*=4,，见图(2)所表示.,(1)(2),练习,3,24/26,School of Information Science and Engineering,练习,4,4.某校计算机系三年级学生在本学期共选6门选修课,C,i,i,=1,2,6.设,S,(,C,i,)为选,C,i,课学生集.已知,S,(,C,i,),S,(,C,6,),i,=1,2,5，,S,(,C,i,),S,(,C,i,+1,),i,=1,2,3,4，,S,(,C,5,),S,(,C,1,),.,问这6门课最少几个时间段？,25/26,School of Information Science and Engineering,解,解答,由已知条件做无向图,G,=，,其中,V,=,C,1,C,2,C,6,，,E,=(,C,i,C,j,)|,S,(,C,i,),S,(,C,j,),，,如图所表示,W,6,.,给,G,一个着色(点着色)，,C,i,与,C,j,着同色,C,i,与,C,j,不相邻,没有学生既学,C,i,又学,C,j,C,i,与,C,j,可同时考.,于是最少考试时间为,(,G,)=4（见定理17.21）,26/26,School of Information Science and Engineering,