DDOSvoid's Blog

二分图

发表于 更新于 分类于
本文字数： 5.9k 阅读时长 ≈ 5 分钟

简介

定义：简而言之，就是顶点集 $V$ 可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻

无向图 $G$ 为二分图的充分必要条件是，$G$ 至少有两个顶点，且其所有回路的长度均为偶数

一下为了方便，令 $X$ 为左边的点集，$Y$ 为右边的点集

二分图判定

定理：一张图是二分图，当且仅当该图中不存在奇环

实际上的判断只需要 $dfs$ 黑白染色即可

1
2
3
4
5
6
7
8
9
int vis[maxn];
bool dfs(int u, int d) {
    vis[u] = d;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (vis[v] == d) return 0;
        if (vis[v] == -1 && !dfs(v, d ^ 1)) return 0;
    }
    return 1; 
}

二分图最大匹配

最大匹配

大概就是选取最多的边，使得任意两条边没有交点

增广路

存在在当前匹配中的边为匹配边

匹配边两端的端点为匹配点

增广路是指一条路径，在路径上匹配边和非匹配边交替出现，且路径的开始和结束都是非匹配边

增广路的性质：

  1. 长度为奇数
  2. 将增广路上的边取反，即匹配边变成非匹配边，非匹配边变成匹配边，得到匹配仍然合法，且匹配的边数增加了 $1$

定理：二分图的一组匹配 $S$ 是最大匹配，当且仅当图中不含有 $S$ 的增广路

匈牙利算法

其实就是找增广路，然后取反，直到不存在增广路

时间复杂度为 $O(n\cdot e+m)$，其中 $m$ 为右部点的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 1010
#define maxm 50010
using namespace std;

int n, m, k;

struct Edge {
    int to, next;
} e[maxm * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int I, vis[maxn], g[maxn];
bool dfs(int u) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (vis[v] == I) continue;
        vis[v] = I; if (!g[v] || dfs(g[v])) return g[v] = u, 1;
    } return 0; 
}

int ans;
int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= k; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y + n); add_edge(y + n, x);
    }
    for (int i = 1; i <= n; ++i) vis[i] = ++I, ans += dfs(i);
    cout << ans << "\n"; 
    return 0;
}

其它匹配

完美匹配：

DAG 的最小路径覆盖

我们考虑将 $DAG$ 变成一个奇怪的二分图，对于原图中的有向边，$u$ 连 $v’$

然后我们考虑这张二分图的一条匹配，匹配中的每一条边都意味着原图两个路径并到了一起，即总路径数减一

所以我们要让匹配尽量大，也就是求最大匹配

二分图最大匹配必须点

如果一个点在二分图的所有最大匹配上都是匹配点，则该点是最大匹配必须点

反之如果一个点在至少一个最大匹配上不是匹配点，则该点是最大匹配非必须点

我们考虑如何求解非必须点，首先先用 $dinic$ 跑一个最大匹配出来

然后我们从 $s$ 出发，只走还没留满的边，所有能够到达的左部的点都是非必须点，右边同理

正确性的话，以从 $s$ 出发为例，从 $s$ 走到的第一个点一定是非匹配点，再走一步，则一定是沿着非匹配边走到右边的点，如果能从右边走回来的话，则一定是走的匹配边的反向边

也就是说我们从左部出发回到左部的路径都是形如：匹配边-非匹配边-匹配边-非匹配边……

且长度为偶数，说明如果我们将这些路径取反，还是一个最大匹配，则这个路径上的左部点都是非必须点

实现大概如下

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> ans; bool vis[maxn]; int bl[maxn]; // bl[u] = 0 是左部点，bl[u] = 1 是右部点
void Dfs(int u, int f) {
    vis[u] = 1; 
    if (bl[u] ^ f) ans.push_back(u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (w == f && !vis[v]) Dfs(v, f);
    }
} 

int main() { 
	Dfs(s, 1); Dfs(t, 0);
}

二分图最大权完美匹配

KM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#define ll long long
#define maxn 510
#define INF 100000000000000000
using namespace std;
 
int n, m;

ll a[maxn][maxn];

ll lx[maxn], ly[maxn], slack[maxn];
bool vis[maxn]; int g[maxn], pre[maxn];
void bfs(int u) {
    int x, y = 0, py = 0; g[y] = u;
    fill(pre, pre + maxn, 0);
    fill(slack, slack + maxn, INF);
    do {
        x = g[y]; vis[y] = 1; ll d = INF; 
        for (int i = 1; i <= n; ++i) {
            if (vis[i]) continue; 
            if (slack[i] > lx[x] + ly[i] - a[x][i])
                slack[i] = lx[x] + ly[i] - a[x][i], pre[i] = y;
            if (slack[i] < d) d = slack[i], py = i;
        }
        for (int i = 0; i <= n; ++i)
            if (vis[i]) lx[g[i]] -= d, ly[i] += d;
            else slack[i] -= d;
        y = py;
    } while (g[y]);
    while (y) g[y] = g[pre[y]], y = pre[y];
}

ll KM() {
    for (int i = 1; i <= n; ++i) g[i] = lx[i] = ly[i] = 0;
    for (int i = 1; i <= n; ++i) fill(vis, vis + maxn, 0), bfs(i);
    ll ans = 0;  
    for (int i = 1; i <= n; ++i) ans += a[g[i]][i];
    return ans;
}

 
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) a[i][j] = -INF;
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        a[x][y] = z; 
    } cout << KM() << "\n";
    for (int i = 1; i <= n; ++i) cout << g[i] << " \n"[i == n];
    return 0;
}

二分图最小点覆盖

在二分图中，选取最少的点，使得每条边至少有一个端点在所选的点集中

一个重要的定理： 二分图最小点覆盖 = 二分图最大匹配

证明：

不妨令 $m$ 表示二分图最大匹配的边数

  1. 至少需要 $m$ 个点

    因为最大匹配的 $m$ 条边两两无公共点，所以至少要选 $m$ 个点来覆盖它们

  2. 至多需要 $m$ 个点

    我们选择最大匹配的 $m$ 条边中每条边的两个端点中的一个

    如果还存在某一条边没有被覆盖，那么这条边一定可以加入到最大匹配中，矛盾

二分图最小点权覆盖

我们考虑网络流

建图：

原图中的边，$u$ 连 $v$，容量为 $\infty$

$s$ 连 $u$，容量为 $a[u]$

$v$ 连 $t$，容量为 $a[v]$

求最小割即可

例题

  1. Luogu P7368 [USACO05NOV]Asteroids G

二分图最小边覆盖

在二分图中，选取最少的边，使得每个点都至少是其中一个边的端点

为了保证一定存在边覆盖，我们定义如果一个点没有向外的连边，则可以选择这个点

又一个重要的定理：二分图最小边覆盖 = n - 二分图最小点覆盖 = n - 二分图最大匹配

证明：

不妨令 $m$ 为二分图最大匹配的边数

注意到一条边至多只能覆盖两个点，所以我们只需要选取最多的能覆盖两条边的即可

那么一定选取最大匹配的 $m$ 条边，剩下的 $n-2m$ 个点我们只能每次用一条边覆盖一个点

所以总共为 $n-m$

二分图最大独立集

在二分图中，包含点数最多的一组独立集为二分图的最大独立集

另一种重要的定理： 二分图最大独立集 = n - 二分图最小点覆盖 = n - 二分图最大匹配

证明：

将任何一个点覆盖去掉之后，剩下的点都构成了一个独立集，且一一对应

所以最大独立集就等于总点数减去最小点覆盖

二分图最大点权独立集

二分图最大点权独立集 = 点权和 - 最小点权覆盖

二分图最小边染色

首先我们能够简单猜测答案一定是所有点的最大度数

我们考虑如何构造，下面给出一个没有证明的构造

我们依次考虑每条边的颜色，不妨假设我们现在正在考虑的边为 $(u,v)$

我们令 $lu$ 为以点 $u$ 为端点的边集中还没有使用过的颜色的编号的最小值，$lv$ 同理

若 $lu=lv$，则我们将这条边的颜色定为 $lu$
若 $lu>lv$，则我们从 $u$ 开始 $dfs$ 找一条 $lu,lv,lu,\cdots$ 的路径，然后反色即可

注意到一定能找到这样的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>
#define maxn 1010
#define maxm 2010
#define ll long long
using namespace std;

int n, m;

struct Edge {
    int fr, to, next;
} e[maxm * 2]; int c1, head[maxn], du[maxn];
inline void add_edge(int u, int v) {
    e[c1].fr = u; e[c1].to = v;
    e[c1].next = head[u]; head[u] = c1++;
}

int col[maxn][maxn], ans[maxm];
void change(int u, int x, int y) {
    if (col[u][x] == -1) return col[u][y] = -1, void(); 
    int i = col[u][x], v = e[i].to;
    change(v, y, x);
    ans[i / 2 + 1] = y;
    col[u][y] = i; col[v][y] = i ^ 1;
} 

int main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
        ++du[x]; ++du[y]; 
    } fill(col[0], col[0] + maxn * maxn, -1); 
    for (int o = 0; o < c1; o += 2) {
        if (ans[o / 2 + 1]) continue; 
        int u = e[o].fr, v = e[o].to, lu = n, lv = n, l; 
        for (int i = n; i; --i) {
            if (col[u][i] == -1) lu = i;
            if (col[v][i] == -1) lv = i;
        }
        if (lu < lv) change(v, lu, lv);
        else if (lu > lv) change(u, lv, lu);
        l = min(lu, lv);
        ans[o / 2 + 1] = l;
        col[u][l] = o; col[v][l] = o ^ 1; 
    }
    cout << *max_element(du + 1, du + n + 1) << "\n"; 
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n"; 
    return 0; 
}

Hall 定理

令左部点为 $X$，右部点为 $Y$，不妨令 $|X|<|Y|$

定义 $M(X)$ 为与 $X$ 相连的点的点集

Hall 定理：一个二分图存在完美匹配的充要条件是对于任意一个 $x\subseteq X$，都有 $|M(x)|\ge |x|$

证明：

  1. 必要性

    显然，如果连出去的点数都不足 $x$，那么一定不能构成完美匹配

  2. 充分性

    假设存在一个满足 $Hall$ 定理的二分图，且没有完美匹配

    坑