最大匹配问题

Intro

二分图是一种特殊模型：若无向图G=(V,E)的顶点V能被划分为两个交集为空的顶点集，并且任意边的两个端点都分属于两个集合，则称图G为一个为二分图

而在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配，最大匹配即为在所有的匹配中，边数最大的一个匹配，特别的，如果很幸运的所有的顶点都在此匹配中，则称此匹配为最优匹配 or 完美匹配

下图表示的即为一个二分图，其中最大匹配M=(A1, B3), (A2, B1), (A3, B2), (A4, B4)

匈牙利算法

介绍

匈牙利算法是由匈牙利数学家Edmonds于1965年提出而得名，用于寻找二分图中的最大匹配

给定二分图G

首先对于A按照顺序匹配对应的B：

1. A1匹配B1
2. A2匹配B1，失败->A2匹配B2
3. A3匹配B1，B2，失败->A3匹配B3

此时我们发现，对于点A4，按照之前的方法，无法找到可以匹配的点，此时匈牙利算法开始发挥作用：尝试寻找一条增广路

增广路的定义为起点与终点皆为非匹配点的交错路，而交错路即为处于匹配中和不处于匹配中的边相互交错形成的路

此时我们反转所找到的增广路，使得增广路上的所有点转变为匹配点，且匹配边数+1

再重复步骤一，我们可以得到图G的最大匹配M=(A1, B1), (A2, B4), (A3, B3), (A4, B2), (A5, B5)，如下图

实现

bool dfs(int x, vector match) {
    vector vis(b.size(), 0);
    for (int i = 0; i < b.size(); i++)
    {
        if (edge[x][i] == 0 || vis[i])
        {
            continue;
        }
        vis[i] = true;
        if (match[i] == -1 || dfs(match[i])
        {
            match[i] = x;
            return true;
        }
    }
    return false;
}

int Hungarian() {
    vector match(b.size(), -1);
    int cnt = 0;
    for (int i = 0; i < a.size(); i++)
    {
        if (dfs(i, match))
        {
            ++cnt;
        }
    }
    return cnt;
}

KM算法 带权的最大匹配

介绍

KM算法被用于求完备匹配下的最大权匹配，若不存在完备匹配，则会求权重最大的最大匹配，对于一个带权二分图G

其最大和为102

此算法通过给每一个顶点设置一个顶标，以将求最大权匹配的问题转化为求完备匹配的问题

令顶点Ai的顶标为A[i]，顶点Bj的顶标为B[j]，使得在算法执行过程中，对于任何一条边<i, j>， A[i] + B[j] ≥ weight[i][j]

---

相等子图

图G中，每一条边都具有左右两个顶标，相等子图即为边权重等于两个顶标和的边所构成的子图

KM算法的正确性基于以下定理：

若在二分图中，A[i] + B[j] ≥ weight[i][j]，并存在某个相等子图有完备匹配，则此完备匹配即为二分图的最大权匹配

---

对于图G，首先我们初始化图的顶标，使得A[i] = max(weight[i])，B[i] = 0

对于A中的每一个顶点，我们使用匈牙利算法在G的相等子图中找一条增广路，如果没有找到则修改顶标来扩大相等子图，继续寻找增广路，当每个点都找到增广路时，即找到了二分图的最佳匹配

此时，对于顶点A1我们找到一条增广路(A1, B3)，而对于顶点A2在相等子图中，找不到增广路径，此时则需要修改顶标来扩大相等子图，使左边一部分顶点的顶标减去d，右边一部分点的顶标加上d，那么：

• 哪些顶标需要修改
• d是多少

第一，哪些顶标需要修改：

在对当前顶点进行增广路搜索时，会产生一棵交错树，如下图中黄蓝交错标注

其中受影响顶点即为需要修改顶标的顶点（紫色标记）

第二，d是多少：

我们可以发现，将下图中标蓝的任何一条边加入相等子图后，便可找到一条增广路

KM算法选择上图三条边中顶标和与边权重之差最小值作为d，也就是说，将插入顶标与边权重差最小的边<A1, B1>或<A2, B1>，此时d = 1

经过修改操作之后，我们得到：

此时相等子图的范围被扩大，我们也可以找到A2的增广路径(A2, B3), (B3, A1), (A1, B1)了

相同的，继续执行以上的操作，直到我们的到最大权匹配，如下图

实现

tba