【学习笔记】二分图

_RainCappuccino_ · 2023-07-05 20:29:55 · 个人记录

First. 定义

万事都先需了解定义

简单来说，二分图（二部图）就是一种满足以下性质的图：

点集 V 的两个不相交子集 X 和 Y 可以组成这个图，且两个子集中，同集合的点之间没有任何边连接。
将两集合一个染黑，一个染白，每条边一定连接着一黑一白点。

Second. 判定

如果判断不出一个图是否为二分图，就不能使用二分图的性质了。

Part.1 染色法

随便选取一个节点，将其染成黑色，接着将与它相连的点染成相反的颜色，如果出现了染色覆盖，那么此图不为二分图。

Part.2 判奇环

使用bfs或dfs扫一遍图，如果存在奇环则不为二分图。

由性质三易证

Third.应用

Part.1 二分图最大匹配

肥肠重要，根本的根本，几乎所有二分图的题都会用到

最大匹配顾名思义就是最大的匹配，那什么是匹配呢？

接下来需要引入\mathsf{\color{#16b1b8}{匹配}} 的定义：

在图论中，假设图 G=(V,E)，其中 V 是点集，E 是边集。
一组两两没有公共点的边集 (M(M\in E)) 称为这张图的匹配。
定义匹配的大小为其中边的数量 |M|，其中边数最大的 M 为 最大匹配。
当图中的边带权的时候，边权和最大的为 最大权匹配。
匹配中的边称为 匹配边，反之称为 未匹配边。

而 二分图最大匹配就是二分图中，边数最大的匹配。

Algorithm.1 匈牙利算法

对于这个算法，我们还要引入一个概念：

\text 增广路（augmenting path）

对于一条由未匹配边、匹配边交错组成，且一未匹配边为始、未匹配边为终的路径即为 \mathsf{ \color{blue} {增广路}}。

由于增广路未匹配边一定比匹配边多 1，所以每次将增广路上的未匹配边与匹配边互换，匹配边就多了一。

由此可以得到，一直去寻找\mathsf{ \color{blue} {增广路直到找不到时}}，即为求得最大匹配。

Code

int link[MAXN];//储存匹配边
bool road[MAXN];//标记是否走过
bool find(int x){
    for(auto i:G[x]){
        if(!road[i]){
            road[i] = 1;
            if(link[i] == 0||find(link[i])){//增广路交替的样子体现在这里
                link[i] = x;
                return true;
            }
        }
    }
    return false;
}
int find_max(){
    int ans = 0; 
    For(i,1,n){
        For(i,1,m) road[i] = 0;
        if(find(i)) ans ++;
    }
    return ans;
}

Algorithm.2 Dinic

~~还没学呢~~

Part.2 二分图最小点覆盖

定义：选最少的点，满足每条边至少有一个端点被选

我们需要引入一个定理：König 定理

一个二分图的最大匹配数等于这个图的最小点覆盖数。证明

所以我们只需要求出最大匹配数就能得到最小点覆盖数。

NKOJ P1524 柯南开锁

Part.3 二分图的最小路径覆盖

定义：在图中找一些路径，这些路径覆盖图中所有的顶点，且路径间无交点

二分图最小路径覆盖=顶点总数 V - 最大匹配

证明：一开始，每个点单独为一条路径，然后，每条匹配边会连接两条路径，且路径上的点不会重复。所以，最小路径覆盖数即为 DAG 顶点数 - 二分图最大匹配数。

Part.4 DAG 的最小路径覆盖

将每个点 u 拆成 u_1, u_2，一个只出，一个只入，然后就构成了一个二分图。

此时该顶点数 - 二分图的最大匹配数即为该 DAG 的最小路径覆盖数。

Part.5 最大独立集

定义：图中一个最大的子集满足集合中任意两点没有连边。

最大独立集 =n - 最小点覆盖。

证明：取反，任意两点间不存在边，又由于原点集最小，所以补集最大。

Part.6 带交点的最小路径覆盖

首先，Floyd 传递闭包，重新建图，转化为无交点的最小路径覆盖

二分图的解题方式

First. 寻

我们需要在题目中找出什么是 X 集，什么是 Y 集。

EG.1
NKOJ P2092 魏
此题的 X 集不再是一个点，而是一条边，也就是曹操每次走的路径，而 Y 集就是郭嘉的任务点。

Second. 建

寻找 X 集 Y 集的关系，进行连边。

EG.2

P1963 [NOI2009] 变换序列 - 洛谷
此题需要通过距离 Dis 以及 Dis 的计算公式来建立 i 与 T_i 之间的关系，连接出4条边。

Third. 判

判断此题为什么类型（最小点覆盖、最大匹配、最小路径覆盖），代入公式计算。

个人见解

我认为以上三个步骤中哪一步都不能少，其中有一些题目“寻”很难，比如：
P1263 [CEOI2002] Royal guards - 洛谷

它需要将连通的空地视为一块，将横列纵列分别标号，将纵列与横列相交的地方是空地的地方连边。