二分图的最小顶点覆盖 最大独立集 最大团

二分图的最小顶点覆盖 最大独立集 最大团

重要结论写在最前面：

一、二分图的最小顶点覆盖

定义：假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。

方法： 最小顶点覆盖等于二分图的最大匹配

我们用二分图来构造最小顶点覆盖。

对于上面这个二分图，顶点分为左右两个集合，\(X\)集合包含\((1,2,3,4)\)，\(Y\)集合包含\((5,6,7,8,9)\),假如现在我们已经找到一个最大匹配\(M\) ，就是上面的红线所标注的\(M=\{(1,7),(2,5),(4,8)\}\)。

作如下定义：

• 定义\(1、2、4、5、7、8\)为已经匹配过的点，其他点为未匹配的点
• 定义\((4,8)、(1,7)、(2,5)\)为已匹配的边，其他边为未匹配的边

下面我们从\(Y\)集合中找出未匹配的点，就是上面标记的\(6\)和\(9\)。每次我们从右边选出一个未匹配的点，从该点出发， 做一条

未匹配边->匹配边->未匹配边->……->匹配边（注意最后以匹配边结尾），并且标记用到的点

得到下图：

其中紫色的边为我们刚才画的边，其中标记的点有\(2、4、5、6、8、9\)。 上图的两条路为：

• \(9->4->8->2->5\)
• \(6->2->5\)

这两条路都是 未匹配边->匹配边->未匹配边->……->匹配边

注意:如果一个右侧未匹配点有多条边，那么这样的从该点开始的路径就有多条，上面的\(6\)和\(9\)都只有一条边，所以从每个点开始的这样的路径只有一条。

现在我们将 左侧标记的点 \(2、4\)和 右侧未标记的点 \(7\)选出组成集合\(S\)， 那个\(S\)就是一个最小顶点覆盖集，就是\(S\)集合可以覆盖所有的边。

注：形象的解释就是从\((2,4,7)\)出发，可以到达点集中所有的点。

下面 证明：

（1）\(|S|=M\)，即 最小顶点覆盖等于二分图最大匹配

• 左边标记的点全都为匹配边的顶点，因为我们构造路径的时候左边的点向右找的边都是最大匹配的边

解释：未匹配边->匹配边，都是这样构建的，所以，左边标记的点当然都是匹配边的顶点。

• 右边未标记的点也为二分图最大匹配边的顶点,而且左边标记的加上有边未标记的正好是最大匹配的数目

（2）\(S\)能覆盖所有的边。所有的边可以分为下面三种情况：

• ① 左端点标记、右端点标记；这些边一定被左侧标记的点覆盖，比如上面的\(2\),\(4\)
• ② 右端点未标记；这些边一定被右侧未标记的点覆盖，比如上面的\(7\)
• ③ 左端点未标记、右端点标记。

下面我们证明 ③ 这种边压根就不会存在：若\(c\)是最大匹配中的边，由于右端点不可能是一条路径的起点（因为我们的起点都是从\(Y\)集合中未匹配的点开始的），于是右端点的标记只能是在构造中从左边连过来，这是左端点必定被标记了，这时\(c\)就转化成了\(a\)；若\(c\)属于未匹配边，那么左端点必定是一个匹配点，那么\(c\)的右端点必定是一条路径的起始点，因此\(c\)的左端点也会成为一条路径的第二个点而被标记，这时\(c\)也就成了\(a\)。所以\(c\)这种边肯定是不存在的。

（3）\(S\)是最小的顶点集：因为最大匹配为\(M\)，而\(|S|=M\)，所以如果\(S\)中的点再少，那么连\(M\)个匹配的边都不能覆盖。

三、二分图的最大独立集

定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。

方法： 最大独立集 = 所有顶点数 - 最小顶点覆盖

在上面这个图中最小顶点覆盖=\(3\)，即\(2,4,7\)构成最小顶点覆盖，则其他点\(6\)个构成最大独立集。且其他点不可能相连。假设其他点相连则这条边必定没有被\(2,4,7\) 覆盖，与\(2,4,7\)是最小顶点覆盖矛盾。因此其他点之间必定没有边。而\(2,4,7\)是最小顶点覆盖，所谓最小就是不能再小了，因此我们的独立集就是最大了。

四、二分图的最大团

定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说，我们默认为左边的所有点之间都有边，右边的所有顶点之间都有边。那么，实际上，我们是要在左边找到一个顶点子集\(X\)，在右边找到一个顶点子集\(Y\)，使得\(X\)中每个顶点和\(Y\)中每个顶点之间都有边。

方法： 二分图的最大团=补图的最大独立集

补图的定义是：对于二分图中左边一点\(x\)和右边一点\(y\)，若\(x\)和\(y\)之间有边，那么在补图中没有，否则有。

这个方法很好理解，因为最大独立集是两两不相邻，所以最大独立集的补图两两相邻。

五、练习题

【\(HDU1151\)】—\(Air\) \(Raid\)（最小路径覆盖）

• 题解描述
  给定一个\(DAG\)（有向无环图），选定最少的点，使得从这些点出发可以覆盖每一条路径(即每个点都经过至少一遍)。

输入：

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

输出

2
1

以测试数据为例，\(4\)个路口，\(3\)条路。现派伞兵经过所有路口，求最少要派几名。

思路：

首先构建二分图，图的左边代表\(1-n\)，右边也代表\(1'-n'\)，若两点\(i->j'\)可行，则二分图中建边\(i->j'\),求最少路径覆盖即为求最大独立集，也就是\(n-\)最大匹配数。

解释:
在二分图中，最小路径覆盖和最大独立集是等价的。
二分图是指一个图的顶点可以分为两个不相交的集合，并且图中的每条边都连接一个集合中的顶点和另一个集合中的顶点。
在二分图中，最小路径覆盖的解可以直接对应到最大独立集的解，反之亦然。具体来说，对于二分图中的最小路径覆盖问题，我们可以将其转化为最大独立集问题求解。而对于二分图中的最大独立集问题，我们也可以将其转化为最小路径覆盖问题求解。
这个等价关系的原因是，二分图的最大独立集正好对应着最小路径覆盖中选择的路径的起点和终点集合。因为在二分图中，任意两个相邻的顶点之间都没有边相连，所以选择一个顶点就意味着不选择与之相邻的顶点。

结论：二分图中最少路径覆盖即为最大独立集

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
/*
测试用例：
2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

答案：
2
1
*/
int match[N];
int st[N], g[N][N];
int n, m;

int dfs(int x) {
    for (int i = 1; i <= n; i++) {
        if (g[x][i] && !st[i]) {
            st[i] = 1;
            int t = match[i];
            if (t == -1 || dfs(t)) {
                match[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    int T;
    cin >> T; // T组测试数据
    while (T--) {
        cin >> n >> m; // n个节点,m条边
        // 多组测试数据
        memset(match, -1, sizeof match);
        memset(g, 0, sizeof g);

        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            g[a][b] = 1; // a->b,有向图
        }

        // 如果a->b,b->c,则 a->c,题意中说如果存在传递关系，需要我们建立关系清晰的边，也就是，
        // 用 floyd,在O(N^3)的复杂度下完善点点之间的边关系
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    g[i][j] |= g[i][k] & g[k][j];

        // 新图建成，开始跑匈牙利算法，求二分图的最大匹配
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            memset(st, 0, sizeof st);
            if (dfs(i)) cnt++;
        }
        // 二分图的最小点覆盖 = n- 二分图的最大匹配
        printf("%d\n", n - cnt);
    }
    return 0;
}

http://poj.org/problem?id=2594