二部图匹配网络流

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,of 220,二部图,&,网络流,二部图,二部图,定义,设,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,|.,11/13/2024,3,例,二部图,二部图,完全,二部图,K,3,3,11/13/2024,4,7.3 图的矩阵表示,二部图的判别法,定理,无向图,G,=,是,二部图,当且仅当,G,中无奇圈,.,11/13/2024,5,无向,简单,图的点覆盖集、点独立集、匹配,点独立集与点独立数,定义,设,G,=,，,V,*,V,.,(1),(,点,),独立集,V,*,V,*,中顶点彼此不相邻,(2),V,*,为,极大点独立集,V,*,中再加入任何顶点就不是点独立集,(3),最大点独立集,元素最多的点独立集,(4),点独立数,最大独立集中的元素个数，记为,0,在图中，点独立数依次为,2,2,3.,(1)(2)(3),11/13/2024,7,点覆盖集与点覆盖数,定义,设,G,=,V,*,V,.,(1),V,*,是,点覆盖集,e,E,，,v,V,*,，使,e,与,v,关联,(2),V,*,是,极小点覆盖集,V,*,的任何真子集都不是点覆盖集,(3),最小点覆盖集,顶点数最少的点覆盖集,(4),点覆盖数,0,(,G,),最小点覆盖的元素个数,图中，点覆盖数依次为,3,，,4,，,7.,11/13/2024,8,点覆盖集与点独立集的关系,0,+,0,=,n,点覆盖数,+,点独立数,=,点数,11/13/2024,9,匹配,(,边独立集,),与匹配数,(,边独立数,),定义,设,G,=,E,*,E,，,(1),匹配,(,边独立集,),E,*,E,*,中各边均不相邻,(2),极大匹配,E,*,E,*,中不能再加其他边了,(3),最大匹配,边数最多的匹配,(4),匹配数,最大匹配中的边数，记为,1,上图中各图的匹配数依次为,3,3,4.,11/13/2024,10,关于匹配中的其他概念,定义,设,M,为,G,中一个匹配,.,(1),匹配边,(,v,i,v,j,),M,(2),v,为,M,饱和点,有,M,中边与,v,关联,(3),v,为,M,非饱和点,无,M,中边与,v,关联,(4),M,的,交错路径,由匹配边和非匹配边交替构成的路径,(5),M,的,增广路径,起、终点都是,M,非饱和点的交错路径,11/13/2024,11,最大匹配判别定理,定理,M,为,G,中最大匹配当且仅当,G,中不含,M,的可增广交错路径,.,11/13/2024,12,二部图匹配,匈牙利算法,增广路径,匹配,M=x,1,y,1,x,2,y,3,x,3,y,4,有一条增广路径,x,1,x,2,y,1,y,2,x,3,x,4,y,3,y,4,x,1,x,2,y,1,y,2,x,3,x,4,y,3,y,4,x,1,x,2,y,1,y,2,x,3,x,4,y,3,y,4,由,M,增广路径可构造比,M,大的匹配,存在,M,增广路径,M,非最大匹配,用,(M-,),(,-M),代替,M,x,1,x,2,y,1,y,2,x,3,x,4,y,3,y,4,11/13/2024,14,匈牙利算法,由增广路径的定义可以推出下述三个结论：,1,、,的路径长度必定为奇数，第一条边和最后一条边都不属于,M,。,2,、,经过取对称差操作可以得到一个更大的匹配,M,。,3,、,M,为,G,的最大匹配当且仅当不存在关于,M,的增广路径。,11/13/2024,15,匈牙利算法,用增广路径求最大匹配,(,称作匈牙利算法,),算法：,(1),置,M,为空,(2),找出一条增广路,，通过取对称差操作获得更大的匹配,M,代替,M,(3),重复,(2),操作直到找不出增广路径为止,11/13/2024,16,匈牙利算法示例,图,1,图,2,11/13/2024,17,二部图的最小点覆盖,定理,:G,是二部图,则,0,=,1,.,即,二部图的最大匹配数,=,最小点覆盖数,注,:,定理对一般图不成立,.,11/13/2024,18,二部图的最大独立集,定理：二部图中,:,最大独立集数顶点总数最小点覆盖数,也,顶点总数最大匹配数,11/13/2024,19,例题,1,Place the Robots,问题描述,有一个,N*M(N,M=50),的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。,Wall,Grass,Empty,11/13/2024,20,例题,1,Place the Robots,（,ZOJ,）,模型一,5,4,6,7,8,3,2,1,1,2,3,4,6,5,7,8,于是，问题转化为求图的最大独立集问题。,以空地为顶点，有冲突的空地之间连边，可以得到右边的这个图：,11/13/2024,21,例题,1,Place the Robots,模型一,5,4,6,7,8,3,2,1,1,2,3,4,6,5,7,8,这是,NP,问题！,11/13/2024,22,将每一行，每一列被墙隔开,且,包含空地,的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。把这些块编上号。,同样，把竖直方向的块也编上号。,例题,1,Place the Robots,（,ZOJ,）,模型二,1,2,3,4,5,1,2,3,4,11/13/2024,23,例题,1,Place the Robots,模型二,1,2,3,4,5,1,2,3,4,把每个横向块看作,X,部的点，竖向块看作,Y,部的点，若两个块有公共的空地，则在它们之间连边。,于是，问题转化成这样的一个二部图：,1,1,2,2,3,3,4,4,5,11/13/2024,24,由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。,例题,1,Place the Robots,模型二,1,2,3,4,1,2,3,5,4,1,1,2,2,3,3,4,4,5,11/13/2024,25,例题,2,打猎,猎人要在,n*n,的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟都被打掉，也可以在某一列中打,这样此列中的所有鸟都打掉,.,问至少打几枪,才能打光所有的鸟？,建图：二部图的,X,部为每一行，,Y,部为每一列，如果,(,i,j,),有一只鸟，那么连接,X,部的,i,与,Y,部的,j,。,该二部图,最小点覆盖数,即是最少要打的枪数。,11/13/2024,26,Girls and Boys,The second year of the university somebody started a study on the romantic relations between the students.The relation“romantically involved”is defined between one girl and one boy.For the study reasons it is necessaryto find out the maximum set satisfying the condition:there are no two students in the set who have been“romantically involved”.The result of the program is thenumber of students in such a set.The input contains several data sets in text format.Each data set represents one set of subjects of the study,with the following description:the number of studentsthe description of each student,in the following format,11/13/2024,27,Girls and Boys,student_identifier:(number_of_romantic_relations,)student_identifier1 student_identifier2.orstudent_identifier:(0)The,student_identifier,is an integer number between 0and n-1,for n subjects.For each given data set,the program should write to standard output a line containing the result.,11/13/2024,28,Girls and Boys,Sample Input,7,0:(3)4 5 6,1:(2)4 6,Y:(0),E:(0),4:(2)0 1,5:(1)0,6:(2)0 1,Output,5,0,1,Y,E,4,5,6,11/13/2024,29,网络流简介,11/13/2024,31,11/13/2024,32,s,a,d,b,c,t,16,11,13,8,10,4,1,12,12,20,15,7,7,9,4,14,11,4,4,s,a,d,b,c,t,5,5,11,3,12,5,7,5,3,4,8,11,4,11,15,11/13/2024,33,剩余图 增广之后的新流,s,a,d,b,c,t,16,13,10,4,12,20,7,9,14,4,20,s,a,d,b,c,t,16,4,13,10,4,12,4,7,9,4,14,4,4,4,s,a,d,b,c,t,12,4,4,8,20,7,5,10,4,10,4,4,13,4,20,7,s,a,d,b,c,t,16,11,13,10,7,4,12,4,7,7,9,4,14,11,4,4,11/13/2024,34,剩余图 增广之后的新流,20,7,s,a,d,b,c,t,16,11,13,10,7,4,12,4,7,7,9,4,14,11,4,4,13,4,s,a,d,b,c,t,5,11,11,8,7,5,3,3,4,11,13,4,7,s,a,d,b,c,t,16,11,13,8,10,4,1,12,12,20,15,7,7,9,4,14,11,4,4,11/13/2024,35,剩余图 增广之后的新流,s,a,d,b,c,t,16,11,13,8,10,4,1,12,12,20,15,7,7,9,4,14,11,4,4,s,a,d,b,c,t,5,5,11,3,12,5,7,5,3,4,8,11,4,11,15,s,a,d,b,c,t,16,11,13,12,10,4,1,12,12,20,19,7,7,9,14,11,4,4,11,s,a,d,b,c,t,5,1,11,3,12,1,7,9,3,4,12,11,19,11/13/2024,36,2,2,1,3,4,2,2,2,2,2,1,3,4,2,2,2,2,2,1,3,4,2,2,2,2,2,0,2,0,2,2,1,3,4,2,2,2,2,2,2,2,1,3,4,2,0,2,2,2,2,2,2,1,2,3,4,2,2,2,2,2,11