基于线性规划的图最大闭合子图问题求解示例
字数 1611 2025-11-03 08:34:44

基于线性规划的图最大闭合子图问题求解示例

题目描述
最大闭合子图问题旨在从有向图中选取一个顶点子集，使得子集中任意顶点的后继也属于该子集（即闭合性），同时最大化子集中顶点的权重之和。该问题在项目选型、资源依赖分析中具有重要应用。例如，顶点代表项目（权重为收益），边代表依赖关系，需选择收益最大且满足依赖约束的项目集合。

问题建模

  1. 设有向图 \(G = (V, E)\)，顶点 \(v_i\) 的权重为 \(w_i\)（可正可负）。
  2. 定义二元变量 \(x_i \in \{0,1\}\)：若 \(x_i = 1\) 表示顶点 \(v_i\) 被选入子图。
  3. 闭合性约束：对每条边 \((v_i, v_j) \in E\)，若 \(v_i\) 被选（\(x_i = 1\)），则 \(v_j\) 必须被选（\(x_j = 1\)）。
  4. 目标函数：最大化总权重 \(\sum_{i} w_i x_i\)。

线性规划松弛与转化
直接求解整数规划较困难，需通过以下步骤转化为最小割问题（可高效求解）：

  1. 构造辅助网络：

    • 添加源点 \(s\) 和汇点 \(t\)。
    • 对每个顶点 \(v_i\)：
      • 若 \(w_i > 0\)，从 \(s\) 到 \(v_i\) 连容量为 \(w_i\) 的边（表示收益）。
      • 若 \(w_i < 0\)，从 \(v_i\) 到 \(t\) 连容量为 \(-w_i\) 的边（表示成本）。
    • 对每条边 \((v_i, v_j) \in E\)，从 \(v_i\) 到 \(v_j\) 连容量为无穷大的边（保证闭合性）。

  2. 最小割的意义：

    • 将网络划分为包含 \(s\) 的集合 \(S\) 和包含 \(t\) 的集合 \(T\)。
    • 割的容量 = \(\sum_{v_i \in T} w_i^+ + \sum_{v_i \in S} (-w_i^-)\)（其中 \(w_i^+ = \max(w_i,0)\)，\(w_i^- = \min(w_i,0)\)）。
    • 最大闭合子图的权重 = 正权重总和 − 最小割容量。

求解步骤

  1. 计算正权重和： \(W^+ = \sum_{w_i > 0} w_i\)。
  2. 求解最小割：使用最大流算法（如Dinic算法）得到最小割容量 \(C\)。
  3. 还原解：
    • 最小割对应的 \(S\) 集合（不含 \(s\)）即为最大闭合子图的顶点集合。
    • 最大权重和 = \(W^+ - C\)。

实例演示
假设有向图包含顶点 \(v_1, v_2, v_3\)，权重分别为 \(3, -2, 1\)，边为 \((v_1, v_2), (v_1, v_3)\)：

  1. 构造网络：
    • \(s \to v_1\)（容量3），\(s \to v_3\)（容量1）；
    • \(v_2 \to t\)（容量2）；
    • \(v_1 \to v_2\)、\(v_1 \to v_3\)（容量无穷大）。
  2. 最小割为 \(\{s, v_1, v_3\}\) 与 \(\{v_2, t\}\)，容量 \(C = 2\)。
  3. 最大闭合子图为 \(\{v_1, v_3\}\)，权重和 = \((3+1) - 2 = 2\)。

关键点说明

  • 无穷大边确保若 \(v_i\) 在 \(S\) 中且存在边 \((v_i, v_j)\)，则 \(v_j\) 不能在 \(T\) 中（否则割容量无穷大，非最小）。
  • 通过最小割问题间接求解，避免了直接处理整数约束，体现了线性规划与图论的巧妙结合。
基于线性规划的图最大闭合子图问题求解示例 题目描述 最大闭合子图问题旨在从有向图中选取一个顶点子集，使得子集中任意顶点的后继也属于该子集（即闭合性），同时最大化子集中顶点的权重之和。该问题在项目选型、资源依赖分析中具有重要应用。例如，顶点代表项目（权重为收益），边代表依赖关系，需选择收益最大且满足依赖约束的项目集合。 问题建模 设有向图 \( G = (V, E) \)，顶点 \( v_ i \) 的权重为 \( w_ i \)（可正可负）。 定义二元变量 \( x_ i \in \{0,1\} \)：若 \( x_ i = 1 \) 表示顶点 \( v_ i \) 被选入子图。 闭合性约束：对每条边 \( (v_ i, v_ j) \in E \)，若 \( v_ i \) 被选（\( x_ i = 1 \)），则 \( v_ j \) 必须被选（\( x_ j = 1 \)）。 目标函数：最大化总权重 \( \sum_ {i} w_ i x_ i \)。 线性规划松弛与转化 直接求解整数规划较困难，需通过以下步骤转化为最小割问题（可高效求解）： 构造辅助网络 ： 添加源点 \( s \) 和汇点 \( t \)。 对每个顶点 \( v_ i \)： 若 \( w_ i > 0 \)，从 \( s \) 到 \( v_ i \) 连容量为 \( w_ i \) 的边（表示收益）。 若 \( w_ i < 0 \)，从 \( v_ i \) 到 \( t \) 连容量为 \( -w_ i \) 的边（表示成本）。 对每条边 \( (v_ i, v_ j) \in E \)，从 \( v_ i \) 到 \( v_ j \) 连容量为无穷大的边（保证闭合性）。 最小割的意义 ： 将网络划分为包含 \( s \) 的集合 \( S \) 和包含 \( t \) 的集合 \( T \)。 割的容量 = \( \sum_ {v_ i \in T} w_ i^+ + \sum_ {v_ i \in S} (-w_ i^-) \)（其中 \( w_ i^+ = \max(w_ i,0) \)，\( w_ i^- = \min(w_ i,0) \)）。 最大闭合子图的权重 = 正权重总和 − 最小割容量。 求解步骤 计算正权重和 ： \( W^+ = \sum_ {w_ i > 0} w_ i \)。 求解最小割 ：使用最大流算法（如Dinic算法）得到最小割容量 \( C \)。 还原解 ： 最小割对应的 \( S \) 集合（不含 \( s \)）即为最大闭合子图的顶点集合。 最大权重和 = \( W^+ - C \)。 实例演示 假设有向图包含顶点 \( v_ 1, v_ 2, v_ 3 \)，权重分别为 \( 3, -2, 1 \)，边为 \( (v_ 1, v_ 2), (v_ 1, v_ 3) \)： 构造网络： \( s \to v_ 1 \)（容量3），\( s \to v_ 3 \)（容量1）； \( v_ 2 \to t \)（容量2）； \( v_ 1 \to v_ 2 \)、\( v_ 1 \to v_ 3 \)（容量无穷大）。 最小割为 \( \{s, v_ 1, v_ 3\} \) 与 \( \{v_ 2, t\} \)，容量 \( C = 2 \)。 最大闭合子图为 \( \{v_ 1, v_ 3\} \)，权重和 = \( (3+1) - 2 = 2 \)。 关键点说明 无穷大边确保若 \( v_ i \) 在 \( S \) 中且存在边 \( (v_ i, v_ j) \)，则 \( v_ j \) 不能在 \( T \) 中（否则割容量无穷大，非最小）。 通过最小割问题间接求解，避免了直接处理整数约束，体现了线性规划与图论的巧妙结合。