二分图匹配——匈牙利算法和km算法简介

《二分图匹配——匈牙利算法和km算法简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二分图匹配匈牙利算法和KM算法简介二分图的概念二分图又称作二部图，是图论中的一种特殊模型。设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。112233445最大匹配给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题(maximalmatchingproblem)如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。匈牙利算法求最

2、大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。匈牙利算法由增广路的定义可以推出下述三个结论：1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。2－P经过取反操作可以得到一个更大的匹配M’。3－M为G的最大匹配当且仅当不存在相对于M的增广路径。匈牙利算法用增广路求最大匹配(称作匈

3、牙利算法，匈牙利数学家Edmonds于1965年提出)算法轮廓：(1)置M为空(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M(3)重复(2)操作直到找不出增广路径为止匈牙利算法程序清单：Functionfind(k:integer):integer;varst,sf,i,j,t:integer;queue,father:array[1..100]ofinteger;beginqueue[1]:=k;st:=1;sf:=1;fillchar(father,sizeof(father),0);repeat匈牙利算法fori:=1tondoi

4、f(father[i]=0)and(a[queue[st],i]=1)thenbeginifmatch2[i]<>0thenbegininc(sf);queue[sf]:=match2[i];father[i]:=queue[st];endelse匈牙利算法beginj:=queue[st];whiletruedobegint:=match1[j];match1[j]:=i;match2[i]:=j;ift=0thenbreak;i:=t;j:=father[t];匈牙利算法end;find:=1;exit;end;end;inc(st);untils

5、t>sf;find:=0;end;匈牙利算法在主程序中调用下面的程序即可得出最大匹配数。Bmatch:=0;ForI:=1tondoBmatch:=Bmatch+find(i);Writeln(Bmatch);一个关于二分图的性质：最大匹配数＋最大独立集＝X＋Y最佳匹配如果边上带权的话，找出权和最大的匹配叫做求最佳匹配。实际模型：某公司有职员x1,x2,…,xn,他们去做工作y1,y2,…,yn,每个职员做各项工作的效益未必一致，需要制定一个分工方案，使得人尽其才，让公司获得的总效益最大。数学模型：G是加权完全二分图，求总权值最大的完备匹配。KM算法穷

6、举的效率－n！，我们需要更加优秀的算法。定理：设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的一个最佳匹配。证明很容易。KM算法对于任意的G和M，可行顶标都是存在的：l(x)=maxw(x,y)l(y)=0欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹

7、配；问题是当标号之后的Gl无完备匹配时怎么办？1957年（居然比匈牙利算法早？？？），Kuhn和Munkras给出了一个解决该问题的有效算法，用逐次修改可行顶标l(v)的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。KM算法修改方法如下：先将一个未被匹配的顶点u(uin{x})做一次增广路，记下哪些结点被访问那些结点没有被访问。求出d=min{lx[i]+ly[j]-w[i,j]}其中i结点被访问，j结点没有被访问。然后调整lx和ly：对于访问过的x顶点，将它的可行标减去d，对于所有访问过的y顶点，将它的可行标增加d。修改后的顶标仍是可行顶

8、标，原来的匹配M仍然存在，相等子图中至少出现了一条不属于M的边，所以造成M的逐渐增广。KM算法