二分图
2026-03-31
简介
二分图是指,可以将所有点分为两个点集,使得对于每条边的两个点属于不同的点集。
与此同时,还有两个个等价关系:一个图是二分图等价于图中不存在奇数环等价于染色法中不存在矛盾。
证明
我们先来证明图中不存在奇数环等价于染色法中不存在矛盾。
先证充分性,考虑反证法,假设图中不存在奇数环且染色法出现了矛盾,设矛盾点为 u 和 v,它们颜色相同且有一条连边,显然,将这条边删掉以后剩余的图一定有一条路径能将它们相连,且这个路径有偶数条边,加上 u 和 v 之间的边,我们构造了一个奇数环,矛盾。
再证必要性,考虑反证法,假设染色法没有矛盾且存在奇数环,显然这个环上一个点一定能绕一圈走回自己且颜色不同,矛盾。
然后证明上面两个等价于一个图是二分图。
先证充分性,由于染色法没有矛盾,因此所有黑色点都只连向白色点,白色点也只连向黑色点,因此可以直接把黑色放一起,白色放一起即可,此时图是一个二分图。
再证必要性,考虑反证法,假设图为二分图且图中存在奇数环,显然从这个环上一个点出发,与之相连的点应在另一个集合,到最后两个相邻点在同一集合,矛盾。
综上所述,一个图是二分图等价于图中不存在奇数环等价于染色法中不存在矛盾。
例题
Acwing 257. 关押罪犯
题目要求将原图分为两个部分,使得每个部分内部的边权的最大值最小。
考虑二分答案 mid,显然只需要对所有 >mid 的边进行染色,看有无冲突即可。
匈牙利算法
月老算法
匈牙利算法主要思想为:当前匹配是最大匹配当且仅当没有增广路。
最大匹配数:在一个图中,最大匹配(所含点数可能不同)的数量。
最小点覆盖:在二分图的所有点中选出最少的点,使得每条边的两端至少有一个被选中的点。
有一个结论:在二分图中,最小点覆盖等于最大匹配数。
证明
先证最小点覆盖 ≥ 最大匹配数。
对于每个最大匹配,显然两个匹配之间没有公共点,所以至少需要选择一个点,即最小点覆盖。
再证最小点覆盖 ≤ 最大匹配数。
考虑构造,首先跑一遍最大匹配,然后对于左边所有不在最大匹配中的点做增广路径并标记经过的点(显然,增广不会成功),然后,左边所有未被选中和右边所有被选中的点就是一个合法构造。
构造合法证明
显然,有以下几点:
- 左边的所有非匹配点一定被标记。
- 右边的所有非匹配点一定没被标记。
- 对于匹配边,它的两端要么都被标记要么都不被标记。
对于这一条,由于所有匹配边的右端被标记,左端也一定会被标记,反之亦然。
这个时候,左边没被标记的一定是匹配点,右边被标记的一定是匹配点。
这也就证明了我们选择的点一定是匹配边的两端,显然,此时所有匹配边如果两端都被标记,就会选择右边;如果都没被标记,就会选择左边。
还有两种情况:
- 左边是非匹配点,右边是匹配点。
显然此时会选择右边的点。 - 左边是匹配点,右边是非匹配点。
显然,如果左边被选择右边也一定会被选择(第二条性质),所以左边没被选择,也就是在构造里。
最大独立集:选出最多的点,使得它们两两之间没有连边。
最大团:选出最多的点,使得它们两两之间都有边。
容易发现,最大独立集相当于去掉最少的点将所有边破坏掉,也就相当于求最小点覆盖,也就是最大匹配数。也就是说,如果去掉 m 个点,则最大独立集即为 n−m。
最小路径点覆盖(最小路径覆盖):在 DAG 中,选出最少的互不相交的边覆盖所有点。
这个问题的传统解法是进行拆点,具体的,将原先 n 个点拆成 1,2,⋯,n 和 1′,2′,⋯,n′,将每个边 u→v 变为 u↔v′(没错,变成了无向边)。容易发现,这个新图 G′ 是一个二分图,原问题答案就是 n 减去 G′ 的最大匹配数。
证明
容易发现,原图的每一个路径一定是新图的一个匹配,则这个路径的终点一定是新图左侧的非匹配点。
也就是说,原图不相交路径最少等价于新图左侧非匹配点最少,也可以求左侧匹配点最多,也就是最大匹配数。
最小路径重复点覆盖:在 DAG 中,选出最少的边覆盖所有点。
这个问题其实是最小路径点覆盖的扩展,具体做法:先求原图的传递闭包(将所有点能到达的点的连边补满),然后求传递闭包的最小路径点覆盖。
证明
令原图的最小路径重复点覆盖为 G,新图的最小路径点覆盖为 G′。
从最小路径重复点覆盖到最小路径点覆盖:将原图可重复点覆盖的边一一取出来看,首先,第一条边不看;然后,将第二条边和第一条边相同的点直接跳过(传递闭包的性质允许我们这样做);依此类推,最终会发现原图的最小重复路径点覆盖的边可以转换为新图的最小路径点覆盖。
显然,一定不存在全部被覆盖过的边,如果存在的话可以将其删去来达到最小路径重复点覆盖。
从最小路径点覆盖到最小路径重复点覆盖:显然,我们可以将所有传递闭包增加的边还原回去,这样就是最小路径重复点覆盖。
例题
Acwing 372. 棋盘覆盖
网格图是一个常见的二分图(考虑棋盘一样黑白染色,一定是个二分图)。
显然,我们可以将每个相邻网格两两连边,放最多卡片等价于取最多的边使其没有重复的两个端点,也就是我们在求最大匹配,匈牙利算法处理即可。
Acwing 376. 机器任务
显然,A 和 B 共有 n+m−2 种模式(0 一开始就可以处理),而每个物品相当于连接左边的 ai 和右边的 bi,这天然满足二分图性质,求最少重启次数相当于求最小覆盖数,也就是最大匹配数。
Acwing 378. 骑士放置
转换一下题目,相当于在网格图上每个格子向八个格子连边,求最多不会互相连边的大小,相当于求最大独立集,用总点数减去最大匹配数即可。
还有一个问题,原图是否是二分图?显然是的,将横纵坐标和奇偶进行染色即可,对于边而言,容易发现连边一定会改变奇偶,所以边也没有问题。
Acwing 379. 捉迷藏
先说结论,点数减去最小路径点覆盖数。
接下来是证明,令原图最小路径点覆盖数量为 cnt,显然我们只能在这 cnt 条路径上放点,且每个路径最多只能放一个点,即 ans≥cnt。
然后证 ans 能够等于 cnt,考虑选出这些路径的终点,构成集合 E,定义 next(A) 表示集合 A 中所有能到达的点,若 E∩next(E)=∅,则说明 E 中有 cnt 个节点,此时 E 即为一种合法的构造。
如果 E∩next(E)=∅,则 ∀e∈E,使其反向走,直到 e∈/next(E) 为止(显然最多走到起点一定会停止,否则与最小路径点覆盖矛盾),此时所有 e 便是一种合法构造。
