二分图二分图又称作二部图，是图论中的一种特殊模型。
设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
如图就是一个二分图。
二分图的最大匹配给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)
如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
求二分图最大匹配可以用最大流或者匈牙利算法。
最大匹配
给定一个二分图G,在G的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配.
选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)
如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配.
匈牙利算法
求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的.但是这个算法的复杂度为边数的指数级函数.因此,需要寻求一种更加高效的算法.
增广路的定义(也称增广轨或交错轨):
若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径.
由增广路的定义可以推出下述三个结论:
1-P的路径长度必定为奇数,第一条边和最后一条边都不属于M.
2-P经过取反操作可以得到一个更大的匹配M'.
3-M为G的最大匹配当且仅当不存在相对于M的增广路径.
匈牙利算法
用增广路求最大匹配(称作匈牙利算法,匈牙利数学家Edmonds于1965年提出)
算法轮廓:
(1)置M为空
(2)找出一条增广路径P,通过取反操作获得更大的匹配M'代替M
(3)重复(2)操作直到找不出增广路径为止
g:array[1..maxn,1..maxm]of boolean;
y:array[1..maxm]of boolean;
link:array[1..maxm]of longint;
function find(v:longint):boolean;
var i:longint;
begin
for i:=1 to m do
if g[v,i] and (not y[ i ]) then
begin
y[ i ]:=true;
if (link[ i ]=0)or find(link[ i ]) then
begin
link[ i ]:=v;
find:=true;
exit;
end;
end;
find:=false;
end;
begin
//read the graph into array g[][]
for i:=1 to n do
begin
fillchar(y,sizeof(y),0);
if find(i) then inc(ans);
end;
其中n,m分别为2部图两边节点的个数,两边的节点分别用1..n,1..m编号
g[x][y]=true表示x,y两个点之间有边相连
link[y]记录的是当前与y节点相连的x节点
y记录的是y中的i节点是否被访问过.
算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.
代码中find(i)就是寻找有没有从x点i开始的增广轨,如果有就进行上述操作,代码是递归的,所以看起来不是很显然,画个图试试就很清楚了.
翻译成C语言：
//其中n,m分别为2部图两边节点的个数,两边的节点分别用1..n,1..m编号
bool g[n][m];//g[x][y]表示x,y两个点之间有边相连
bool y[m];//y记录的是y中的i节点是否被访问过.
int link[m];//link[y]记录的是当前与y节点相连的x节点
bool find(int v)
{
int i;
for(i=0;i<m;i++)
{
if(g[v][i]&&!y[i])
{
y[i]=true;
if(link[i]==0||find(link[i])
{
link[i]=v;
return true;
}
}
}
return false;
}
int main()
{
//read the graph int array g[][]
for(i=0;i<n;i++)
{
memset(y,0,sizeof(y));
if(find(i)) ans++;
}
return 0;
}