最大权闭合子图

发表于 2020-07-16 分类于算法阅读次数：

概念

一个有向图 \(G = (V, E)\) 的闭合子图是一个导出子图 \(G_0 = (V_0, E_0)\) ，满足 \(\forall u \in V_0, (u, x) \in E\) 有 \(x \in V_0\) 成立。

最大权闭合子图即点权和最大的闭合子图。

网络流模型

注意到对于任意两个点 \(u, v\) 满足 \(u\) 能到达 \(v\) ，闭合子图必须满足以下两个限制之一：

\(u\) 不在该闭合子图中
\(v\) 在该闭合子图中

容易联想到“割”，建源点 \(S\) 连向所有点，所有点连向汇点 \(T\) 。割掉 \((u, T)\) 表示 \(u\) 在闭合子图中，割掉 \((S, u)\) 表示 \(u\) 不在闭合子图中。那么新图的一组合法割就对应了原图的一个闭合子图。

求最大权闭合子图就只要给新图定义合适的边权，使得最大权闭合子图的权值等于一个定值 \(K\) 减去新图最小割。

容易想到令原图边边权为 \(+\infty\) ，\((S, u)\) 的边权为 \(u\) 的点权，\((u, T)\) 的边权为 \(0\) 。那么上述的定值 \(K\) 就是点权和。但是 \(u\) 的点权可能为负数，这样定权会导致负权边的出现。常规操作，对于点权为 \(-X (X > 0)\) 的点 \(u\) ，不妨先“预流”一条 \(S -> u -> T\) 的流量为 \(-X\) 的路径，这样 \((S, u)\) 的边权变为 \(0\) ，\((u, T)\) 的边权变为 \(X\) 。算上“预流”的流量，此时 \(K\) 是所有正权点的权值和。此时就可以简单地应用网络流解决这个问题。

最大密度子图

对于无向图 \(G = (V, E)\) ，其非空导出子图 \(G_0 = (V_0, E_0)\) 的密度定义为边数与点数的比值，即 \(\frac{|E_0|}{|V_0|}\) 。

最大密度子图即密度最大的导出子图。

问题实际上是一个分数规划，不难想到二分密度 \(X\) 然后判断是否存在 \(G_0\) 满足 \(|E_0| - X |V_0| > 0\) 。

令每条边的权值为 \(1\) ，每个点的权值为 \(-X\) ，那么问题就是要求一个点权和加边权和最大的导出子图。

注意到一条边出现在导出子图中当且仅当它的两个端点都在该导出子图中，根据这个限制关系可以把原图的边都抽象成点然后建新的有向图。判断新图的最大权导出子图的权值是否为正数即可。

需要注意的是，空集也是一个导出子图，其密度是没有定义的，却始终满足 \(|E_0| - X |V_0| = 0\) ，因此二分的判断条件一定是严格大于而不是大于等于。