二部图&网络流二部图25/1/13of220二部图定义设G=为一个无向图，若能将V分成V1和V2(V1V2=V，V1V2=)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图(或称二分图、偶图等)，称V1和V2为互补顶点子集，常将二部图G记为.又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，则称G为完全二部图，记为Kr,s，其中r=|V1|，s=|V2|.25/1/17.3图的矩阵表示4of220例二部图二部图6v4v5v1v2v3v完全二部图K3,325/1/15of220二部图的判别法定理无向图G=是二部图当且仅当G中无奇圈.无向简单图的点覆盖集、点独立集、匹配25/1/17of220点独立集与点独立数定义设G=，V*V.(1)(点)独立集V*——V*中顶点彼此不相邻(2)V*为极大点独立集——V*中再加入任何顶点就不是点独立集(3)最大点独立集——元素最多的点独立集(4)点独立数——最大独立集中的元素个数，记为0在图中，点独立数依次为2,2,3.(1)(2)(3)25/1/18of220点覆盖集与点覆盖数定义设G=,V*V.(1)V*是点覆盖集——eE，vV*，使e与v关联(2)V*是极小点覆盖集——V*的任何真子集都不是点覆盖集(3)最小点覆盖集——顶点数最少的点覆盖集(4)点覆盖数——0(G)——最小点覆盖的元素个数图中，点覆盖数依次为3，4，7.25/1/19of220点覆盖集与点独立集的关系0+0=n点覆盖数+点独立数=点数25/1/110of220匹配(边独立集)与匹配数(边独立数)定义设G=,E*E，(1)匹配(边独立集)E*——E*中各边均不相邻(2)极大匹配E*——E*中不能再加其他边了(3)最大匹配——边数最多的匹配(4)匹配数——最大匹配中的边数，记为1上图中各图的匹配数依次为3,3,4.25/1/111of220关于匹配中的其他概念定义设M为G中一个匹配.(1)匹配边——(vi,vj)M(2)v为M饱和点——有M中边与v关联(3)v为M非饱和点——无M中边与v关联(4)M的交错路径——由匹配边和非匹配边交替构成的路径(5)M的增广路径——起、终点都是M非饱和点的交错路径25/1/112of220最大匹配判别定理定理M为G中最大匹配当且仅当G中不含M的可增广交错路径.二部图匹配匈牙利算法25/1/114of220增广路径匹配M={{x1,y1},{x2,y3},{x3,y4}}有一条增广路径x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4由M增广路径可构造比M大的匹配存在M增广路径M非最大匹配用(M-)(-M)代替Mx1x2y1y2x3x4y3y425/1/115of220匈牙利算法由增广路径的定义可以推出下述三个结论：1、的路径长度必定为奇数，第一条边和最后一条边都不属于M。2、经过取对称差操作可以得到一个更大的匹配M。3、M为G的最大匹配当且仅当不存在关于M的增广路径。25/1/116of220匈牙利算法用增广路径求最大匹配(称作匈牙利算法)算法：(1)置M为空(2)找出一条增广路，通过取对称差操作获得更大的匹配M代替M(3)重复(2)操作直到找不出增广路径为止25/1/117of220匈牙利算法示例图1图225/1/118of220二部图的最小点覆盖定理:G是二部图,则0=1.即二部图的最大匹配数=最小点覆盖数注:定理对一般图不成立.25/1/119of220二部图的最大独立集定理：二部图中:最大独立集数＝顶点总数－最小点覆盖数也＝顶点总数－最大匹配数25/1/120of220例题1PlacetheRobots问题描述有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。WallGrassEmpty25/1/121of220例题1PlacetheRobots（ZOJ）模型一5467832112346578于是，问题转化为求图的最大独立集问题。以空地为顶点，有冲突的空地之间连边，可以得到右边的这个图：25/1/122of220例题1PlacetheRobots模型一5467832112346578这是NP问题！25/1/123of220将每一行，每一列被墙隔开且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。把这些块编上号。同样，把竖直方向的块也编上号。例题1PlacetheRobots（ZOJ）模型二12345123425/1/124of220例题1PlacetheRobots模型二123451234把每个横向块看作X部的点，竖向块看作Y部的点，若两个...
