二分图最大匹配及常用建图方法.doc

《二分图最大匹配及常用建图方法.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法———艺术二分图匹配剖析很多人说，算法是一种艺术。但是对于初学者的我，对算法认识不是很深刻，但偶尔也能感受到他强大的魅力与活力。这让我追求算法的脚步不能停止。下面我通过分析匈牙利算法以及常用建图方式，与大家一起欣赏算法的美。匈牙利算法匈牙利算法是用来解决最大二分图匹配问题的，所谓二分图即“一组点集可以分为两部分，且每部分内各点互不相连，两部分的点之间可以有边”。所谓最大二分图匹配即”对于二分图的所有边，寻找一个子集，这个子集满足两个条件，1：任意两条边都不依赖于同一个点。2：让这个子集里的边在满足条件一的情况下尽量多。首先可以想到的是，我们可

2、以通过搜索，找出所有的这样的满足上面条件的边集，然后从所有的边集中选出边数最多的那个集合，但是我们可以感觉到这个算法的时间复杂度是边数的指数级函数，因此我们有必要寻找更加高效的方法。目前比较有效的方法有匈牙利算法和通过添加汇点和源点的网络流算法，对于点的个数都在200到300之间的数据，我们是采取匈牙利算法的，因为匈牙利算法实现起来要比网络流简单些。下面具体说说匈牙利算法：介绍匈牙利之前，先说说“增广轨”。定义：若P是图G中一条连通两个未匹配顶点的路径，并且属最大匹配边集M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的

3、一条增广轨定义总是抽象的下面通过图来理解它。图中的线段（2->3,3->1,1->4）便是上面所说的p路径，我们假定边（1,3）是以匹配的边，（2,3）（1,4）是未匹配的边，则边（4,1）边（1,3）和边（3,2）在路径p上交替的出现啦，那么p就是相对于M的一条增广轨，这样我们就可以用边1,4和边2,3来替换边1,3那么以匹配的边集数量就可以加1,。匈牙利算法就是同过不断的寻找增广轨实现的。很明显如果二分图的两部分点分别为n和m，那么最大匹配的数目应该小于等于MIN（n,m）;因此我们可以枚举任第一部分（的二部分也可以）里的每一个点，我们从每个

4、点出发寻找增广轨，最后吧第一部分的点找完以后，就找到了最大匹配的数目，当然我们也可以通过记录找出这些边。下面给出关于二分图最大匹配的两个定理1:最大匹配数+最大独立集=n+m2:二分图的最小覆盖数=最大匹配数3:最小路径覆盖=最大独立集最大独立集是指求一个二分图中最大的一个点集，该点集内的点互不相连。最小顶点覆盖是指在二分图中，用最少的点，让所有的边至少和一个点有关联。最小路径覆盖是指一个不含圈的有向图G中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束，且长度也为任意值，包

5、括0下面给出二分图最大匹配的伪代码：/*use[i]数组时标记第二部分点中的第j个点是否使用过。match[i]与第二部分中的点i匹配的点是match[i]*/IntGetAugmentPath(number)//通过number这个点寻找增广轨，找到返回1找不到返回0；Pßrelated[number].next;//与number相连的点；While（p!=NULL）{Ifnotused[p]then//p点没有被使用过Ifmatch[p]==0orGetAugmentPath(match[p])//p点没有和另一部分的点配对//或和p配对的

6、那个点可以找到其它点和他配对（找到增广轨）Return1;pßp.next//与number相连的下几个点}Return0;}endGetAugmentPath;我们只需要在主程序中对某一部分点集的每个点进行增广轨的寻找；Intmain{ansß0ForI=1àn//枚举第一部分的n个点；Forj=1àmuse[j]ßfalse//把第二部分的m个点表示为没有使用过。ifGetAugmentPath(i)thenansßans+1//找到增广轨就给边数加一；}程序非常好写，也非常好懂。123456712345678每次我们从上面的第i个点出发尽量

7、去找一个能唯一和它匹配的点p，策略有两种，一是直接在下面的点中找到一个点p，他没有和上面的点匹配过（即match[p]=0）。二是当p和上面的某个点匹配过，即（match[p]）那么我们就从match[p]出发，去给他找下面另外的点和他匹配，把p点留给点i。这样我们不就多找到了一条？然而对于匈牙利算法来说，难点并不在与程序本身，而是在如何把实际问题转化为最大二分图匹配的模型，然后再利用匈牙利算法解决。下面我们说几种常见的建图模型。常见建图模型法一行列匹配法101010100上图是一个3*3的矩阵，方格内的1表示这个地方有敌人，0表示没有敌人，现在

8、我们有很多箭，每根箭可以杀死一行或者一列的敌人，问题是，我们要杀死所有的敌人至要用到几根箭？初看似乎和最大二分图没有什么相关联的，然而如