基于线性规划的图最大闭合子图问题求解示例
字数 1969 2025-11-08 10:02:38

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

题目描述
最大闭合子图问题（Maximum Closure Problem）是图论与线性规划结合的一个经典问题。给定一个有向图 \(G = (V, E)\)，每个顶点 \(v \in V\) 有一个权重 \(w_v\)（可为正、负或零）。闭合子图（Closure）指顶点子集 \(S \subseteq V\)，满足：若 \(u \in S\) 且存在有向边 \((u, v) \in E\)，则 \(v \in S\)（即从 \(S\) 中顶点出发的边必须指向 \(S\) 内部）。目标是选择闭合子图 \(S\)，使其权重和 \(\sum_{v \in S} w_v\) 最大。

应用场景
例如在项目管理中，顶点代表任务（权重为收益），边代表依赖关系（任务 \(u\) 完成后才能启动 \(v\)）。最大闭合子图对应收益最大的可行任务集合。

解题过程

  1. 问题建模为线性规划
    引入决策变量 \(x_v \in \{0, 1\}\)：若 \(x_v = 1\) 表示顶点 \(v\) 被选入 \(S\)，否则为 0。目标函数为最大化总权重：

\[ \max \sum_{v \in V} w_v x_v \]

闭合性约束：对每条边 \((u, v) \in E\)，若 \(u\) 被选（\(x_u = 1\)），则 \(v\) 必须被选（\(x_v = 1\)），即 \(x_u \leq x_v\)。整体模型为：

\[ \begin{align} \max \quad & \sum_{v \in V} w_v x_v \\ \text{s.t.} \quad & x_u \leq x_v, \quad \forall (u, v) \in E \\ & x_v \in \{0, 1\}, \quad \forall v \in V \end{align} \]

  1. 整数规划松弛为线性规划
    将 \(x_v \in \{0, 1\}\) 松弛为 \(0 \leq x_v \leq 1\)。由于约束矩阵是全单模的（Totally Unimodular），线性规划的最优解自动为整数解（0 或 1），因此可直接用线性规划求解。

  2. 构造对偶问题（最小割模型）
    通过最大流/最小割算法高效求解：

    • 构建流网络：添加源点 \(s\) 和汇点 \(t\)。
      • 对权重 \(w_v > 0\) 的顶点，从 \(s\) 向 \(v\) 连容量 \(w_v\) 的边（选 \(v\) 获益）。
      • 对权重 \(w_v < 0\) 的顶点，从 \(v\) 向 \(t\) 连容量 \(-w_v\) 的边（不选 \(v\) 避免损失）。
      • 对每条边 \((u, v) \in E\)，从 \(u\) 向 \(v\) 连容量 \(\infty\) 的边（保证闭合性）。
    • 计算 \(s-t\) 最小割：割集将顶点分为包含 \(s\) 的集合 \(S\) 和包含 \(t\) 的集合 \(T\)。
    • 最大闭合子图即为 \(S \setminus \{s\}\)，其权重 = 正权重之和 − 最小割容量。

  3. 示例计算
    考虑图：顶点集 \(V = \{1, 2, 3\}\)，边 \((1, 2), (1, 3)\)，权重 \(w_1 = 3, w_2 = -2, w_3 = -1\)。

    • 正权重和 = \(3\)。
    • 建流网络：\(s \to 1\)（容量 3），\(2 \to t\)（容量 2），\(3 \to t\)（容量 1），边 \((1,2)\) 和 \((1,3)\) 容量 \(\infty\)。
    • 最小割：割集 \(\{s, 1, 2, 3\} / \{t\}\) 容量 = \(2 + 1 = 3\)（割边为 \(2 \to t, 3 \to t\)），或割集 \(\{s\} / \{1,2,3,t\}\) 容量 = 3（割边为 \(s \to 1\)）。最小割容量 = 3。
    • 最大闭合子图权重 = \(3 - 3 = 0\)，即 \(S = \emptyset\)（选顶点 1 必选 2 和 3，总权重 \(3 - 2 - 1 = 0\)，不如不选）。

  4. 算法总结
    通过线性规划松弛和网络流转化，将 NP-hard 的整数规划问题转化为多项式时间可解问题，体现了线性规划在图优化中的强大作用。

基于线性规划的图最大闭合子图问题求解示例 题目描述 最大闭合子图问题（Maximum Closure Problem）是图论与线性规划结合的一个经典问题。给定一个有向图 \( G = (V, E) \)，每个顶点 \( v \in V \) 有一个权重 \( w_ v \)（可为正、负或零）。闭合子图（Closure）指顶点子集 \( S \subseteq V \)，满足：若 \( u \in S \) 且存在有向边 \( (u, v) \in E \)，则 \( v \in S \)（即从 \( S \) 中顶点出发的边必须指向 \( S \) 内部）。目标是选择闭合子图 \( S \)，使其权重和 \( \sum_ {v \in S} w_ v \) 最大。 应用场景 例如在项目管理中，顶点代表任务（权重为收益），边代表依赖关系（任务 \( u \) 完成后才能启动 \( v \)）。最大闭合子图对应收益最大的可行任务集合。 解题过程 问题建模为线性规划 引入决策变量 \( x_ v \in \{0, 1\} \)：若 \( x_ v = 1 \) 表示顶点 \( v \) 被选入 \( S \)，否则为 0。目标函数为最大化总权重： \[ \max \sum_ {v \in V} w_ v x_ v \] 闭合性约束：对每条边 \( (u, v) \in E \)，若 \( u \) 被选（\( x_ u = 1 \)），则 \( v \) 必须被选（\( x_ v = 1 \)），即 \( x_ u \leq x_ v \)。整体模型为： \[ \begin{align} \max \quad & \sum_ {v \in V} w_ v x_ v \\ \text{s.t.} \quad & x_ u \leq x_ v, \quad \forall (u, v) \in E \\ & x_ v \in \{0, 1\}, \quad \forall v \in V \end{align} \] 整数规划松弛为线性规划 将 \( x_ v \in \{0, 1\} \) 松弛为 \( 0 \leq x_ v \leq 1 \)。由于约束矩阵是全单模的（Totally Unimodular），线性规划的最优解自动为整数解（0 或 1），因此可直接用线性规划求解。 构造对偶问题（最小割模型） 通过最大流/最小割算法高效求解： 构建流网络：添加源点 \( s \) 和汇点 \( t \)。 对权重 \( w_ v > 0 \) 的顶点，从 \( s \) 向 \( v \) 连容量 \( w_ v \) 的边（选 \( v \) 获益）。 对权重 \( w_ v < 0 \) 的顶点，从 \( v \) 向 \( t \) 连容量 \( -w_ v \) 的边（不选 \( v \) 避免损失）。 对每条边 \( (u, v) \in E \)，从 \( u \) 向 \( v \) 连容量 \( \infty \) 的边（保证闭合性）。 计算 \( s-t \) 最小割：割集将顶点分为包含 \( s \) 的集合 \( S \) 和包含 \( t \) 的集合 \( T \)。 最大闭合子图即为 \( S \setminus \{s\} \)，其权重 = 正权重之和 − 最小割容量。 示例计算 考虑图：顶点集 \( V = \{1, 2, 3\} \)，边 \( (1, 2), (1, 3) \)，权重 \( w_ 1 = 3, w_ 2 = -2, w_ 3 = -1 \)。 正权重和 = \( 3 \)。 建流网络：\( s \to 1 \)（容量 3），\( 2 \to t \)（容量 2），\( 3 \to t \)（容量 1），边 \( (1,2) \) 和 \( (1,3) \) 容量 \( \infty \)。 最小割：割集 \( \{s, 1, 2, 3\} / \{t\} \) 容量 = \( 2 + 1 = 3 \)（割边为 \( 2 \to t, 3 \to t \)），或割集 \( \{s\} / \{1,2,3,t\} \) 容量 = 3（割边为 \( s \to 1 \)）。最小割容量 = 3。 最大闭合子图权重 = \( 3 - 3 = 0 \)，即 \( S = \emptyset \)（选顶点 1 必选 2 和 3，总权重 \( 3 - 2 - 1 = 0 \)，不如不选）。 算法总结 通过线性规划松弛和网络流转化，将 NP-hard 的整数规划问题转化为多项式时间可解问题，体现了线性规划在图优化中的强大作用。