这篇文章上次修改于 365 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记6——二分图匹配

前置定义

二分图(Bipartite Graph )：如果一个图的顶点可以分为两个集合X和Y，图的所有边连接的两个点都来自不同的集合，则称该图为“二分图”或“二部图”。

最大匹配问题

对于一个二分图，问最多可以有几对边连接的点，并且这些点不重复。

说的形象一点，类似于婚配问题，将所有人分为男女两组，告诉你哪些人互相匹配（A能接受B，B必定接受A），问最多可以配成几对。

这就是一个典型的最大匹配，对于结果我们成为最大匹配对数

匈牙利算法

通过最简单的思路来看，我们就从上往下进行判断

操作A(x)判断这位男性x可以匹配的对象中有没有未被匹配的。若有则匹配，并进行A(x的下一位)：若无

判断x连接的已被匹配的女性y，y对应匹配男性为z，判断z是否可以取消该匹配获得新匹配（即操作A(z)），若能，则匹配，若不能，则x无法被匹配。

范例代码：

#include <bits/stdc++.h>
using namespace std;

int findMaximumMatching(const vector<vector<int>> & adj, const function<bool(int)> & onLeft){
    int result = 0;
    vector<int> linked(adj.size(), -1); // linked[i] 值为 j 意为对于右点i，其连接为j
    vector<bool> visited(adj.size());
    
    function<bool(int)> dfs = [&](int u){
        for(int v:adj[u]){
            if(visited[v]) continue;
            visited[v] = true;
            if(linked[v]==-1||dfs(linked[v])){
                linked[v] = u;
                return true;
            }
        }
        return false;
    };
    
    for(int i = 0; i < adj.size(); i++){
        if(not onLeft(i)) continue;
        fill(visited.begin(), visited.end(), false);
        if(dfs(i)) result++;
    }
    return result;
}

最小顶点覆盖

覆盖：当一个边连接到某个点，可以说为该边被该点覆盖

给一副二分图，问该图最少被几个点覆盖？

该结果我们称为最小顶点覆盖。对于最小顶点覆盖，不妨先寻找它和最大匹配对数的关系

证明：最大匹配对数 = 最小顶点覆盖

要证明两者相等，不妨先得出

最小顶点覆盖A >= 最大匹配对数B：

对于最大匹配，暂时去掉所有除了匹配边之外的边，剩余B条边，这B条边都由两个点覆盖，又因为所有的边都要被覆盖，这B条边只能被它的两端的某个点覆盖，这些点不会重复，所以为了覆盖这B条边，至少需要B个点，可得A >= B。

最小顶点覆盖A <= 最大匹配对数B

对于最小顶点覆盖的A个点，去掉其它的所有点，剩下的每个点都有一个特性——每个点的所有边中至少有一个边另一端是空的，利用反证法，若某个点的所有边中都有它的另一端，那么该点可以被删除而不被纳入最小顶点覆盖。得证。然后对于最小覆盖的每个点，它和另一端空的边必能形成一个匹配，故B >= A

根据以上得证！

最小定点覆盖题就被转化为最大匹配问题

DAG图的最小路径覆盖

用尽量少的不相交简单路径覆盖有向无环图(DAG) 的所有顶点，这就是——DAG图的最小路径覆盖问题。

路径覆盖问题的目标是选择尽可能少的路径，以覆盖图中的所有节点。这些路径不能相交，除非它们共享一个起点或终点。

对于图

graph LR
1((1))
2((2))
3((3))
4((4))
1 --> 3
2 --> 3
3 --> 4

可见只需选择点1， 2便可覆盖所有点

变化思考

graph TD
1((1))
2((2))
3((3))
4((4))

5((1'))
6((2'))
7((3'))
8((4'))

1 --> 7
2 --> 7
3 --> 8

由于是有向图，我们应当思考如何转化为无向图问题，对于有向，我们可以让每个点都获得它的复制体，并且总是复制体被指向，原来的点指出。

结论：

最小路径覆盖数=节点数(n)-最大匹配数(m)

证明：

一开始每个点都是一条路径，每次找一条匹配边，代表合并两条路径

由于路径不相交（即每个点的入度和出度至少有一个为1），所以二分图上的边也不相交（如果相交则说明某个点的入度或出度大于1），这正好是匹配的定义

每条匹配边代表答案减去1，所以最小路径覆盖=原图节点数-新图最大匹配数

int findMinimumPathCover(const vector<vector<int>> & adj){
    int maximumMatching = 0;
    int nodeNum = adj.size();
    vector<int> linked(nodeNum, -1); // linked[i] 值为 j 意为对于右点i，其连接为j
    vector<bool> visited(nodeNum);
    
    function<bool(int)> dfs = [&](int u){
        for(int v:adj[u]){
            if(visited[v]) continue;
            visited[v] = true;
            if(linked[v]==-1 or dfs(linked[v])){
                linked[v] = u;
                return true;
            }
        }
        return false;
    };
    
    for(int i = 0; i < adj.size(); i++){
        fill(visited.begin(), visited.end(), false);
        if(dfs(i)) maximumMatching++;
    }
    return nodeNum - maximumMatching;
}

最大独立集

二分图的最大独立集是指在一个二分图中选择最大数量的节点，使得这些节点之间没有直接相连的边。

独立集： 一个图的独立集是指图中的一组节点，其中任意两个节点之间没有直接相连的边。
最大独立集： 对于给定的图，最大独立集是指具有最大节点数的独立集。

结论：

二分图最大独立集 = 节点数(n) - 二分图最大匹配

证明：

去掉二分图的最小点覆盖，剩下的点就是一个独立集，添加任意一个最小点覆盖中的点，依据之前的定理：最小点覆盖的每个点都有一个特性——每个点的所有边中至少有一个边另一端是空的，然而这个空的点就属于我们剩下的独立集，也就是说，添加任意一个最小点覆盖中的点，都会导致生成一条边，故：二分图最大独立集 = 节点数(n) - 二分图最小点覆盖 = 节点数(n) - 二分图最大匹配

进阶参考

Mai Icy