基于线性规划的图最小割问题的多项式时间算法求解示例
字数 3195 2025-12-09 11:28:12

基于线性规划的图最小割问题的多项式时间算法求解示例

题目描述

考虑一个无向连通图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。每条边 \(e \in E\) 有一个非负容量 \(c_e\)。图的一个割 \((S, V \setminus S)\) 是将顶点集 \(V\) 分割成两个非空子集 \(S\) 和 \(V \setminus S\)，割的容量定义为所有连接 \(S\) 和 \(V \setminus S\) 的边的容量之和。本问题要求找到一个最小割，即容量最小的割。我们将通过将其转化为线性规划问题，并利用最大流最小割定理，设计一个多项式时间算法。

解题步骤

步骤1：问题建模

  1. 定义决策变量：对于每个顶点 \(i \in V\)，引入一个变量 \(x_i \in \{0, 1\}\)，表示顶点属于割的哪一侧。通常约定：令一个固定顶点 \(r \in V\) 始终在 \(S\) 中（即 \(x_r = 0\)），而其他顶点的取值决定其所属子集。但为了建模方便，我们采用另一种等价形式。
  2. 等价建模：对于每对顶点 \(i, j \in V\)，定义变量 \(y_{ij} \in \{0, 1\}\)，其中 \(y_{ij} = 1\) 表示顶点 \(i\) 和 \(j\) 位于割的不同侧，否则位于同一侧。注意 \(y_{ij} = y_{ji}\) 且 \(y_{ii} = 0\)。
  3. 目标函数：最小化割容量，即 \(\min \sum_{\{i, j\} \in E} c_{ij} y_{ij}\)。
  4. 约束条件：变量 \(y_{ij}\) 必须对应一个合法的割。一个重要观察是：对于任意三个顶点 \(i, j, k\)，如果 \(i\) 和 \(j\) 位于同一侧，且 \(j\) 和 \(k\) 位于同一侧，则 \(i\) 和 \(k\) 必须位于同一侧。这可以表达为三角不等式：\(y_{ik} \le y_{ij} + y_{jk}\)。同时，由于 \(r\) 固定在一侧，我们可以要求对于所有 \(i \neq r\)，有 \(y_{ri} \in \{0, 1\}\)，但 \(y_{ri} = 1\) 表示 \(i\) 在另一侧。实际上，这个模型是“度量标记”问题，其可行解对应于割。
  5. 整数规划模型：

\[ \begin{aligned} \min \quad & \sum_{\{i, j\} \in E} c_{ij} y_{ij} \\ \text{s.t.} \quad & y_{ij} \le y_{ik} + y_{jk} \quad \forall i, j, k \in V \\ & y_{ij} = y_{ji} \quad \forall i, j \in V \\ & y_{ii} = 0 \quad \forall i \in V \\ & y_{ij} \in \{0, 1\} \quad \forall i, j \in V \end{aligned} \]

注意：第一个约束是三角不等式，保证了 \(y\) 构成一个度量（在 \(\{0,1\}\) 值下）。但此模型规模为 \(O(|V|^3)\) 个约束，可能较大。

步骤2：线性规划松弛

  1. 松弛整数约束：将 \(y_{ij} \in \{0, 1\}\) 松弛为 \(0 \le y_{ij} \le 1\)。得到线性规划（LP）：

\[ \begin{aligned} \min \quad & \sum_{\{i, j\} \in E} c_{ij} y_{ij} \\ \text{s.t.} \quad & y_{ij} \le y_{ik} + y_{jk} \quad \forall i, j, k \in V \\ & y_{ij} = y_{ji} \quad \forall i, j \in V \\ & 0 \le y_{ij} \le 1 \quad \forall i, j \in V \end{aligned} \]

  1. 关键性质：可以证明，这个线性规划的最优解总是整数（即每个 \(y_{ij} \in \{0, 1\}\)）。原因是约束矩阵是全单模的，且右端项为整数。因此，求解此线性规划等价于求解原整数规划。

步骤3：转化为最大流问题

  1. 最大流最小割定理：在任意图中，从源点 \(s\) 到汇点 \(t\) 的最大流值等于最小 \(s-t\) 割的容量。对于无向图，可以将每条无向边替换为两条方向相反、容量均为 \(c_e\) 的有向边，然后应用有向图的最大流最小割定理。
  2. 全局最小割：全局最小割是任意一对顶点之间的最小割。可以通过固定一个顶点 \(s\)，然后对每个其他顶点 \(t \neq s\)，计算 \(s-t\) 最小割，并取最小值。但这需要 \(|V|-1\) 次最大流计算，虽然多项式时间但效率不高。
  3. 更高效的算法：可以使用 Stoer-Wagner 算法，其基本思想是不断合并顶点，直到图只剩一个顶点，过程中记录最小割值。该算法的时间复杂度为 \(O(|V|^3)\) 或 \(O(|V|(|E| + |V| \log |V|))\) 使用优先队列，是多项式时间。
  4. 算法步骤简述：
    a. 初始化当前图 \(G' = G\)，当前最小割值 \(\lambda = \infty\)。
    b. 当 \(G'\) 中顶点数大于 1 时：
    - 在 \(G'\) 上运行最大生成树类似的过程（Maximum Adjacency Search）：从一个任意顶点开始，每次将与其他已选顶点集合相邻边权和最大的顶点加入集合，记录最后加入的两个顶点 \(u\) 和 \(v\) 以及它们之间的割值 \(c\)。
    - 更新 \(\lambda = \min(\lambda, c)\)。
    - 合并顶点 \(u\) 和 \(v\)（即收缩边 \((u, v)\)），更新 \(G'\)。
    c. 返回 \(\lambda\) 作为最小割值。

步骤4：算法正确性证明概要

  1. 关键引理：在 Maximum Adjacency Search 过程中，最后加入的顶点 \(v\) 与之前已选集合之间的割，等于 \(v\) 与其他顶点（在原始图中）的割值。这保证了算法记录的割值是某个特定割的容量。
  2. 全局最小割包含性：可以证明，全局最小割一定会在某次迭代中被记录为 \(v\) 与已选集合之间的割。因此，算法最终会找到全局最小割。

步骤5：算法复杂度分析

  1. 每次迭代需要 \(O(|E| + |V| \log |V|)\) 时间（使用优先队列实现 Maximum Adjacency Search）。
  2. 总共 \(|V| - 1\) 次迭代，因此总时间复杂度为 \(O(|V|(|E| + |V| \log |V|))\)。
  3. 这是多项式时间，因为输入规模为 \(O(|V| + |E|)\)。

总结

本问题展示了如何将图的最小割问题建模为整数规划，通过线性规划松弛得到等价模型，并利用最大流最小割定理和 Stoer-Wagner 算法在多项式时间内求解。重点在于理解最小割与最大流对偶关系，以及如何通过图收缩技术高效找到全局最小割。

基于线性规划的图最小割问题的多项式时间算法求解示例 题目描述 考虑一个无向连通图 \( G = (V, E) \)，其中 \( V \) 是顶点集，\( E \) 是边集。每条边 \( e \in E \) 有一个非负容量 \( c_ e \)。图的一个割 \((S, V \setminus S)\) 是将顶点集 \( V \) 分割成两个非空子集 \( S \) 和 \( V \setminus S \)，割的容量定义为所有连接 \( S \) 和 \( V \setminus S \) 的边的容量之和。本问题要求找到一个最小割，即容量最小的割。我们将通过将其转化为线性规划问题，并利用最大流最小割定理，设计一个多项式时间算法。 解题步骤 步骤1：问题建模 定义决策变量 ：对于每个顶点 \( i \in V \)，引入一个变量 \( x_ i \in \{0, 1\} \)，表示顶点属于割的哪一侧。通常约定：令一个固定顶点 \( r \in V \) 始终在 \( S \) 中（即 \( x_ r = 0 \)），而其他顶点的取值决定其所属子集。但为了建模方便，我们采用另一种等价形式。 等价建模 ：对于每对顶点 \( i, j \in V \)，定义变量 \( y_ {ij} \in \{0, 1\} \)，其中 \( y_ {ij} = 1 \) 表示顶点 \( i \) 和 \( j \) 位于割的不同侧，否则位于同一侧。注意 \( y_ {ij} = y_ {ji} \) 且 \( y_ {ii} = 0 \)。 目标函数 ：最小化割容量，即 \( \min \sum_ {\{i, j\} \in E} c_ {ij} y_ {ij} \)。 约束条件 ：变量 \( y_ {ij} \) 必须对应一个合法的割。一个重要观察是：对于任意三个顶点 \( i, j, k \)，如果 \( i \) 和 \( j \) 位于同一侧，且 \( j \) 和 \( k \) 位于同一侧，则 \( i \) 和 \( k \) 必须位于同一侧。这可以表达为三角不等式：\( y_ {ik} \le y_ {ij} + y_ {jk} \)。同时，由于 \( r \) 固定在一侧，我们可以要求对于所有 \( i \neq r \)，有 \( y_ {ri} \in \{0, 1\} \)，但 \( y_ {ri} = 1 \) 表示 \( i \) 在另一侧。实际上，这个模型是“度量标记”问题，其可行解对应于割。 整数规划模型 ： \[ \begin{aligned} \min \quad & \sum_ {\{i, j\} \in E} c_ {ij} y_ {ij} \\ \text{s.t.} \quad & y_ {ij} \le y_ {ik} + y_ {jk} \quad \forall i, j, k \in V \\ & y_ {ij} = y_ {ji} \quad \forall i, j \in V \\ & y_ {ii} = 0 \quad \forall i \in V \\ & y_ {ij} \in \{0, 1\} \quad \forall i, j \in V \end{aligned} \] 注意：第一个约束是三角不等式，保证了 \( y \) 构成一个度量（在 \(\{0,1\}\) 值下）。但此模型规模为 \( O(|V|^3) \) 个约束，可能较大。 步骤2：线性规划松弛 松弛整数约束 ：将 \( y_ {ij} \in \{0, 1\} \) 松弛为 \( 0 \le y_ {ij} \le 1 \)。得到线性规划（LP）： \[ \begin{aligned} \min \quad & \sum_ {\{i, j\} \in E} c_ {ij} y_ {ij} \\ \text{s.t.} \quad & y_ {ij} \le y_ {ik} + y_ {jk} \quad \forall i, j, k \in V \\ & y_ {ij} = y_ {ji} \quad \forall i, j \in V \\ & 0 \le y_ {ij} \le 1 \quad \forall i, j \in V \end{aligned} \] 关键性质 ：可以证明，这个线性规划的最优解总是整数（即每个 \( y_ {ij} \in \{0, 1\} \)）。原因是约束矩阵是全单模的，且右端项为整数。因此，求解此线性规划等价于求解原整数规划。 步骤3：转化为最大流问题 最大流最小割定理 ：在任意图中，从源点 \( s \) 到汇点 \( t \) 的最大流值等于最小 \( s-t \) 割的容量。对于无向图，可以将每条无向边替换为两条方向相反、容量均为 \( c_ e \) 的有向边，然后应用有向图的最大流最小割定理。 全局最小割 ：全局最小割是任意一对顶点之间的最小割。可以通过固定一个顶点 \( s \)，然后对每个其他顶点 \( t \neq s \)，计算 \( s-t \) 最小割，并取最小值。但这需要 \( |V|-1 \) 次最大流计算，虽然多项式时间但效率不高。 更高效的算法 ：可以使用 Stoer-Wagner 算法，其基本思想是不断合并顶点，直到图只剩一个顶点，过程中记录最小割值。该算法的时间复杂度为 \( O(|V|^3) \) 或 \( O(|V|(|E| + |V| \log |V|)) \) 使用优先队列，是多项式时间。 算法步骤简述 ： a. 初始化当前图 \( G' = G \)，当前最小割值 \( \lambda = \infty \)。 b. 当 \( G' \) 中顶点数大于 1 时： - 在 \( G' \) 上运行最大生成树类似的过程（Maximum Adjacency Search）：从一个任意顶点开始，每次将与其他已选顶点集合相邻边权和最大的顶点加入集合，记录最后加入的两个顶点 \( u \) 和 \( v \) 以及它们之间的割值 \( c \)。 - 更新 \( \lambda = \min(\lambda, c) \)。 - 合并顶点 \( u \) 和 \( v \)（即收缩边 \( (u, v) \)），更新 \( G' \)。 c. 返回 \( \lambda \) 作为最小割值。 步骤4：算法正确性证明概要 关键引理 ：在 Maximum Adjacency Search 过程中，最后加入的顶点 \( v \) 与之前已选集合之间的割，等于 \( v \) 与其他顶点（在原始图中）的割值。这保证了算法记录的割值是某个特定割的容量。 全局最小割包含性 ：可以证明，全局最小割一定会在某次迭代中被记录为 \( v \) 与已选集合之间的割。因此，算法最终会找到全局最小割。 步骤5：算法复杂度分析 每次迭代需要 \( O(|E| + |V| \log |V|) \) 时间（使用优先队列实现 Maximum Adjacency Search）。 总共 \( |V| - 1 \) 次迭代，因此总时间复杂度为 \( O(|V|(|E| + |V| \log |V|)) \)。 这是多项式时间，因为输入规模为 \( O(|V| + |E|) \)。 总结 本问题展示了如何将图的最小割问题建模为整数规划，通过线性规划松弛得到等价模型，并利用最大流最小割定理和 Stoer-Wagner 算法在多项式时间内求解。重点在于理解最小割与最大流对偶关系，以及如何通过图收缩技术高效找到全局最小割。