二分图匹最大配与最佳匹配.doc

二分图：
二分图是这样的一个图，它的顶点可以分为两个集合X和Y。所有的边关联的两个顶点中，恰好一个属于集合X，一个属于集合Y。
二分图的匹配：
给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
二分图的最大匹配:
二分图的所有匹配中包含边数最多的匹配称为图的最大匹配。
完美（完备）匹配：
如果所有点都在匹配边上，称这个最大匹配是完美匹配。
最佳匹配：
如果边上带权的话，找出权和最大的匹配叫做求最佳匹配。
增广路径：
也称增广轨或交错轨。若P是图G中一条连通两个未匹配顶点的路径，并且属最大匹配边集M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广轨。
定义总是抽象的下面通过图来理解它。

图中的线段（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,。

下面给出关于二分图最大匹配的三个定理
1:最大匹配数+最大独立集=n+m
2:二分图的最小覆盖数=最大匹配数
3:最小路径覆盖=最大独立集
最大独立集是指求一个二分图中最大的一个点集，该点集内的点互不相连。
最小顶点覆盖是指在二分图中，用最少的点，让所有的边至少和一个点有关联。
最小路径覆盖是指一个不含圈的有向图G中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束，且长度也为任意值，包括0.
求解二分图最大匹配的方法：
匈牙利算法（时间复杂度O(nm)）
其思想是是通过不断的寻找增广轨实现最大匹配。
转化为单位容量简单网络的最大流问题(本文不介绍)
在二分图的基础上，加入源点s和汇点t，让s与每个X结点连一条边，每个Y结点和t连一条边，所有弧的容量为1。这样，饱和弧就对应着匹配边。

匈牙利算法二分图最大匹配的伪代码：
/*
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配对的那个点可以找到其它点和他配对（找到增广轨）
{
Modifyuse[number]andmatch[p]
Return1;
}enfif;
pp.next//与number相连的下个点
}
Return0;
}endGetAugmentPath;

我们只需要在主程序中对某一部分点集的每个点进行增广轨的寻找；
Intmain{
ans0
Forj=1m
use[j]false//把第二部分的m个点表示为没有使用过。
Fori=1n//枚举第一部分的n个点；
ifGetAugmentPath(i)then
ansans+1//找到增广轨就给边数加一；
}
例子：

每次我们从上面的第i个点出发尽量去找一个能唯一和它匹配的点p，策略有两种，一是直接在下面的点中找到一个点p，他没有和上面的点匹配过（即match[p]=0）。二是当p和上面的某个点匹配过，即（match[p]）那么我们就从match[p]出发，去给他找下面另外的点和他匹配，把p点留给点i。这样我们不就多找到了一条？

然而对于匈牙利算法来说，难点并不在与程序本身，而是在如何把实际问题转化为最大二分图匹配的模型，然后再利用匈牙利算法解决。

KM（Kuhn-Munkras）算法求二分图最佳的最佳匹配
设M是一个带权完全二分图G的一个完备匹配，给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示，第j个y顶点的可行标用ly[j]表示)，如果对所有的边(i,j)inG,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权)，且对所有的边(i,j)inM,都有lx[i]+ly[j]=w[i,j]成立，则M是图G的一个最佳匹配。
对于任意的G和M，可行顶标都是存在的：
l(x)=maxw(x,y)
l(y)=0
欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的Gl无完备匹配时怎么办？1957年，Kuh