最大密度子图的相关概念

密度子图： 给定一个无向图 $G(V, E)$，图中的某一个点集 $V’$ 和某一个边集 $E’$，这个边集中的任意一条边 $(a, b)$ 都满足 $a$ 和 $b$ 都在 $V’$ 中，则将这个点集和边集统称为原图的 密度子图

最大密度子图： 给定一个无向图 $G(V, E)$，图中存在若干个密度子图，若其中一个密度子图的密度最大（密度为边的数量除以点的数量，即 $\frac{\vert E’ \vert}{\vert V’ \vert}$），则这个密度子图称为 最大密度子图

如何求最大密度子图：

设原图为 $G = (V, E)$，密度子图为 $G’ = (V’, E’)$

可以发现 $\frac{\vert E’ \vert}{\vert V’ \vert}$ 是一个分数，求这个分数的最大值可以用 01 分数规划。

假设当前密度子图的密度是 $g$，即 $\frac{\vert E’ \vert}{\vert V’ \vert} = g$，我们可以进一步得到一个新的关系，$\vert E’ \vert - g \cdot \vert V’ \vert = 0$。

若现在 $\frac{\vert E’ \vert}{\vert V’ \vert}$ 是最大密度子图的密度，$g$ 是二分的中间值，如果 $\vert E’ \vert - g \cdot \vert V’ \vert > 0$，则 $\frac{\vert E’ \vert}{\vert V’ \vert} > g$，说明最大密度子图的密度比 $g$ 大，因此此时需要二分右区间。如果 $\vert E’ \vert - g \cdot \vert V’ \vert < 0$，则 $\frac{\vert E’ \vert}{\vert V’ \vert} < g$，说明最大密度子图的密度比 $g$ 小，因此此时需要二分左区间。最终得到一个固定值，就是 $\frac{\vert E’ \vert}{\vert V’ \vert}$ 的真实值。

现在的问题是需要在每次二分的过程中，求出当前 $\vert E’ \vert - g \cdot \vert V’ \vert$ 的具体数值，才能通过判断它和 $0$ 的关系来进一步二分。

那么如果求出最大密度子图中 $\vert E’ \vert - g \cdot \vert V’ \vert$ 的具体数值呢，首先密度子图有一个特性，若一条边 $(a, b)$，就必须选 $a$ 和 $b$ 这两个点，因此我们可以把边也看成点，从该边向对应的两个点连一条有向边，表示如果选这条边就必须选对应的两个点，这样我们就将密度子图的限制转化成了闭合子图的限制了。

那么接下来问题就变成了求一个最大化 $\vert E’ \vert - g \cdot \vert V’ \vert$ 的闭合点集。这时设所有边转化成的点的权值是 $1$，所有点的权值是 $-g$，那么这就可以用最大权闭合子图的做法直接来求。但是用这样的思路来做的话图中的边数有 $3E + V$，边数非常多，因此我们可以再考虑进行一些优化。

刚才分析出来的做法其实是一种一般化的做法，没有运用一些性质，所以效率比较低。这里有一个性质，如果我们已经确定了当前的点集，那么这个点集的诱导子图一定是最优的（点集内部的所有边全选得出的子图）。

我们要想求最大化的 $\vert E’ \vert - g \cdot \vert V’ \vert$，等价于求最小化 $g \cdot \vert V’ \vert - \vert E’ \vert$，网络流中求最小值可以想到和最小割产生联系。如果直接求密度子图里面边的数量不是很好求，要想尽量把它和割连接起来，所以可以用一个补集的思想，可以用密度子图的点集相关的所有边的数量减去密度子图和其他点的割边的数量，就是密度子图中边的数量，但是和点集相关的所有边的数量仍比好求，由于每条边都连向两个点，可以将每条边一分为二，分别连向两个点，即每条边都让对应的两个点度数 $+1$，这样点集相关的所有边的数量就是点集的总度数，再减去割边的数量就是密度子图中边的数量，但是每条边已经一分为二，所以求出来的数量还需要除以 $2$，因此最终密度子图中边的数量就是 $\frac{\sum_{v \in V’} d_v - C[V’, V - V’]}{2}$。

则最小化 $\vert E’ \vert - g \cdot \vert V’ \vert = \sum_{v \in V’} g - \frac{\sum_{v \in V’} d_v - C[V’, V - V’]}{2} = \sum_{v \in V’} g - (\frac{\sum_{v \in V’} d_v}{2} - \frac{C[V’, V - V’]}{2}) = \sum_{v \in V’} (g - \frac{d_v}{2}) + \frac{C[V’, V-V’]}{2}$

通过以上的转化，我们将原本求的最小化 $\vert E’ \vert - g \cdot \vert V’ \vert$ 和割对应起来了，但是这里还不太一样，除了割以外还多了一项，我们希望再进一步简化成只剩割，那么最终我们只需要求最小割就行了。

所以还需要进一步推公式 $\sum_{v \in V’} (g - \frac{d_v}{2}) + \frac{C[V’, V-V’]}{2} = \frac{1}{2} \cdot (\sum_{v \in V’} (2g - d_v) + C[V’, V-V’])$，然后我们尝试将 $\sum_{v \in V’} (2g - d_v)$ 融入到 $C[V’, V-V’]$，只需要将所有点向汇点连一条容量是 $2g - d_v$ 的边即可，这里 $2g - d_v$ 可能是负数，可以加上一个大数 $U$，对应的源点向所有点连一条容量是 $U$ 的边，而原图中所有点之间的边容量是 $1$。

然后还需要证明原问题的可行解和割是一一对应的，原问题每个点只有选和不选两种选法，所以是 $2^n$ 种，割也是除了源点和汇点，每个点都有两种选法，也是 $2^n$ 种，显然可以一一对应。

为什么加上一个大数 $U$ 还是不影响最终答案呢，这里可以看一下原问题和割的关系，假设 $V’ = S - \lbrace s \rbrace$，割的容量 $C[S, T]$ 就是 $V’$ 和 $s$ 到 $V-V’$ 和 $t$ 的边的容量和，而 $s$ 到 $t$ 的边不存在，还剩三种边，所以 $C[S, T] = \sum_{v \in V-V’} U + \sum_{u \in V’} (U+2g-d_u) + \sum_{u \in V’} \sum_{v \in V-V’} C_{u, v} = \sum_{v \in V-V’} U + \sum_{u \in V’} (U+2g - d_u + \sum_{v \in V-V’} C_{u, v}) = \sum_{v \in V-V’} U + \sum_{u \in V’} (U+2g - (d_u - \sum_{v \in V-V’} C_{u, v})) = \sum_{v \in V-V’} U + \sum_{u \in V’} (U+2g - \sum_{v \in V’} C_{u, v}) = \sum_{v \in V} U + \sum_{u \in V’} 2g - \sum_{u \in V’} \sum_{v \in V’} C_{u, v}) = U \cdot n + 2g \cdot \vert V’ \vert - 2 \cdot \vert E’ \vert$

我们要让 $\vert E’ \vert - g \cdot \vert V’ \vert$ 最大，就是让 $g \cdot \vert V’ \vert - \vert E’ \vert$ 最小，就是让 $U \cdot n + 2g \cdot \vert V’ \vert - 2 \cdot \vert E’ \vert$ 最小，$U \cdot n$ 是个定值，所以就是要让 $2g \cdot \vert V’ \vert - 2 \cdot \vert E’ \vert$ 最小，等价于让 $C[S, T]$ 最小，所以割和密度子图是存在单调关系的，且是一一对应的，所以求一下最小割即可，答案就是 $\frac{U \cdot n - C[S, T]}{2}$

扩展

在图中加入边权： 在原图中每条边的容量其实是 $1$，这里其实就是将每条边的容量设置成权值，因此必须要求边权 $\geq 0$，这样一来上述的证明需要稍作变动，$\vert E’ \vert$ 的定义要改成所有选择的边的权值和。那么在算密度子图内部的边的权值之和时就是将每条边的权值一分为二，每条边的权值在对应的两个点上都算一次，那么 $d_v$ 就不再记录每个点的度数，改成所有从当前出发的边的权值和。将两个定义一改，就可以完全套用上述的证明，答案依然是 $\frac{U \cdot n - C[S, T]}{2}$

在图中同时加入边权和点权： 假定每个点的权值是 $p_i$，那么最终要求的目标值应该是 $\frac{\vert E’ \vert + \vert V’ \vert}{\vert V’ \vert}$，然后再去寻找它和 $g$ 的关系，处理只有应该是要最大化 $\vert E’ \vert + \vert V’ \vert - g \cdot \vert V’ \vert$，等价于最小化 $g \cdot \vert V’ \vert - \vert V’ \vert - \vert E’ \vert$，这个式子具体表示出来就是 $\frac{1}{2} \cdot (\sum_{v \in V’} (2g - 2p_v - d_v) + C[V’, V-V’])$，相比原表达式这里等于是多减去一个点权，那么所有点向汇点连的边的容量就改成 $2g - 2p_v - d_v + U$，最后讨论数值关系时也变成 $C[S, T] = U \cdot n + 2g \cdot \vert V’ \vert - 2 \cdot \vert E’ \vert - 2 \cdot \vert V’ \vert$，最终答案还是 $\frac{U \cdot n - C[S, T]}{2}$，可以发现最终结果的式子是不变的，区别在于过程中的一些变动。