最大权闭合子图（Maximum Weight Closure of a Graph）问题
字数 3731 2025-12-17 04:16:36

最大权闭合子图（Maximum Weight Closure of a Graph）问题

问题描述

我们有一个有向图 \(G = (V, E)\)，图中每个顶点 \(v \in V\) 都有一个权重 \(w(v)\)（可以是正数、负数或零）。
一个闭合子图（Closure） 指的是图 \(G\) 的一个顶点子集 \(C \subseteq V\)，满足：如果 \(u \in C\) 且存在一条有向边 \((u, v) \in E\)，则 \(v\) 也必须属于 \(C\)。换句话说，在子图 \(C\) 中，从任意顶点出发的有向边所指向的顶点也必须包含在 \(C\) 中，即 \(C\) 关于有向边是“闭合”的。

最大权闭合子图问题 的目标是找到一个闭合子图 \(C\)，使得其中所有顶点的权重之和 \(\sum_{v \in C} w(v)\) 最大。

这个问题在实际中有广泛应用，比如：

  • 项目选择问题：某些项目有收益（正权重）或成本（负权重），且项目间有依赖关系（必须先完成某些项目才能做其他项目），要选择一组项目使总收益最大。
  • 病毒营销或影响传播中的收益最大化建模。

解题思路

这个问题可以转化为网络流中的最小割问题来求解。核心思想是：

  1. 构造一个流网络。
  2. 将原问题转化为求该网络的最小割。
  3. 根据最小割得出最大权闭合子图。

详细步骤

步骤1：构造流网络

我们从原图 \(G = (V, E)\) 构造一个新的流网络 \(N = (V_N, E_N)\)：

  • 顶点集 \(V_N = V \cup \{s, t\}\)，其中 \(s\) 是源点，\(t\) 是汇点。
  • 对于原图中每个顶点 \(v \in V\)：
    • 如果 \(w(v) > 0\)，则从源点 \(s\) 到 \(v\) 连一条有向边，容量为 \(w(v)\)。
    • 如果 \(w(v) < 0\)，则从 \(v\) 到汇点 \(t\) 连一条有向边，容量为 \(-w(v)\)（即权重的绝对值）。
    • 如果 \(w(v) = 0\)，则不与 \(s\) 或 \(t\) 连边（或者也可以连容量为0的边，不影响）。
  • 对于原图中的每条有向边 \((u, v) \in E\)，在网络 \(N\) 中添加一条从 \(u\) 到 \(v\) 的有向边，容量设为无穷大（在实际计算中可用一个足够大的数，如所有正权重之和+1）。

步骤2：理解构造的含义

这个构造的核心目的是：

  • 原图中每个正权顶点带来收益，我们希望通过选择它来获得这个收益（在流网络中体现为从 \(s\) 到该点的边）。
  • 负权顶点带来成本，选择它就要付出代价（体现为从该点到 \(t\) 的边）。
  • 原图的有向边表示依赖：如果选择了 \(u\)，则必须选择 \(v\)（否则就会违反闭合性）。在流网络中，我们用容量无穷大的边 \((u, v)\) 来强制：如果在最小割中 \(u\) 在源点一侧（被选择）而 \(v\) 在汇点一侧（未被选择），那么这条无穷大的边会穿过割，导致割的容量无穷大，这不可能成为最小割（除非总权重和本身就是负无穷）。因此，在最小割中，这样的划分不会被允许，从而保证了闭合性。

步骤3：最小割与闭合子图的关系

在流网络 \(N\) 中，一个 \(s$-$t\) 割将顶点分成两个集合：包含源点 \(s\) 的集合 \(S\) 和包含汇点 \(t\) 的集合 \(T\)。
关键结论：令 \(C = S \setminus \{s\}\)（即 \(S\) 中除源点以外的顶点），则 \(C\) 是原图的一个闭合子图。
反之，原图的任何一个闭合子图 \(C\) 都可以对应网络 \(N\) 中的一个割，其构造方式为：\(S = \{s\} \cup C\)，\(T = V_N \setminus S\)。

步骤4：权值和与割容量的关系

设原图中所有正权顶点的权重之和为 \(W^+ = \sum_{w(v)>0} w(v)\)。
对于网络 \(N\) 中的一个割 \((S, T)\)，其容量 \(cap(S, T)\) 由三部分组成：

  1. 从 \(s\) 到 \(T\) 中正权顶点的边：这些正权顶点未被选入 \(C\)，我们损失了它们的收益，每条边贡献容量 \(w(v)\)。
  2. 从 \(S\) 中负权顶点到 \(t\) 的边：这些负权顶点被选入了 \(C\)，我们需要付出成本，每条边贡献容量 \(-w(v)\)。
  3. 从 \(S\) 到 \(T\) 的无穷大边：如果存在，则割容量无穷大（但在最小割中，由于闭合性要求，这样的边不应该出现）。

因此，对于任意对应一个闭合子图的割，其容量满足：

\[cap(S, T) = \sum_{\substack{v \notin C \\ w(v) > 0}} w(v) \;+\; \sum_{\substack{v \in C \\ w(v) < 0}} (-w(v)) \]

这可以改写为：

\[cap(S, T) = W^+ - \sum_{v \in C} w(v) \]

因为：

  • 第一项是“未选的正权顶点权重之和”。
  • 第二项是“已选的负权顶点权重之和的相反数”。
  • 而 \(W^+ = \sum_{v \in C, w(v)>0} w(v) + \sum_{v \notin C, w(v)>0} w(v)\)。
  • 整理后得到上述关系。

步骤5：最大化权重和等价于最小化割容量

由上式可得：

\[\sum_{v \in C} w(v) = W^+ - cap(S, T) \]

因为 \(W^+\) 是常数，所以最大化闭合子图的权重和等价于最小化割的容量。
因此，我们只需要在网络 \(N\) 上计算从 \(s\) 到 \(t\) 的最小割，然后令 \(C = S \setminus \{s\}\)（其中 \(S\) 是最小割中源点所在的集合），则 \(C\) 就是最大权闭合子图。

算法流程

  1. 输入：有向图 \(G = (V, E)\)，顶点权重 \(w(v)\)。
  2. 构造流网络 \(N\)：
    • 创建源点 \(s\) 和汇点 \(t\)。
    • 对每个 \(v \in V\)：
      • 若 \(w(v) > 0\)，加边 \((s, v)\)，容量 \(w(v)\)。
      • 若 \(w(v) < 0\)，加边 \((v, t)\)，容量 \(-w(v)\)。
    • 对每条边 \((u, v) \in E\)，加边 \((u, v)\)，容量 \(+\infty\)。
  3. 在网络 \(N\) 上运行最大流算法（如 Dinic、Edmonds-Karp 等），得到最大流值及最小割 \((S, T)\)。
  4. 输出：最大权闭合子图 \(C = S \setminus \{s\}\)，其权重和为 \(W^+ - cap(S, T)\)。

实例演示

考虑一个简单例子：

  • 顶点：\(A, B, C\)，权重：\(w(A)=5, w(B)=-3, w(C)=2\)。
  • 有向边：\((A, B), (A, C)\)。

构造网络 \(N\)：

  • 边 \((s, A)\)，容量 5。
  • 边 \((s, C)\)，容量 2。
  • 边 \((B, t)\)，容量 3。
  • 边 \((A, B)\)，容量 \(+\infty\)。
  • 边 \((A, C)\)，容量 \(+\infty\)。

计算最小割：

  • 若选择 \(C = \{A, C\}\)（闭合吗？边 \((A,B)\) 存在，但 \(B\) 不在 \(C\) 中，不闭合，所以对应割会包含无穷大边 \((A,B)\)，容量无穷大，不是最小割）。
  • 最小割应该是 \(S = \{s, A, B, C\}\)，\(T = \{t\}\)，此时 \(C = \{A, B, C\}\)，权重和 = \(5-3+2=4\)，割容量 = \(W^+ - 4 = (5+2) - 4 = 3\)，检查：割边只有 \((B,t)\)，容量 3，正确。
  • 另一种选择 \(C = \{C\}\) 不闭合（因为 \(A\) 指向 \(C\) 但 \(A\) 不在 \(C\) 中），对应割有边 \((A,C)\) 无穷大。

所以最大权闭合子图是 \(\{A, B, C\}\)，权重和 4。

复杂度分析

  • 网络 \(N\) 有 \(|V|+2\) 个顶点，最多 \(|E| + |V|\) 条边（每条原图边和每个顶点到 \(s\) 或 \(t\) 的边）。
  • 使用 Dinic 算法，复杂度为 \(O((|V|+2)^2 \cdot (|E|+|V|))\)，即 \(O(|V|^2 \cdot |E|)\) 级别（因为容量有大值，但通常用 BFS/DFS 增广不影响复杂度分析）。
  • 这是一个多项式时间算法，可以高效求解。

总结

最大权闭合子图问题通过巧妙的网络流构造，将依赖关系用无穷大容量边表示，将权重转化为割的容量，从而利用最小割求解。这个方法不仅高效，而且揭示了组合优化问题与网络流之间的深刻联系。

最大权闭合子图（Maximum Weight Closure of a Graph）问题 问题描述 我们有一个 有向图 \(G = (V, E)\)，图中每个顶点 \(v \in V\) 都有一个权重 \(w(v)\)（可以是正数、负数或零）。 一个 闭合子图（Closure） 指的是图 \(G\) 的一个顶点子集 \(C \subseteq V\)，满足：如果 \(u \in C\) 且存在一条有向边 \((u, v) \in E\)，则 \(v\) 也必须属于 \(C\)。换句话说，在子图 \(C\) 中，从任意顶点出发的有向边所指向的顶点也必须包含在 \(C\) 中，即 \(C\) 关于有向边是“闭合”的。 最大权闭合子图问题 的目标是找到一个闭合子图 \(C\)，使得其中所有顶点的权重之和 \(\sum_ {v \in C} w(v)\) 最大。 这个问题在实际中有广泛应用，比如： 项目选择问题：某些项目有收益（正权重）或成本（负权重），且项目间有依赖关系（必须先完成某些项目才能做其他项目），要选择一组项目使总收益最大。 病毒营销或影响传播中的收益最大化建模。 解题思路 这个问题可以转化为 网络流中的最小割问题 来求解。核心思想是： 构造一个流网络。 将原问题转化为求该网络的最小割。 根据最小割得出最大权闭合子图。 详细步骤 步骤1：构造流网络 我们从原图 \(G = (V, E)\) 构造一个新的流网络 \(N = (V_ N, E_ N)\)： 顶点集 \(V_ N = V \cup \{s, t\}\)，其中 \(s\) 是 源点 ，\(t\) 是 汇点 。 对于原图中每个顶点 \(v \in V\)： 如果 \(w(v) > 0\)，则从源点 \(s\) 到 \(v\) 连一条有向边，容量为 \(w(v)\)。 如果 \(w(v) < 0\)，则从 \(v\) 到汇点 \(t\) 连一条有向边，容量为 \(-w(v)\)（即权重的绝对值）。 如果 \(w(v) = 0\)，则不与 \(s\) 或 \(t\) 连边（或者也可以连容量为0的边，不影响）。 对于原图中的每条有向边 \((u, v) \in E\)，在网络 \(N\) 中添加一条从 \(u\) 到 \(v\) 的有向边，容量设为 无穷大 （在实际计算中可用一个足够大的数，如所有正权重之和+1）。 步骤2：理解构造的含义 这个构造的核心目的是： 原图中每个正权顶点带来收益，我们希望通过选择它来获得这个收益（在流网络中体现为从 \(s\) 到该点的边）。 负权顶点带来成本，选择它就要付出代价（体现为从该点到 \(t\) 的边）。 原图的有向边表示依赖：如果选择了 \(u\)，则必须选择 \(v\)（否则就会违反闭合性）。在流网络中，我们用容量无穷大的边 \((u, v)\) 来 强制 ：如果在最小割中 \(u\) 在源点一侧（被选择）而 \(v\) 在汇点一侧（未被选择），那么这条无穷大的边会穿过割，导致割的容量无穷大，这不可能成为最小割（除非总权重和本身就是负无穷）。因此，在最小割中，这样的划分不会被允许，从而保证了闭合性。 步骤3：最小割与闭合子图的关系 在流网络 \(N\) 中，一个 \(s\)-\(t\) 割将顶点分成两个集合：包含源点 \(s\) 的集合 \(S\) 和包含汇点 \(t\) 的集合 \(T\)。 关键结论 ：令 \(C = S \setminus \{s\}\)（即 \(S\) 中除源点以外的顶点），则 \(C\) 是原图的一个闭合子图。 反之，原图的任何一个闭合子图 \(C\) 都可以对应网络 \(N\) 中的一个割，其构造方式为：\(S = \{s\} \cup C\)，\(T = V_ N \setminus S\)。 步骤4：权值和与割容量的关系 设原图中所有正权顶点的权重之和为 \(W^+ = \sum_ {w(v)>0} w(v)\)。 对于网络 \(N\) 中的一个割 \((S, T)\)，其容量 \(cap(S, T)\) 由三部分组成： 从 \(s\) 到 \(T\) 中正权顶点的边：这些正权顶点未被选入 \(C\)，我们损失了它们的收益，每条边贡献容量 \(w(v)\)。 从 \(S\) 中负权顶点到 \(t\) 的边：这些负权顶点被选入了 \(C\)，我们需要付出成本，每条边贡献容量 \(-w(v)\)。 从 \(S\) 到 \(T\) 的无穷大边：如果存在，则割容量无穷大（但在最小割中，由于闭合性要求，这样的边不应该出现）。 因此，对于任意 对应一个闭合子图 的割，其容量满足： \[ cap(S, T) = \sum_ {\substack{v \notin C \\ w(v) > 0}} w(v) \;+\; \sum_ {\substack{v \in C \\ w(v) < 0}} (-w(v)) \] 这可以改写为： \[ cap(S, T) = W^+ - \sum_ {v \in C} w(v) \] 因为： 第一项是“未选的正权顶点权重之和”。 第二项是“已选的负权顶点权重之和的相反数”。 而 \(W^+ = \sum_ {v \in C, w(v)>0} w(v) + \sum_ {v \notin C, w(v)>0} w(v)\)。 整理后得到上述关系。 步骤5：最大化权重和等价于最小化割容量 由上式可得： \[ \sum_ {v \in C} w(v) = W^+ - cap(S, T) \] 因为 \(W^+\) 是常数，所以 最大化闭合子图的权重和 等价于 最小化割的容量 。 因此，我们只需要在网络 \(N\) 上计算从 \(s\) 到 \(t\) 的 最小割 ，然后令 \(C = S \setminus \{s\}\)（其中 \(S\) 是最小割中源点所在的集合），则 \(C\) 就是最大权闭合子图。 算法流程 输入 ：有向图 \(G = (V, E)\)，顶点权重 \(w(v)\)。 构造流网络 \(N\) ： 创建源点 \(s\) 和汇点 \(t\)。 对每个 \(v \in V\)： 若 \(w(v) > 0\)，加边 \((s, v)\)，容量 \(w(v)\)。 若 \(w(v) < 0\)，加边 \((v, t)\)，容量 \(-w(v)\)。 对每条边 \((u, v) \in E\)，加边 \((u, v)\)，容量 \(+\infty\)。 在网络 \(N\) 上运行最大流算法 （如 Dinic、Edmonds-Karp 等），得到最大流值及最小割 \((S, T)\)。 输出 ：最大权闭合子图 \(C = S \setminus \{s\}\)，其权重和为 \(W^+ - cap(S, T)\)。 实例演示 考虑一个简单例子： 顶点：\(A, B, C\)，权重：\(w(A)=5, w(B)=-3, w(C)=2\)。 有向边：\((A, B), (A, C)\)。 构造网络 \(N\)： 边 \((s, A)\)，容量 5。 边 \((s, C)\)，容量 2。 边 \((B, t)\)，容量 3。 边 \((A, B)\)，容量 \(+\infty\)。 边 \((A, C)\)，容量 \(+\infty\)。 计算最小割： 若选择 \(C = \{A, C\}\)（闭合吗？边 \((A,B)\) 存在，但 \(B\) 不在 \(C\) 中，不闭合，所以对应割会包含无穷大边 \((A,B)\)，容量无穷大，不是最小割）。 最小割应该是 \(S = \{s, A, B, C\}\)，\(T = \{t\}\)，此时 \(C = \{A, B, C\}\)，权重和 = \(5-3+2=4\)，割容量 = \(W^+ - 4 = (5+2) - 4 = 3\)，检查：割边只有 \((B,t)\)，容量 3，正确。 另一种选择 \(C = \{C\}\) 不闭合（因为 \(A\) 指向 \(C\) 但 \(A\) 不在 \(C\) 中），对应割有边 \((A,C)\) 无穷大。 所以最大权闭合子图是 \(\{A, B, C\}\)，权重和 4。 复杂度分析 网络 \(N\) 有 \(|V|+2\) 个顶点，最多 \(|E| + |V|\) 条边（每条原图边和每个顶点到 \(s\) 或 \(t\) 的边）。 使用 Dinic 算法，复杂度为 \(O((|V|+2)^2 \cdot (|E|+|V|))\)，即 \(O(|V|^2 \cdot |E|)\) 级别（因为容量有大值，但通常用 BFS/DFS 增广不影响复杂度分析）。 这是一个多项式时间算法，可以高效求解。 总结 最大权闭合子图问题通过巧妙的网络流构造，将依赖关系用无穷大容量边表示，将权重转化为割的容量，从而利用最小割求解。这个方法不仅高效，而且揭示了组合优化问题与网络流之间的深刻联系。