笔记：二部图最大匹配的匈牙利算法

二部图最大匹配问题

定义

设简单二部图(G=< A,B,E>,Msubset E,)如果(M)中任意两条边都不相邻，则称(M)是(G)的匹配。当(M)的边数最多时，(M)称作最大匹配。当(|A|=|B|=n)时，边数为(n)的匹配称作完美匹配。

相关概念

交错路径和增广交错路径

设(M)是二部图(G)的一个匹配，则称(M)中的边为匹配边，(G)中不属于(M)的边为非匹配边，与匹配边关联的顶点为饱和点。(G)中由匹配边和非匹配边交替构成的路径称为交错路径，起点和重点都是非饱和顶点的交错路径称为增广交错路径。

引理1

设(M)是二部图(G)的一个匹配，(P)是一条关于(M)的增广交错路径，则(M'=Migoplus E(P))（和原来匹配做对称差）是一个匹配，且(|M'|=|M|+1)，其中(E(P))是(P)的边集。

定理1

二部图的匹配是最大匹配当且仅当不存在关于它的增广交错路径。

匈牙利算法（Hungarian algorithm）

基本思想

(1).从初始匹配(M)开始，寻找一条关于它的增广交错路径(P)

(2).令(Mleftarrow Migoplus E(P))

(3).检查是否存在关于(M)的增广交错路径(P)，若不存在，算法结束。否则转(2).

实现：标号法

1.设当前匹配为(M)，对(A)中每一个非饱和点(A_i)加标号(l(A_i)=0)，(A_i)是已标号但未检查的点。

2.对任意已标号但未检查的顶点(A_i)，把所有与其相邻但未标号的顶点(B_j)标号为(l(B_j)=A_i).

3.如果(B_j)是非饱和点，则找到一条增广交错路径，修改匹配，重新开始标号。

4.如果(B_j)是饱和点，则设((A_k,B_j)in M)，令(l(A_k)=B_j)，则(A_k)成为已标号未检查顶点，(A_i)成为已标号已检查的顶点。

5.重复算法，直到(A)中不存在已标号未检查的顶点。

匈牙利算法的复杂度分析

设二部图(G=< A,B,E>)。在匈牙利算法的每个阶段若找到增广交错路径(P)，令(Mleftarrow Migoplus E(P)).对于初始状态，(M=emptyset)是(G)的匹配。当计算终止时，不存在增广交错路径。

除去算法最终阶段外，算法每个阶段增加一条匹配边，匹配边总数为(min{|A|,|B|})条，所以最多有(min{|A|,|B|}+1)个阶段，在每个标号阶段中，每条边最多被检查一次，增广交错路径长度不超过(2|M|+1)，所以每个阶段将在(O(|E|))内完成。故整个算法在(O(min{|A|,|B|} imes E))步内中止。