Bipartite Matching and Hungarian Algorithm.

1. 二分图的基本概念

设$G=(V,E)$是一个无向图，如果顶点集合$V$可分割为两个互不相交的子集$X,Y$，并且边集合$E$中每条边关联的两个顶点分别属于这两个子集，则称图$G$为一个二分图(bipartite graph)。

下图给出了一个二分图$G$的例子，其顶点集合$V=\{X_1,X_2,X_3,X_4,Y_1,Y_2,Y_3,Y_4\}$，边集合$E=\{(X_1,Y_1),(X_1,Y_2),(X_2,Y_2),(X_2,Y_3),(X_3,Y_1),(X_3,Y_2),(X_4,Y_3)\}$

2. 图的匹配

对于二分图$G$的一个子图$M$，如果子图$M$的边集合$E$中的任意两条边都不依附于同一个顶点，则称$M$是一个匹配(matching)。匹配建立了二分图的两个子集中部分顶点的一一对应关系。

下图给出了二分图$G$的两个匹配$M_1$和$M_2$:

匹配$M$的边集合所关联的点称为饱和点，其余点称为非饱和点。如上图中：

• $M_1$的饱和点：$X_1,X_3,X_4,Y_1,Y_2,Y_3$
• $M_2$的饱和点：$X_1,X_2,Y_1,Y_3$

在图$G$的所有匹配中，所含匹配边数最多的匹配称为图$G$的最大匹配。 如果图$G$的某个匹配使得图$G$的所有顶点都是饱和点，则该匹配是一个完美匹配。完美匹配一定是最大匹配，但并非每个图都存在完美匹配。

定义图$G$中的一条路径，如果该路径中的边在属于匹配$M$和不属于匹配$M$中交替出现，则称其为交错路。下图分别给出了匹配$M_3=\{(X_2,Y_2),(X_4,Y_3)\}$和$M_4=\{(X_1,Y_2),(X_2,Y_3)\}$的一条交错路：

对于匹配$M$的一条交错路，如果该交错路的起点和终点都是匹配$M$的非饱和点，则该交错路为增广路。下图给出了匹配$M_3=\{(X_2,Y_2),(X_4,Y_3)\}$的一条增广路。

增广路具有以下结论：

1. 增广路的路径边数为奇数，且第一条边和最后一条边都不属于匹配$M$；
2. 增广路中匹配边的数量总是比非匹配边的数量多$1$条；
3. 将增广路中边的匹配方式取反，会得到一个更大的匹配$M’$，匹配数$+1$；
4. 匹配$M$是图$G$的最大匹配等价于不存在$M$的增广路。

3. 二分匹配与匈牙利算法

二分匹配(Bipartite Matching)问题即寻找二分图$G$中的最大匹配$M$。

匈牙利算法(Hungarian Algorithm)最早是由匈牙利数学家D.Kőnig用来求矩阵中$0$元素个数的一种方法，由此他证明了“矩阵中独立$0$元素的最多个数等于能覆盖所有$0$元素的最少直线数”。

1955年W.W.Kuhn在求解指派问题时引用了这一结论, 并提出根据二分图的增广路寻找最大匹配的算法，仍然称为“匈牙利算法”。

指派问题是人员调度问题中的经典问题：由$m$个人完成$n$项工作，第$i$个人完成第$j$项工作的成本为$c_{ij}$，由此构造成本矩阵$C$。现需确定指派方案使得完成任务的总成本最低。特别地，若工作成本$c_{ij}=1$，则成本矩阵$C$可以padding为图的连接矩阵，这等价于图论中的最大匹配问题。

匈牙利算法的思路为：

1. 设二分图$G$的初始匹配$M$为空$\Phi$；
2. 寻找一条增广路，通过取反操作构造一个更大的匹配$M’$代替匹配$M$；
3. 重复上述步骤直至寻找不到增广路。

在实现时可以通过深度优先搜索进行增广路径的选择。

• 首先从任意的一个未配对的点$u$开始，任意选一条边$u\to v$开始配对。
• 如果点$v$未配对过，则配对成功，对应一条增广路。
• 如果点$v$已经被配对，则尝试调整与点$v$配对的点，使其与其余未配对的点进行配对，使得点$v$能与点$u$成功配对，并更新原来的配对关系。
• 如果点$u$始终未能与点$v$成功配对，则从点$u$的边中重新选一条边，直到点$u$配对成功或尝试过点$u$的所有边为止。
• 然后对剩下的未配对点进行配对，直到遍历所有点，找不到新的增广路为止。

下面给出匈牙利算法的简单实现：

def Hungarian(G):
    N, M = G.shape # G[u,v]=1表示结点u,v之间有连接
    matched = [None] * N # 记录已匹配的结点

    def found(x): # 通过DFS寻找增广路
        for m in range(M):
            if G[x, m] != 1 or visited[m]:
                continue
            visited[m] = 1
            if not matched[m] or found(matched[m]):
                matched[m] = x
                return True
        return False

    for n in range(N):
        visited = [0] * N # 记录已访问的结点
        found(n)
    return [*enumerate(matched)] # 返回(v,u)

使用scipy库可以方便地实现匈牙利算法：

from scipy.optimize import linear_sum_assignment
match_index_list = linear_sum_assignment(cost_matrix)
# ([X1, X2, ...], [Y1, Y2, ...])