最大权闭合子图（Maximum Weight Closure of a Graph）问题
字数 3884 2025-12-14 08:46:45

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

我将详细讲解最大权闭合子图问题，包括问题定义、如何转化为最小割/最大流问题，以及完整的求解步骤。

1. 问题描述

我们有一个有向图 \(G = (V, E)\)。每个顶点 \(v\) 都有一个权值 \(w(v)\)，可为正、负或零。

一个闭合子图（Closure） 是指顶点集的一个子集 \(C \subseteq V\)，满足：

  • 若 \(u \in C\)，且存在一条从 \(u\) 到 \(v\) 的有向边 \((u, v) \in E\)，则 \(v\) 也必须属于 \(C\)。

换句话说，闭合子图是一个“封闭”的点集：从集合中任意点出发，沿着有向边走，永远不会走出这个集合。

目标：在所有可能的闭合子图中，找到一个权值和最大的闭合子图 \(C^*\)，即最大化：

\[\sum_{v \in C} w(v) \]

2. 问题理解与例子

例子：
假设一个工程项目的依赖图，每个顶点代表一个任务或资源，权值是完成该任务的收益（正）或成本（负）。如果任务 A 依赖任务 B（即 A 需要 B 的输出），则有一条边从 A 指向 B（表示：若选择 A，则必须选择 B）。
我们希望选择一组任务，满足所有依赖关系，并使得总收益最大。这就是一个最大权闭合子图问题。

重要观察：

  • 闭合子图性质保证了依赖关系的满足。
  • 正权顶点是我们想选的（增加总权值），负权顶点是我们想避免的（减少总权值）。
  • 但为了选某些正权顶点，可能不得不选一些它们所依赖的负权顶点，因此需要权衡。

3. 转化为最小割问题

最大权闭合子图可以通过构造一个网络流模型，并计算其最小割来求解。步骤如下：

3.1 构造网络

  • 源点 \(s\) 和汇点 \(t\)。
  • 对原图中每个顶点 \(v\)：
    • 若 \(w(v) > 0\)，添加边 \((s, v)\)，容量为 \(w(v)\)。
    • 若 \(w(v) < 0\)，添加边 \((v, t)\)，容量为 \(-w(v)\)。
  • 对原图中每条有向边 \((u, v) \in E\)，在新图中添加边 \((u, v)\)，容量为 无穷大（在实现中可用一个足够大的数，如 \(\sum_{w>0} w(v) + 1\)）。

3.2 直观解释

  • 从源点 \(s\) 到正权顶点的边：表示选择该顶点能获得的收益。若在最小割中这条边被割掉（即不从 \(s\) 到该顶点），意味着我们不选该顶点，从而损失这份收益。
  • 从负权顶点到汇点 \(t\) 的边：表示选择该顶点需付出的代价。若在最小割中这条边被割掉（即该顶点不能到达 \(t\)），意味着我们选了该顶点，从而付出代价。
  • 原图的有向边容量设为无穷大，确保不会被割，从而强制满足闭合性质：若 \(u\) 在闭合子图中（即与 \(s\) 相连的一侧），则 \(v\) 也必须与 \(s\) 在同一侧，否则割会包含无穷大的边，不是最小割。

4. 最小割与最大权闭合子图的关系

记新构造的网络为 \(N\)，其最小割为 \((S, T)\)，其中 \(s \in S\)， \(t \in T\)。

定义闭合子图：

\[C = S \setminus \{s\} \]

即，所有在最小割中与源点 \(s\) 同侧的原图顶点的集合。

闭合性证明：
若 \(u \in C\) 且存在边 \((u, v)\) 在原图中，假设 \(v \notin C\)，则 \(v \in T\)。那么边 \((u, v)\) 在 \(N\) 中是从 \(S\) 到 \(T\) 的边，但它的容量是无穷大，这与最小割的有限性矛盾。因此 \(v\) 必须在 \(C\) 中。闭合性得证。

权值计算：
设：

  • \(W^+ = \sum_{w(v) > 0} w(v)\) 所有正权之和（即所有潜在收益）。
  • 最小割的容量 = 从 \(S\) 到 \(T\) 的边的容量和。

可以证明：

\[\text{最大权闭合子图的权值和} = W^+ - \text{最小割容量} \]

推导：
最小割包含两种边：

  1. 从 \(s\) 到某个正权顶点 \(v\)（若 \(v \in T\)，即 \(v \notin C\)），容量 \(w(v)\)，表示放弃该正权顶点的收益。
  2. 从某个负权顶点 \(u\) 到 \(t\)（若 \(u \in S\)，即 \(u \in C\)），容量 \(-w(u)\)，表示承担该负权顶点的代价。

所以：

\[\text{最小割容量} = \sum_{v \notin C, w(v)>0} w(v) \;+\; \sum_{u \in C, w(u)<0} (-w(u)) \]

因此：

\[W^+ - \text{最小割容量} = \sum_{v \in C, w(v)>0} w(v) \;+\; \sum_{u \in C, w(u)<0} w(u) = \sum_{v \in C} w(v) \]

这正是闭合子图 \(C\) 的总权值。

5. 求解步骤总结

  1. 输入：有向图 \(G=(V,E)\)，权值函数 \(w(v)\)。
  2. 构造网络流图 \(N\)：
    • 创建源点 \(s\) 和汇点 \(t\)。
    • 对每个 \(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 = \{ v \in V \mid v \text{ 在 } S \text{ 中} \}\)（排除源点 \(s\)）。
  5. 计算最大权值：
    • 可计算为： \(W^+ - \text{最小割容量}\)，也可直接求和 \(\sum_{v \in C} w(v)\)。

6. 一个简单例子

假设有向图有三个顶点 \(A, B, C\)，权值分别为 \(+5, -2, +3\)。
有向边： \(A \to B\)， \(B \to C\)。

构造网络：

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

跑最大流/最小割：

  • 若割包含 \(s \to A\)（容量 5），则因无穷大边不能割，必须割 \(B \to t\)（2）和 \(s \to C\)（3），总容量 10。
  • 若割不包含 \(s \to A\)，则 \(A\) 与 \(s\) 分离，但 \(A\) 到 \(B\) 无穷大，所以 \(B\) 也必须与 \(s\) 同侧？等等，分析需仔细，但直觉上：
    最小割应放弃 \(A\)（不选 \(A\)）以避免必须选负权 \(B\) 的代价。
    计算得：最小割容量 = \(s \to A\) 的 5（放弃 \(A\)）+ \(B \to t\) 的 2（选了 \(B\) 的代价）+ 可能 \(s \to C\) 的 3（放弃 \(C\)）。但我们可通过不选 \(A\) 来避免选 \(B\)，从而不选 \(C\)? 实际上，闭合子图必须满足：若选 \(A\) 则必选 \(B\)，若选 \(B\) 则必选 \(C\)。
    最优解是：
    • 选 \(\{C\}\) 权值和 3。
    • 或选 \(\{\}\) 权值和 0。
    • 不能只选 \(A\) 或 \(\{A,B\}\) 等因为会引入负权。
      实际最小割给出 \(C = \{C\}\)，权值和 3。

7. 算法复杂度与实现注意

  • 构造的网络有 \(|V|+2\) 个顶点，\(|E|+|V|\) 条边。
  • 需要运行一次最大流算法。若使用 Dinic 算法，复杂度为 \(O(|V|^2 |E|)\) 或更优的 \(O(|E| \sqrt{|V|})\) 对二分单位容量图（此处非单位，但可通过容量缩放等优化）。
  • 无穷大容量可用一个大于所有正权值之和的数代替，以确保不被割。

8. 应用场景

  • 项目选择问题（如上例）。
  • 选矿问题（需先开采某些矿石才能开采其他）。
  • 在文献引用网络中选取高影响力论文集合（依赖引用关系）。
  • 某些形式的病毒营销收益最大化问题（需激活前置节点）。

这样，你就掌握了最大权闭合子图问题的定义、转化方法、求解步骤及应用。

最大权闭合子图（Maximum Weight Closure of a Graph）问题 我将详细讲解 最大权闭合子图问题 ，包括问题定义、如何转化为最小割/最大流问题，以及完整的求解步骤。 1. 问题描述 我们有一个 有向图 \( G = (V, E) \)。每个顶点 \( v \) 都有一个 权值 \( w(v) \)，可为正、负或零。 一个 闭合子图（Closure） 是指顶点集的一个子集 \( C \subseteq V \)，满足： 若 \( u \in C \)，且存在一条从 \( u \) 到 \( v \) 的有向边 \( (u, v) \in E \)，则 \( v \) 也必须属于 \( C \)。 换句话说，闭合子图是一个“封闭”的点集：从集合中任意点出发，沿着有向边走，永远不会走出这个集合。 目标 ：在所有可能的闭合子图中，找到一个 权值和最大 的闭合子图 \( C^* \)，即最大化： \[ \sum_ {v \in C} w(v) \] 2. 问题理解与例子 例子 ： 假设一个工程项目的依赖图，每个顶点代表一个任务或资源，权值是完成该任务的收益（正）或成本（负）。如果任务 A 依赖任务 B（即 A 需要 B 的输出），则有一条边从 A 指向 B（表示：若选择 A，则必须选择 B）。 我们希望选择一组任务，满足所有依赖关系，并使得总收益最大。这就是一个最大权闭合子图问题。 重要观察 ： 闭合子图性质保证了依赖关系的满足。 正权顶点是我们想选的（增加总权值），负权顶点是我们想避免的（减少总权值）。 但为了选某些正权顶点，可能不得不选一些它们所依赖的负权顶点，因此需要权衡。 3. 转化为最小割问题 最大权闭合子图可以通过 构造一个网络流模型 ，并计算其 最小割 来求解。步骤如下： 3.1 构造网络 源点 \( s \) 和汇点 \( t \)。 对原图中每个顶点 \( v \)： 若 \( w(v) > 0 \)，添加边 \( (s, v) \)，容量为 \( w(v) \)。 若 \( w(v) < 0 \)，添加边 \( (v, t) \)，容量为 \( -w(v) \)。 对原图中每条有向边 \( (u, v) \in E \)，在新图中添加边 \( (u, v) \)，容量为 无穷大 （在实现中可用一个足够大的数，如 \( \sum_ {w>0} w(v) + 1 \)）。 3.2 直观解释 从源点 \( s \) 到正权顶点的边：表示选择该顶点能获得的收益。若在最小割中这条边被割掉（即不从 \( s \) 到该顶点），意味着我们不选该顶点，从而损失这份收益。 从负权顶点到汇点 \( t \) 的边：表示选择该顶点需付出的代价。若在最小割中这条边被割掉（即该顶点不能到达 \( t \)），意味着我们选了该顶点，从而付出代价。 原图的有向边容量设为无穷大，确保 不会被割 ，从而强制满足闭合性质：若 \( u \) 在闭合子图中（即与 \( s \) 相连的一侧），则 \( v \) 也必须与 \( s \) 在同一侧，否则割会包含无穷大的边，不是最小割。 4. 最小割与最大权闭合子图的关系 记新构造的网络为 \( N \)，其最小割为 \( (S, T) \)，其中 \( s \in S \)， \( t \in T \)。 定义闭合子图 ： \[ C = S \setminus \{s\} \] 即，所有在最小割中与源点 \( s \) 同侧的 原图顶点 的集合。 闭合性证明 ： 若 \( u \in C \) 且存在边 \( (u, v) \) 在原图中，假设 \( v \notin C \)，则 \( v \in T \)。那么边 \( (u, v) \) 在 \( N \) 中是从 \( S \) 到 \( T \) 的边，但它的容量是无穷大，这与最小割的有限性矛盾。因此 \( v \) 必须在 \( C \) 中。闭合性得证。 权值计算 ： 设： \( W^+ = \sum_ {w(v) > 0} w(v) \) 所有正权之和（即所有潜在收益）。 最小割的容量 = 从 \( S \) 到 \( T \) 的边的容量和。 可以证明： \[ \text{最大权闭合子图的权值和} = W^+ - \text{最小割容量} \] 推导 ： 最小割包含两种边： 从 \( s \) 到某个正权顶点 \( v \)（若 \( v \in T \)，即 \( v \notin C \)），容量 \( w(v) \)，表示放弃该正权顶点的收益。 从某个负权顶点 \( u \) 到 \( t \)（若 \( u \in S \)，即 \( u \in C \)），容量 \( -w(u) \)，表示承担该负权顶点的代价。 所以： \[ \text{最小割容量} = \sum_ {v \notin C, w(v)>0} w(v) \;+\; \sum_ {u \in C, w(u) <0} (-w(u)) \] 因此： \[ W^+ - \text{最小割容量} = \sum_ {v \in C, w(v)>0} w(v) \;+\; \sum_ {u \in C, w(u)<0} w(u) = \sum_ {v \in C} w(v) \] 这正是闭合子图 \( C \) 的总权值。 5. 求解步骤总结 输入 ：有向图 \( G=(V,E) \)，权值函数 \( w(v) \)。 构造网络流图 \( N \)： 创建源点 \( s \) 和汇点 \( t \)。 对每个 \( 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 = \{ v \in V \mid v \text{ 在 } S \text{ 中} \} \)（排除源点 \( s \)）。 计算最大权值 ： 可计算为： \( W^+ - \text{最小割容量} \)，也可直接求和 \( \sum_ {v \in C} w(v) \)。 6. 一个简单例子 假设有向图有三个顶点 \( A, B, C \)，权值分别为 \( +5, -2, +3 \)。 有向边： \( A \to B \)， \( B \to C \)。 构造网络： \( s \to A \) 容量 5，\( s \to C \) 容量 3。 \( B \to t \) 容量 2。 \( A \to B \) 容量 \( +\infty \)， \( B \to C \) 容量 \( +\infty \)。 跑最大流/最小割： 若割包含 \( s \to A \)（容量 5），则因无穷大边不能割，必须割 \( B \to t \)（2）和 \( s \to C \)（3），总容量 10。 若割不包含 \( s \to A \)，则 \( A \) 与 \( s \) 分离，但 \( A \) 到 \( B \) 无穷大，所以 \( B \) 也必须与 \( s \) 同侧？等等，分析需仔细，但直觉上： 最小割应放弃 \( A \)（不选 \( A \)）以避免必须选负权 \( B \) 的代价。 计算得：最小割容量 = \( s \to A \) 的 5（放弃 \( A \)）+ \( B \to t \) 的 2（选了 \( B \) 的代价）+ 可能 \( s \to C \) 的 3（放弃 \( C \)）。但我们可通过不选 \( A \) 来避免选 \( B \)，从而不选 \( C \)? 实际上，闭合子图必须满足：若选 \( A \) 则必选 \( B \)，若选 \( B \) 则必选 \( C \)。 最优解是： 选 \( \{C\} \) 权值和 3。 或选 \( \{\} \) 权值和 0。 不能只选 \( A \) 或 \( \{A,B\} \) 等因为会引入负权。 实际最小割给出 \( C = \{C\} \)，权值和 3。 7. 算法复杂度与实现注意 构造的网络有 \( |V|+2 \) 个顶点，\( |E|+|V| \) 条边。 需要运行一次最大流算法。若使用 Dinic 算法，复杂度为 \( O(|V|^2 |E|) \) 或更优的 \( O(|E| \sqrt{|V|}) \) 对二分单位容量图（此处非单位，但可通过容量缩放等优化）。 无穷大容量可用一个大于所有正权值之和的数代替，以确保不被割。 8. 应用场景 项目选择问题（如上例）。 选矿问题（需先开采某些矿石才能开采其他）。 在文献引用网络中选取高影响力论文集合（依赖引用关系）。 某些形式的病毒营销收益最大化问题（需激活前置节点）。 这样，你就掌握了 最大权闭合子图问题 的定义、转化方法、求解步骤及应用。