二分图进阶指南

二分图进阶指南

前置知识:匈牙利算法,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
2
3
4
5
6
7
8
9
10
11
12
void dfs(int x)
{
if(l[x])
return;
l[x]=1;
for(int i=1;i<=n;++i)
if(mp[x][i]&&!r[i])
{
r[i]=1;
dfs(link[i]);
}
}

最小点覆盖中点的个数=最大匹配($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
2
3
4
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
mp[i][j]|=mp[i][k]&mp[k][j];

在原图上跑Floyd传递闭包。

如图,避免了相交的问题。原先相交的链变得不再相交,即可将这个问题转化为不可相交的链覆盖。

DAG中的$Dilworth$定理,最大独立集和最长反链

$Dilworth$定理:

DAG的最大独立集=DAG的最小不相交链覆盖

在求出最小不相交链覆盖后,图中的非匹配点即位链的终点。

非匹配点的点集即为答案的具体。

实际上,可以在每一条链中各选一个点,组成最大独立集。


观察反链和独立集的定义。

传递闭包后的图的最大独立集,任意2点之间没有连边,即任意2点不可达。

这时的最大独立集即为原图的最长反链。

输出方案的方法同上。

例题:[CTSC2008]祭祀