基于线性规划的图最大闭合子图问题求解示例
字数 1967 2025-11-05 08:30:58

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

问题描述
给定一个有向图 \(G = (V, E)\)，每个顶点 \(v_i\) 有一个权重 \(w_i\)（可为正、负或零）。闭合子图（Closed Subgraph）定义为：若一个子图的顶点集合 \(S \subseteq V\) 满足，对于任意 \(S\) 中的顶点 \(u\)，所有由 \(u\) 出发的有向边指向的顶点也属于 \(S\)（即 \(S\) 关于有向边封闭）。最大闭合子图问题是寻找一个闭合子图，使其顶点权重之和最大。

应用场景
该问题常用于项目选择依赖分析（如某些项目需先完成其他项目）、资源分配与风险控制等场景。

解题过程

步骤1：问题转化为最小割问题

  1. 构造一个流网络：

    • 添加源点 \(s\) 和汇点 \(t\)。
    • 对每个顶点 \(v_i\)：
      • 若 \(w_i > 0\)，从 \(s\) 到 \(v_i\) 连一条容量为 \(w_i\) 的边（表示选择 \(v_i\) 的收益）。
      • 若 \(w_i < 0\)，从 \(v_i\) 到 \(t\) 连一条容量为 \(-w_i\) 的边（表示不选 \(v_i\) 可避免损失）。
    • 对原图每条有向边 \((u, v) \in E\)，添加容量为 \(+\infty\) 的边（确保闭合性：若选 \(u\) 则必选 \(v\)）。

  2. 定理：最大闭合子图的权重和 = 所有正权重之和 − 该流网络的最小割容量。

步骤2：线性规划建模

  • 定义变量 \(x_i \in \{0,1\}\) 表示顶点 \(v_i\) 是否被选入子图。
  • 目标函数：最大化 \(\sum_{i} w_i x_i\)。
  • 约束条件（闭合性）：对每条边 \((u,v) \in E\)，有 \(x_u \leq x_v\)（若选 \(u\) 则必选 \(v\)）。
  • 松弛为线性规划（LP）：允许 \(x_i \in [0,1]\)，但最优解必为整数（因约束矩阵为全单模矩阵）。

步骤3：求解LP的对偶问题

  1. 原LP：

\[\max \sum_i w_i x_i \quad \text{s.t.} \quad x_u - x_v \leq 0 \ (\forall (u,v) \in E), \ 0 \leq x_i \leq 1. \]

  1. 引入对偶变量 \(y_{uv} \geq 0\)（对应边约束）和 \(a_i, b_i \geq 0\)（对应边界约束 \(x_i \leq 1\) 和 \(-x_i \leq 0\)）：

\[\min \sum_i b_i \quad \text{s.t.} \quad b_i - a_i + \sum_{u: (u,i) \in E} y_{ui} - \sum_{v: (i,v) \in E} y_{iv} = w_i \ (\forall i), \ a_i, b_i, y_{uv} \geq 0. \]

  1. 通过对偶变换可验证，该对偶问题等价于流网络中的最小割问题。

步骤4：算法实现

  1. 构建流网络（如步骤1）。
  2. 使用最大流算法（如Dinic或Push-Relabel）计算 \(s-t\) 最小割。
  3. 最小割将顶点分为两部分：
    • \(S\)：包含 \(s\) 的集合（对应 \(x_i = 1\)，被选中的顶点）。
    • 验证 \(S\) 满足闭合性（因无穷大边确保约束成立）。
  4. 计算权重和：\(\sum_{v_i \in S} w_i\)。

步骤5：实例验证

  • 设图有顶点 \(\{1,2,3\}\)，权重 \(w_1=3, w_2=-2, w_3=1\)，边 \((1,2), (2,3)\)。
  • 流网络：
    • \(s \to 1\)（容量3），\(s \to 3\)（容量1）；
    • \(2 \to t\)（容量2）；
    • 边 \((1,2), (2,3)\) 容量无穷大。
  • 最小割：割集 \(\{s,1,2,3\}\) 与 \(\{t\}\)，容量=2（由边 \(2 \to t\) 贡献）。
  • 最大权重和 = 正权重和 \((3+1) - 2 = 2\)，对应闭合子图 \(\{1,2,3\}\)。

总结
通过线性规划松弛与对偶理论，将最大闭合子图问题转化为最小割问题，利用网络流算法高效求解。该方法保证了最优解且复杂度为多项式时间（如使用Dinic算法为 \(O(V^2E)\)）。

基于线性规划的图最大闭合子图问题求解示例 问题描述 给定一个有向图 \( G = (V, E) \)，每个顶点 \( v_ i \) 有一个权重 \( w_ i \)（可为正、负或零）。闭合子图（Closed Subgraph）定义为：若一个子图的顶点集合 \( S \subseteq V \) 满足，对于任意 \( S \) 中的顶点 \( u \)，所有由 \( u \) 出发的有向边指向的顶点也属于 \( S \)（即 \( S \) 关于有向边封闭）。最大闭合子图问题是寻找一个闭合子图，使其顶点权重之和最大。 应用场景 该问题常用于项目选择依赖分析（如某些项目需先完成其他项目）、资源分配与风险控制等场景。 解题过程 步骤1：问题转化为最小割问题 构造一个流网络： 添加源点 \( s \) 和汇点 \( t \)。 对每个顶点 \( v_ i \)： 若 \( w_ i > 0 \)，从 \( s \) 到 \( v_ i \) 连一条容量为 \( w_ i \) 的边（表示选择 \( v_ i \) 的收益）。 若 \( w_ i < 0 \)，从 \( v_ i \) 到 \( t \) 连一条容量为 \( -w_ i \) 的边（表示不选 \( v_ i \) 可避免损失）。 对原图每条有向边 \( (u, v) \in E \)，添加容量为 \( +\infty \) 的边（确保闭合性：若选 \( u \) 则必选 \( v \)）。 定理：最大闭合子图的权重和 = 所有正权重之和 − 该流网络的最小割容量。 步骤2：线性规划建模 定义变量 \( x_ i \in \{0,1\} \) 表示顶点 \( v_ i \) 是否被选入子图。 目标函数：最大化 \( \sum_ {i} w_ i x_ i \)。 约束条件（闭合性）：对每条边 \( (u,v) \in E \)，有 \( x_ u \leq x_ v \)（若选 \( u \) 则必选 \( v \)）。 松弛为线性规划（LP）：允许 \( x_ i \in [ 0,1 ] \)，但最优解必为整数（因约束矩阵为全单模矩阵）。 步骤3：求解LP的对偶问题 原LP： \[ \max \sum_ i w_ i x_ i \quad \text{s.t.} \quad x_ u - x_ v \leq 0 \ (\forall (u,v) \in E), \ 0 \leq x_ i \leq 1. \] 引入对偶变量 \( y_ {uv} \geq 0 \)（对应边约束）和 \( a_ i, b_ i \geq 0 \)（对应边界约束 \( x_ i \leq 1 \) 和 \( -x_ i \leq 0 \)）： \[ \min \sum_ i b_ i \quad \text{s.t.} \quad b_ i - a_ i + \sum_ {u: (u,i) \in E} y_ {ui} - \sum_ {v: (i,v) \in E} y_ {iv} = w_ i \ (\forall i), \ a_ i, b_ i, y_ {uv} \geq 0. \] 通过对偶变换可验证，该对偶问题等价于流网络中的最小割问题。 步骤4：算法实现 构建流网络（如步骤1）。 使用最大流算法（如Dinic或Push-Relabel）计算 \( s-t \) 最小割。 最小割将顶点分为两部分： \( S \)：包含 \( s \) 的集合（对应 \( x_ i = 1 \)，被选中的顶点）。 验证 \( S \) 满足闭合性（因无穷大边确保约束成立）。 计算权重和：\( \sum_ {v_ i \in S} w_ i \)。 步骤5：实例验证 设图有顶点 \( \{1,2,3\} \)，权重 \( w_ 1=3, w_ 2=-2, w_ 3=1 \)，边 \( (1,2), (2,3) \)。 流网络： \( s \to 1 \)（容量3），\( s \to 3 \)（容量1）； \( 2 \to t \)（容量2）； 边 \( (1,2), (2,3) \) 容量无穷大。 最小割：割集 \( \{s,1,2,3\} \) 与 \( \{t\} \)，容量=2（由边 \( 2 \to t \) 贡献）。 最大权重和 = 正权重和 \( (3+1) - 2 = 2 \)，对应闭合子图 \( \{1,2,3\} \)。 总结 通过线性规划松弛与对偶理论，将最大闭合子图问题转化为最小割问题，利用网络流算法高效求解。该方法保证了最优解且复杂度为多项式时间（如使用Dinic算法为 \( O(V^2E) \)）。