二部图匹配网络流ppt课件.ppt

《二部图匹配网络流ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二部图&网络流7/30/20211二部图7/30/20212二部图定义设G=为一个无向图，若能将V分成V1和V2(V1V2=V，V1V2=)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图(或称二分图、偶图等)，称V1和V2为互补顶点子集，常将二部图G记为.又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，则称G为完全二部图，记为Kr,s，其中r=

2、V1

3、，s=

4、V2

5、.7/30/20213例二部图二部图完全二部图K3,37/30/202147.3图的矩阵表示二部图的判别法定理无向图G=是二部

6、图当且仅当G中无奇圈.7/30/20215无向简单图的点覆盖集、点独立集、匹配7/30/20216点独立集与点独立数定义设G=，V*V.(1)(点)独立集V*——V*中顶点彼此不相邻(2)V*为极大点独立集——V*中再加入任何顶点就不是点独立集(3)最大点独立集——元素最多的点独立集(4)点独立数——最大独立集中的元素个数，记为0在图中，点独立数依次为2,2,3.(1)(2)(3)7/30/20217点覆盖集与点覆盖数定义设G=,V*V.(1)V*是点覆盖集——eE，vV*，使e与v关联(2)V*是极小点覆盖集——V*的任何真子集都不是点

7、覆盖集(3)最小点覆盖集——顶点数最少的点覆盖集(4)点覆盖数——0(G)——最小点覆盖的元素个数图中，点覆盖数依次为3，4，7.7/30/20218点覆盖集与点独立集的关系0+0=n点覆盖数+点独立数=点数7/30/20219匹配(边独立集)与匹配数(边独立数)定义设G=,E*E，(1)匹配(边独立集)E*——E*中各边均不相邻(2)极大匹配E*——E*中不能再加其他边了(3)最大匹配——边数最多的匹配(4)匹配数——最大匹配中的边数，记为1上图中各图的匹配数依次为3,3,4.7/30/202110关于匹配中的其他概念定义设M为G中一个匹配.(1)匹配

8、边——(vi,vj)M(2)v为M饱和点——有M中边与v关联(3)v为M非饱和点——无M中边与v关联(4)M的交错路径——由匹配边和非匹配边交替构成的路径(5)M的增广路径——起、终点都是M非饱和点的交错路径7/30/202111最大匹配判别定理定理M为G中最大匹配当且仅当G中不含M的可增广交错路径.7/30/202112二部图匹配匈牙利算法7/30/202113增广路径匹配M={{x1,y1},{x2,y3},{x3,y4}}有一条增广路径x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4由M增广路径可构造比M大的匹配存在

9、M增广路径M非最大匹配用(M-)(-M)代替Mx1x2y1y2x3x4y3y47/30/202114匈牙利算法由增广路径的定义可以推出下述三个结论：1、的路径长度必定为奇数，第一条边和最后一条边都不属于M。2、经过取对称差操作可以得到一个更大的匹配M。3、M为G的最大匹配当且仅当不存在关于M的增广路径。7/30/202115匈牙利算法用增广路径求最大匹配(称作匈牙利算法)算法：(1)置M为空(2)找出一条增广路，通过取对称差操作获得更大的匹配M代替M(3)重复(2)操作直到找不出增广路径为止7/30/202116匈牙利算法示例图1图27/30/202117

10、二部图的最小点覆盖定理:G是二部图,则0=1.即二部图的最大匹配数=最小点覆盖数注:定理对一般图不成立.7/30/202118二部图的最大独立集定理：二部图中:最大独立集数＝顶点总数－最小点覆盖数也＝顶点总数－最大匹配数7/30/202119例题1PlacetheRobots问题描述有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。WallGrassEmpty7/30/202120例题1Pl

11、acetheRobots（ZOJ）模型一5467832112346578于是，问题转化为求图的最大独立集问题。以空地为顶点，有冲突的空地之间连边，可以得到右边的这个图：7/30/202121例题1PlacetheRobots模型一5467832112346578这是NP问题！7/30/202122将每一行，每一列被墙隔开且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。把这些块编上号。同样，把竖直方向的块也编上号。例题1PlacetheRobots（ZOJ）模型二1234512347/30/