二分图

null二分图匹配二分图匹配Bi-partite graphBi-partite graph二分图的定义： 二分图是这样的一个图，它的顶点可以分为两个集合X和Y。所有的边关联的两个顶点中，恰好一个属于集合X，一个属于集合Y。 二分图的匹配： 给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。二分图的最大匹配二分图的最大匹配定义： 图中包含边数最多的匹配称为图的最大匹配。如右图所示：蓝色部分 就构成一个最大匹配， 同时它也是一个完美匹 配 完美匹配： 如果所有点都在匹配边上，称这个最大 匹配是完美匹配。 二分图的最大匹配二分图的最大匹配匈牙利算法（时间复杂度O(nm)） 其思想是用宽度优先搜索来找增广路径（和floodfill算法类似 转化为单位容量简单网络的最大流问题 在二分图的基础上，加入源点s和汇点t，让s与每个X结点连一条边，每个Y结点和t连一条边，所有弧的容量为1。这样，饱和弧就对应着匹配边。二分图的最大匹配二分图的最大匹配匈牙利算法： 寻找增广路： 初始时最大匹配为空 for 二分图左半边的每个点i     do 从点i出发寻找增广路径 如果找到，则把它取反 （即增加了总了匹配数）。 看一道例题：PKU 1469 PKU 1469PKU 1469 一共有N个学生跟P门课程,一个学生可以任意选一门或多门课,问是否达成: 1.每个学生代表的都是不同的课（如果一个学生选修的那门课，那么他就可以代表这门课） 2.每门课都有一个代表 PKU1469PKU1469输入为: P N(课程数跟学生数) 接着有P行,格式为Count studenti studenti+1 ……studentcount (Count表示对课程1感兴趣的学生数,接着有Count个学生) 如第一行2 1 2表示学生1跟学生2对课程1感兴趣 输出为: 若每门课都能找到一位代表则输出”YES”,否则为”NO” PKU1469PKU1469假如有三个学生跟三门课程,学生1,2,3.为了跟学生区分,假设3个课程为4,5,6 左边节点是学生,右边节点是课程,下图表示,学生1对课程4,5感兴趣,学生2对课程5,6感兴趣,学生3对课程6感兴趣于是问题就变为在二分图中寻找最大匹配,只要这个最大匹配大于或等于课程数P,那么就达到要求了.寻找最大匹配的匈牙利算法流程 寻找最大匹配的匈牙利算法流程 首先我们先看节点1,寻找下一条边,假设找到节点5,因为1跟5都还没匹配,所以找到一个匹配.标记,xM[1]=5,yM[5]=1;假如我们用xM数组表示左边节点对其右边节点的匹配, yM表示右边节点对其左边节点的匹配,初始化为-1;现在重点看节点3,当寻找下一条边时,如图中的蓝边,我们发现节点6的yM[6]=2;已经匹配了.此时我们就转到节点6的匹配点2上去,发现节点2的另一条边2->5中节点5也已经匹配了,yM[5]=1;继续转到节点1,发现节点1的边1->4中节点4还没匹配.于是我们找到了一个增广路径增广路如图中箭头所示null 总结总结所以流程就是: 1,对于一个未匹配的节点u,寻找它的每条边,如果它的边上的另一个节点v还没匹配则表明找到了一个匹配,直接转步骤4; 2,假如节点u它边上的另一个节点v已经匹配,那么就转向跟v匹配的节点,假设是w,然后再对w重复1,2的步骤,即寻找增广路. 3,假如我们在1,2步过程中找到一条增广路, 那么修改各自对应的匹配点,转步骤4,若无增广路, 则退出. 4,匹配数+1;最小点覆盖最小点覆盖最小覆盖： 最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数 M 简单的证明如下： （1）M个是足够的。只需要让它们覆盖最大匹配的M条边，则其它边一定被覆盖（如果有边e不被覆盖，把e加入后得到一个更大的匹配） （2）M个是必需的，仅考虑形成最大匹配的这M条边，由于它们两两之间没有公共点，因此至少需要M个点才可以把它们覆盖 PKU 3041:(类似的有PKU3020) PKU 3041:(类似的有PKU3020) 问题: 假如你现在正处在一个N*N的矩阵中,这个矩阵里面有K个障碍物,你拥有一把武器,一发弹药一次能消灭一行或一列的障碍物,求最小的弹药消灭全部障碍物 输入为: N K 接下来有K行,每行包含障碍物的坐标,即r行c列; 如: 3 4 1 1 1 3 2 2 3 2 输出为: 花费最小的弹药数PKU3041PKU3041对于上面那个数据我们可以用下面的表示,0表示无障碍物,1表示有; 1 0 1 0 1 0 0 1 0 首先,我们利用行跟列做二分图:123123行列如果第i行的第j列有障碍物,则在图中左边的i行连一条边到右边的j列,上面的数据就对应左图于是问题就转化成最小点覆盖的问题.求最大匹配即可.PKU2226PKU2226现在我们看一道构图比较复杂的题：PKU2226 DAG图的最小路径覆盖DAG图的最小路径覆盖用尽量少的不相交简单路径覆盖有向无环(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。 解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m 记住一个重要的结论： DAC图的最小路径覆盖数=节点数(n)-最大匹配数 看一道例题：PKU1422PKU1422PKU1422 有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。 你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问（visit）所有的路口。对于伞兵的起始降落点不做限制。Input: 3 3 4 1 3 2 3Output: 2null二分图的最大独立集二分图的最大独立集最大独立集问题： 在Ｎ个点的图G中选出m个点，使 这m个点两两之间没有边．求m最大值． 记住一个重要的结论： 二分图的最大独立集数=节点数(n)-最大匹配数 null黑色点即为一个最大独立集可以这样理解，在总的点集中，去掉最少的点， 使得剩下的点相互之间没有边。用最少的点去 覆盖所有的边，也就是最小覆盖。二分图最优匹配二分图最优匹配又称带权最大匹配。 二分图的每条边带有权值。求一个匹配使得匹配边上的权值和最大。 一般X和Y集合顶点个数相同，最优匹配也是一个完备匹配，即每个顶点都被匹配。如果个数不相等，可以通过补点加0边实现转化。 最小？ 看一道例题：PKU2195 PKU2195PKU2195题意： 有N个人跟N个房子,每个人跟房子都有一定的距离, 现在要让这N个人全部回到N个房子里面去,要求所 有人回去的距离最短. 现在我们假设要求的是最大距离.那么就是求最大权 匹配. 下面我们先介绍一下KM算法 KM算法KM算法基本概念：可行顶标和相等子图 可行顶标：L是一个关于结点的函数，L(x)是顶点x对应的顶标值。可行顶标对于图中的每条边(x,y)都有L(x)+L(y)>=w(x,y) 相等子图：只包含L(x)+L(y)=w(x,y)的边的子图KM算法KM算法定理：如果一个相等子图中包含完备匹配，那么这个匹配就是最优匹配 证明：由于在算法过程一直保持顶标的可行性，所以任意一个匹配的权值和肯定小于等于所有结点的顶标之和，则相等子图中的完备匹配肯定是最优匹配KM算法KM算法算法流程 设顶点Xi的顶标为a[i]，顶点Yi的顶标为b[i] ⅰ.初始时，a[i]为与Xi相关联的边的最大权值，b[j]=0，保证a[i]+b[j]>=w(i,j)成立 ⅱ.当相等子图中不包含完备匹配时，就适当修改顶标以扩大相等子图，直到找到完备匹配为止 ⅲ.修改顶标的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 KM算法KM算法当从Xi寻找交错路失败后，得到一棵交错树，它的所有叶子节点都是X节点，对交错树中X顶点的顶标减少d值，Y顶点的顶标增加d值，对于图中所有的边(i,j)，可以看到 i和j都不在交错树中，边(i,j)仍然不属于相等子图 i和j都在交错树中，边(i,j)仍然属于相等子图 i不在交错树中，j在交错树中，a[i]+b[j]扩大，边(i,j)不属于相等子图 KM算法KM算法i在交错树,j不在交错树中,边(i,j)有可能加入到相等子图中 为了使a[i]+b[j]>=w(i,j)始终成立,且至少有一条边加入到相等子图中,d=min{a[i]+b[j]-w(i,j)},i在交错树中,j不在交错树中 null假设有3个人,我们弄个简化版的.每个人与家的距离如下图 第一个人到家1,2,3的距离为3,5,4,第二个人只能到家1,2距离为2,4,第三个人只能到家3,距离为7;nullnull找到最优匹配null回到例题:PKU2195 题目是说有N个人跟N个房子,每个人跟房子都有一定的距离,现在要让这N个人全部回到N个房子里面去,要求所有人回去的距离最短. 那么求的就是最小权匹配了,那么 如果我们把所有边的权值取反,如图所示,求其最大匹配,那么结果就是我们要的了.问题解决.练习题练习题Pku2239,2536 Pku3041,1325,2226 pku1466 Pku1422,2594 pku2195THE ENDTHE END