基于线性规划的图最小割问题求解示例
问题描述
图最小割问题（Minimum Cut Problem）是图论中的经典问题：给定一个带权有向图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集，每条边 \((i, j) \in E\) 有一个非负容量 \(c_{ij}\)。问题要求将顶点集 \(V\) 划分为两个不相交子集 \(S\) 和 \(T\)（即 \(S \cup T = V\)，\(S \cap T = \emptyset\)），使得源点 \(s \in S\)，汇点 \(t \in T\)，且从 \(S\) 到 \(T\) 的所有边的容量之和最小。这个最小容量和称为图的最小割值。
解题思路
最小割问题可以通过线性规划建模求解。关键步骤包括：
- 定义决策变量：为每条边引入变量表示是否被割集包含。
- 约束条件：确保源点和汇点分属不同集合，且割集定义合理。
- 目标函数：最小化割集容量总和。
- 利用线性规划求解器得到最优解。
解题过程
1. 问题建模
- 定义二元决策变量 \(x_{ij} \in \{0, 1\}\) 表示边 \((i, j)\) 是否被割集包含（即是否从 \(S\) 到 \(T\)）。
- 定义辅助变量 \(y_i \in \{0, 1\}\) 表示顶点 \(i\) 属于集合 \(S\)（\(y_i = 1\)）还是 \(T\)（\(y_i = 0\)）。
目标函数为最小化割集容量：
\[\min \sum_{(i,j) \in E} c_{ij} x_{ij} \]
约束条件需满足：
- 若边 \((i, j)\) 被割（即 \(x_{ij} = 1\)），则顶点 \(i\) 必在 \(S\)，顶点 \(j\) 必在 \(T\)：
\[ x_{ij} \geq y_i - y_j \quad \forall (i,j) \in E \]
解释：当 \(y_i = 1\) 且 \(y_j = 0\) 时，\(y_i - y_j = 1\)，强制 \(x_{ij} \geq 1\)；由于 \(x_{ij}\) 为二元变量，等价于 \(x_{ij} = 1\)。其他情况下约束宽松。
- 源点 \(s\) 必须在 \(S\)（\(y_s = 1\)），汇点 \(t\) 必须在 \(T\)（\(y_t = 0\)）：
\[ y_s = 1, \quad y_t = 0 \]
- 变量取值范围：
\[ x_{ij} \in \{0, 1\}, \quad y_i \in \{0, 1\} \quad \forall i \in V, (i,j) \in E \]
2. 线性规划松弛
将整数约束松弛为连续变量：
\[0 \leq x_{ij} \leq 1, \quad 0 \leq y_i \leq 1 \]
松弛后的问题是一个线性规划，其最优解可通过单纯形法或内点法求解。根据最大流最小割定理，该线性规划的最优解即为原问题的最优解（整数解），无需额外整数规划步骤。
3. 求解与解释
- 使用线性规划求解器（如GLPK、CPLEX）求解松弛后的模型。
- 最优解中，若 \(y_i = 1\)，则顶点 \(i \in S\)；若 \(y_i = 0\)，则 \(i \in T\)。
- 割集为所有满足 \(x_{ij} = 1\) 的边 \((i,j)\)，即从 \(S\) 指向 \(T\) 的边。
- 目标函数值即为最小割容量。
示例验证
考虑一个简单图：顶点集 \(V = \{s, a, b, t\}\)，边集 \(E = \{(s,a):3, (s,b):2, (a,b):1, (a,t):2, (b,t):3\}\)。
- 建模后求解，得到最优解 \(y_s = 1, y_a = 1, y_b = 0, y_t = 0\)，割集为边 \((s,b)\) 和 \((a,t)\)，容量和为 \(2 + 2 = 4\)。
- 验证：最大流值也为 4，符合最大流最小割定理。
总结
通过线性规划建模，将图最小割问题转化为连续优化问题，利用现有工具高效求解。该方法适用于任意规模的带权图，体现了线性规划在图论问题中的强大应用。