判断二分图#

一个图是二分图当且仅当这个图可以被2-染色，也就是图中不含奇数环

时间复杂度： $O(n)$

特点：无向图，图中可能存在重边和自环。

算法流程：

从前往后遍历每个结点，如果有结点未染色，则对其进行 dfs 判断 1.1 如果dfs判断其有奇数环，则说明该图不是二分图 dfs部分：参数：当前结点，当前结点颜色
1. 遍历与当前结点相连的结点 1.1 如果未被染色，则对其进行dfs染色，如果对其染色后存在奇数环，返回false 1.2 如果进行了然后，则判断当前结点和相连的结点的颜色是否一致，如果是则说明存在奇数环，返回false 1.3 如果上述情况都没有返回false，则返回true 代码如下：

1
int h[N], e[N << 1], ne[N << 1], idx = 0;
2
int st[N];
3

4
void add(int a, int b) {
5
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
6
}
7

8
// dfs 判断
9
bool dfs(int u, int c) {
10

11
    st[u] = c;
12
    for (int i = h[u]; ~i; i = ne[i]) {
13
        int v = e[i];
14
        if (!st[v]) {
15
            if (!dfs(v, 3 - c)) return false;
16
        } else if (st[v] == st[u]) return false;
17
    }
18
    return true;
19
}
20
// 有可能这个图不连通，所以需要每个都遍历
21
bool flag = true;
22
for (int i = 1; i <= n; i ++ )
23
    if (!st[i] && !dfs(i, 1)) {
24
        flag = false;
25
        break;
26
    }

二分图最大匹配#

匈牙利算法#

时间复杂度： $O(nm)$

特点：二分图，其中左半部包含 $n_1$ 个点（编号 1∼ $n_1$ ），右半部包含 $n_2$ 个点（编号 1∼ $n_2$ ），二分图共包含 $m$ 条边。

交替路：未匹配边 $\rightarrow$ 匹配边 $\rightarrow \cdots$ $\rightarrow$ 未匹配边这样的交替路径 增广路径：交替路的两端端点是未匹配点

二分图的最大匹配等价于当前匹配无增广路径

因此，我们的算法策略就是不断地寻找增广路径，算法流程如下：

对于某个未匹配的点 $v$ 来说，遍历其所有相邻点 $v$ 1.1 如果这个点没有被遍历过 2.1 如果这个点没有被匹配，则 $match[v] = u$ ，返回true 2.2 如果这个点有被匹配，那么继续去判断 $match[v]$ 开始的增广路径，如果找到了，也是将 $match[v] = u$ ，返回true
如果上述操作未能找到增广路径，则返回 false

注意：

在寻找增广路径的过程中，点遍历过了设置为 true，是否对后续没影响？是的，首先在寻找的过程中不应该找遍历过的点，然后如果当前点确实没找到增广路径，说明此处的匹配只能如此匹配，因此后边再遍历它也没有效果
找每个点的匹配时，要注意初始化 st 访问状态

代码如下：

1
const int N = 100010;
2

3
int h[N], e[N], ne[N], idx = 0;
4
int match[N];
5
bool st[N];
6

7
void add(int a, int b) {
8
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
9
}
10

11
bool find(int u) {
12

13
    for (int i = h[u]; ~i; i = ne[i]) {
14
        int v = e[i];
15
        if (!st[v]) {
16
            st[v] = true;
17
            if (!match[v] || find(match[v])) {
18
                match[v] = u;
19
                return true;
20
            }
21
        }
22
    }
23
    return false;
24
}
25

26
/*
27
寻找最大匹配
28
int res = 0;
29
for (int i = 1; i <= n1; i ++ ) {
30
    memset(st, false, sizeof st);
31
    if (find(i)) res ++ ;
32
}
33
/*

二分图匹配的必须边和可行边#

完备匹配#

完备匹配指的是二分图里的任意一个顶点都是匹配边相关联

那么，在完备匹配中，一条边 $(x,y)$ 是必须边，当且仅当同时满足以下条件：

在当前这个完备匹配下， $(x,y)$ 是匹配边
在当前这个完备匹配下，去掉 $(x,y)$ 这条边之后，不能再找一条增广路，其起点是 $x$ ，终点是 $y$

因此，对于完备匹配求必须边有个暴力的做法，就是先求一遍匈牙利算法得到完备匹配，然后枚举每一个匹配，将其删掉，再做一次求增广路，看是否能找到一条增广路，找不到说明这条边是必须边

在完备匹配中，一条边 $(x,y)$ 是可行边，当且仅当满足以下两个条件之一：

$(x,y)$ 当前是匹配边
$(x,y)$ 是非匹配边，设当前 $x$ 与 $u$ 匹配， $y$ 与 $v$ 匹配，连接边 $(x,y)$ 后，结点 $u,v$ 失配，因此必须找到一条从 $u$ 到 $v$ 的增广路，来保证最大匹配不变

那么，在一个完备匹配中判定所有的必须边和可行边有一个通用算法：

构造新的有向图：把非匹配边看作左部到右部的有向边，匹配边看作从右部到左部的有向边来构造新图。
求新图的强连通分量
$(x,y)$ 是原图的必须边，说明 $x,y$ 当前是匹配边，并且 $x,y$ 在新图中属于不同的强连通分量
$(x,y)$ 是原图的可行边， $(x,y)$ 当前匹配边或者 $x,y$ 两点在新图中属于相同的强连通分量

一般最大匹配#

那么，事与愿违，一般情况下，二分图的最大匹配大多是非完备匹配，那么这种情况下就需要借助 [[网络流]]

若 $z$ 是当前右部非匹配点， $(u,v)$ 是匹配边，则 $(z,T)$ 的容量为 $1$ ， $(v,T)$ 的反向边的容量一定是 $1$ 。因此，如果二分图中 $u$ 到 $z$ 有增广路，那么其残留网络上 $u$ 能到达 $z$ ，进而到达 $v$ ，即 $(u,v)$ 在一个强连通分量当中

因此，必须边的判定条件： $(x,y)$ 流量为 $1$ ，并且 $x, y$ 两点在残留网络中属于不同的强连通分量可行边的判定条件： $(x,y)$ 流量为 $1$ ，或者 $x,y$ 两点才残留网络中属于相同的强连通分量

最小点覆盖、最大独立集、最小路径点覆盖（最小路径重复点覆盖）#

最大匹配数=最小点覆盖=总点数-最大独立集=总点数-最小路径覆盖

最小点覆盖#

最小点覆盖：给你一个任意图，从中选出最少的点，使得每条边至少有一个端点是被选出来的。

![[]] 这里要加图

在二分图中，最小点覆盖是等于最大匹配数的

证明：设 $A$ 为最小点覆盖， $B$ 为最大匹配数，因此等价于证明 $A=B$ 先证明 $A \ge B$ 由于二分图中最大匹配数里面的边都是没有交点的，因此要想覆盖所有边，必然匹配里面所有点都至少要选上，因此 $A \ge B$

然后证明这个等号是可以成立的，通过构造方案来证明

求最大匹配
从左部每个非匹配点出发，做一遍增广标记所有经过的点左部所有未被标记的点 + 右部所有被标记的点就是一个最小点覆盖方案首先证明这个和是为最大匹配数，假设为 $m$
左部所有非匹配点一定被标记
右部所有非匹配点一定未被标记（否则为增广路，与最大匹配矛盾）、
对于匹配边，左右两点要么同时标记要么同时不被标记根据这三个性质，左部所有未被标记的点一定是匹配点，右部所有被标记的点也一定是匹配点，右部的匹配点可以分为有标记的和未被标记的，再根据第三条性质，选择点的数量一定是最大匹配数，同时也证明了匹配边一定被这些点覆盖。剩下的就是要证明
左部非匹配点 ---- 右部匹配点连接的边是否被覆盖
左部匹配点 ---- 右部非匹配点连接的边是否被覆盖
左部非匹配点 ---- 右部非匹配点连接的边是否被覆盖第三种情况与最大匹配数矛盾，因此不存在这种情况。第一种情况，由于我们是从左部非匹配点出发，那么和右部匹配点连接的边一定是被标记的，而由于我们选择了右部所有被标记的点，因此这样的边能被覆盖。第二种情况，由于又不非匹配点一定是未被标记的，因此其连接的左部匹配点一定也未被标记，因为标记的过程从未匹配点出发，最后也能够到非匹配点，这样的话会有增广路径，这与最大匹配不符。因此，这样的左部匹配点一定是未被标记的，由于左部选择的是未被标记的匹配点，因此，这样的边也能覆盖。

综上：二分图中，最小点覆盖=最大匹配数。

最大独立集#

最大独立集：从一个任意图中，选出最多的点，使得选出的点之间没有边最大团：从一个任意图中，选出最多的点，任意两点之间都有边补图：在图论中，一个图的补图是一个图跟图 $G$ 有相同的点，而且这些点之间有边相连当且仅当在 $G$ 里面他们没有边相连。因此，独立集的补图就是团

在二分图中，求最大独立集 $\iff$ 去掉最少的点将所有边都破坏掉 $\iff$ 找最小点覆盖 $\iff$ 找最大匹配数

最小路径点覆盖#

最小路径点覆盖：简称最小路径覆盖，针对有向无环图来说，用最少的互不相交的路径（路径里点不重复）将所有点覆盖，求最少路径数

思路：拆点假设原图中有 $1-n$ 个点，设置 $1^\prime - n^\prime$ 个新点， $(i,j)$ 的边变成 $(i, j^\prime)$ ，这样整个图就变成了一个二分图。最后，原图最小路径覆盖就是 $n - m$ ，其中 $m$ 为新图的最大匹配数。

证明首先来看在原图中的每条路径，转化到新图中是怎么样子的，比如： $a->b->c$ 。由于在一个路径点覆盖的方案当中，每个点都只出现一次，然后一定每个点都出现，因此，路径上的每个点在新图中每个点最多一个入度和一个出度。对于只有出度没有入度的点，说明是路径起点；只有入度没有出度的点，说明是路径终点，因此下面的等价关系正确。

原图中的路径 $\iff$ 新图匹配边
原图中的路径终点 $\iff$ 新图左部非匹配点因此，求最少路径数也可以说是求最少路径终点数 $\iff$ 求最少左部非匹配点数 $\iff$ 求左部最大匹配点数 $\iff$ 找最大匹配数

最小路径重复点覆盖#

如果在最小路径点覆盖的基础上放开限制，也即是说点和边是可以相交的，那么将所有点覆盖的路径数是多少？

思路：

求传递闭包 $G^\prime$
在 $G^\prime$ 上求最小路径覆盖证明思路就是两个集合是等价的，或者说可以转化原图所有的最小路径重复点覆盖集合 $\iff$ 新图所有最小路径点覆盖集合

对于任意的最小路径重复点覆盖集合，这样的集合一定是多条路径组合成，第一条路径不考虑，如果第 $i(i>1)$ 条路径上有之前重复的点，我们就将其跳过，如果是起点重复，起点就不考虑，不可能有一条路径所有点都被遍历过，否则这条路径有不有都无所谓，也不满足最小的限制。因此，对于原图中的任意最小路径重复点覆盖集合，都可以变成新图中最小路径覆盖集合。

而对于新图中所有最小路径点覆盖集合，也一定是有多条路径存在，那么可以查看路径中每条边，如果这条边在原图中并不存在，则还原成原图中的路径即可，因为是传递闭包，一定至少有一条路径，由于新图的最小路径点覆盖集合本质上已经覆盖了所有点，因此，对于还原的新边也只会出现重复出现的点，从而是满足要求的。

应用#

DAG 上的一个点集，任意两点之间无路径，求这个点集最多的点的数量