二分图进阶指南
前置知识:匈牙利算法,zkw费用流,Floyd传递闭包
基本概念
二分图:
指顶点可以分成两个互斥的独立集\(U\)和\(V\)的无向图,也就是在任两个同在\(U\)或\(V\)的顶点间没有边。

一般为了方便表示,我们将点集分为左右2个部分。
匹配:
边集\(E\),其中没有任意2条边有相同的顶点
点覆盖:
点集\(V\),使整张图中的每一条边都至少有一个顶点在\(V\)中
链:
点集\(V\),其中任意2个点\(x\)和\(y\),满足\(x\)可到达\(y\)或\(y\)可到达\(x\)
反链:
点集\(V\),其中任意2个点\(x\)和\(y\),满足\(x\)不可到达\(y\)且\(y\)不可到达\(x\)
独立集:
点集\(V\),其中任意2个点\(x\)和\(y\),没有边直接相连
链覆盖:
选出若干条链,使整张图的每个点都在链上
总结
问题 | 答案 | 输出方案 |
---|---|---|
最大匹配 | \(ans\) | \(link\)数组 |
最小点覆盖 | \(ans\)(\(König\)) | 打标记,左没有右有 |
最大独立集 | \(n-ans\) | 打标记,左有右没有 |
最长反链 | 传递闭包,\(n-ans\) | 新图的最大独立集 |
DAG不相交链覆盖 | \(n-ans\) | \(dfs\)输出结果 |
DAG相交链覆盖 | 传递闭包,\(n-ans\) | \(dfs\)输出结果 |
DAG最大独立集 | \(n-ans\)(\(Dilworth\)) | 非匹配点集 |
DAG最长反链 | 传递闭包,\(n-ans\) | 非匹配点集 |
通过传递闭包,我们在所有联通的点之间连边,可以做到:
- 独立集\(\longrightarrow\)最长反链
- 不相交链覆盖\(\longrightarrow\)相交链覆盖
匹配
匈牙利算法:
枚举左边的点,寻找以他为起点的增广路(未匹配边——匹配边——…...——未匹配边)。

若存在这样的路径,图中的最大匹配数便加一。
若边带权,使用zkw费用流解决。
若点带权,拆点后使用zkw费用流解决。
二分图中的\(König\)定理,最小点覆盖和最大独立集
在一张跑完最大匹配的二分图上,我们从左边未匹配的点出发。沿着(未匹配边——匹配边——未匹配边——……——匹配边)的假增广路进行\(dfs\),并将途经的点打上标记。
1 | void dfs(int x) |
最小点覆盖中点的个数=最大匹配(\(König\)定理)
简单的证明:
我们选出的点一定是某一条匹配边的端点,且选出的点与匹配边一一对应。
左边的非匹配点被打上了标记,不会被选出。
右边的非匹配点无法通过假增广路到达,否则就不满足已是最大匹配的条件,不会被打上标记。
匹配边上2端点的标记状态一定是相同的,每条匹配边只可能有一个端点被选出。
所以点的个数即最大匹配数。
最小点覆盖和最大独立集互为补集
简单的证明:
初始状态下所有的点都在集合中,要删除一部分点和所有与他们连接的边,使得图中没有边存在。
这个删去的点集便是最小点覆盖。
最小点覆盖=左边未标记的点+右边已标记的点
简单的证明:
假设存在没有被覆盖的边,且左端点有标记,右端点没有标记。
如果是非匹配边,那么从左端点开始\(dfs\),他的右端点就会被标记。
如果是匹配边,由于我们从左边的非匹配点开始\(dfs\),那么他的左端点的标记一定来源于右端点,即右端点也有标记。
所以不存在没有被覆盖的边。
最大独立集=左边已标记的点+右边未标记的点
简单的证明:
不存在一条边的2个端点都不在最小点覆盖中,每条边都至少有1个端点被覆盖。
所以剩下的点不能通过某一条边直接连接。
当点覆盖集最小的时候,剩余的点集便是最大的。
例题:HDU3335
推荐阅读:Matrix67的博客
DAG中的最小点覆盖,最大独立集
显然,我们可以将一个DAG通过拆点转换为二分图。
我们为每一个点\(u\)建立入点\(u_x\)(放在左边)和出点\(u_y\)(放在右边)。将原图中\(u\)到\(v\)的边转位\(u_y\)到\(v_x\)的边。
原图上的答案即为二分图上的答案。
但在输出方案时,有所不同。
仅当一个点在左右点都满足了对标记的要求时,才算是答案。
最小点覆盖=左边无标记且右边有标记的点
最大独立集=左边有标记且右边无标记的点
DAG中的最小链/路径覆盖
不可相交的链覆盖
最少不相交路径覆盖=原图的点数-新图的最大匹配
简单的证明:
一开始图的链覆盖为\(n\) 。
在二分图匹配中,每找到一条匹配边,则相当于有一条边覆盖原来的2个顶点,使答案减一。
所以有,最少不相交路径覆盖=原图的点数-新图的最大匹配。
可相交的链覆盖
若可从\(x\)到达\(y\),我们便添加一条从\(x\)指向\(y\)的边。
这一过程被称为传递闭包。
1 | for(int k=1;k<=n;++k) |
在原图上跑Floyd传递闭包。

如图,避免了相交的问题。原先相交的链变得不再相交,即可将这个问题转化为不可相交的链覆盖。
DAG中的\(Dilworth\)定理,最大独立集和最长反链
\(Dilworth\)定理:
DAG的最大独立集=DAG的最小不相交链覆盖
在求出最小不相交链覆盖后,图中的非匹配点即位链的终点。
非匹配点的点集即为答案的具体。
实际上,可以在每一条链中各选一个点,组成最大独立集。
观察反链和独立集的定义。
传递闭包后的图的最大独立集,任意2点之间没有连边,即任意2点不可达。
这时的最大独立集即为原图的最长反链。
输出方案的方法同上。
例题:[CTSC2008]祭祀