基于线性规划的图最大密度子图问题的精确线性规划建模与求解示例
一、题目描述
考虑一个无向图 \(G=(V, E)\)，其中 \(V\) 是顶点集（共 \(n\) 个顶点），\(E\) 是边集（共 \(m\) 条边）。图 \(G\) 的密度定义为边的数量除以顶点的数量。给定图 \(G\)，最大密度子图问题 要求找到一个顶点子集 \(S \subseteq V\)，使得由 \(S\) 诱导出的子图（即包含所有两端点均在 \(S\) 中的边）的密度最大。
具体地，设诱导子图的边集为 \(E(S)\)，其密度定义为：
\[\rho(S) = \frac{|E(S)|}{|S|} \]
目标是最大化 \(\rho(S)\)。
这个问题是 NP-Hard 的。但有趣的是，它可以转化为一个线性规划问题，并且通过对偶性可以设计高效算法（如 Charikar 的贪心算法）。本题我们将聚焦于如何将其建模为线性规划，并解释其几何与组合意义。
二、建立线性规划模型
我们引入两类决策变量：
- 顶点变量 \(x_v \in \{0,1\}\)，表示顶点 \(v\) 是否被选入集合 \(S\)。
- 边变量 \(y_e \in \{0,1\}\)，表示边 \(e\) 是否被选入 \(E(S)\)。
约束条件：
- 如果一条边被选中（\(y_e=1\)），则它的两个端点都必须被选中：
\[ y_{uv} \le x_u, \quad y_{uv} \le x_v \quad \forall (u,v) \in E \]
- 变量取值限制：
\[ 0 \le x_v \le 1, \quad 0 \le y_e \le 1 \]
注意：这里我们先考虑线性松弛，允许变量在 \([0,1]\) 之间连续取值。
目标函数：最大化密度 \(\rho = \frac{\sum_{e \in E} y_e}{\sum_{v \in V} x_v}\)。
但这是一个分式线性函数，不是标准线性规划。我们需要进行转化。
三、转化为线性规划
设 \(t = \frac{1}{\sum_{v \in V} x_v} > 0\)，并令：
\[z_v = t x_v, \quad w_e = t y_e \]
则 \(z_v, w_e \ge 0\)，且 \(\sum_{v} z_v = 1\)。
将边约束 \(y_e \le x_v\) 两边乘以 \(t\)，得：
\[w_e \le z_v \]
目标函数变为：
\[\rho = \frac{\sum_{e} y_e}{\sum_{v} x_v} = \frac{\sum_{e} w_e / t}{\sum_{v} z_v / t} = \sum_{e} w_e \]
于是得到等价的线性规划（LP）：
\[\begin{aligned} \text{最大化} \quad & \sum_{e \in E} w_e \\ \text{满足} \quad & w_{uv} \le z_u, \quad w_{uv} \le z_v \quad \forall (u,v) \in E \\ & \sum_{v \in V} z_v = 1 \\ & z_v \ge 0, \quad w_e \ge 0 \end{aligned} \]
这是一个标准的线性规划，变量数为 \(n+m\)，约束数为 \(2m+1\)。
四、线性规划的几何理解
这个线性规划有很好的结构：
- 目标函数只与 \(w_e\) 有关，是边权之和。
- 每个 \(w_e\) 被两个端点变量 \(z_u, z_v\) 控制，不能超过它们中的较小值。
- 所有 \(z_v\) 构成一个概率单纯形（和为1的非负向量）。
直观上，我们需要将“单位质量”分配到顶点上（通过 \(z_v\)），然后每条边可以“承载”不超过其两端点质量的流量（通过 \(w_e\)），目标是最大化总流量。
五、求解思路
步骤1：对偶问题
写出上述线性规划的对偶，可以揭示更多结构。引入对偶变量：
- 对每个约束 \(w_{uv} \le z_u\)，引入 \(\alpha_{uv} \ge 0\)。
- 对每个约束 \(w_{uv} \le z_v\)，引入 \(\beta_{uv} \ge 0\)。
- 对约束 \(\sum_v z_v = 1\)，引入对偶变量 \(\lambda\)（无符号限制）。
得到对偶线性规划：
\[\begin{aligned} \text{最小化} \quad & \lambda \\ \text{满足} \quad & \sum_{u: (u,v) \in E} (\alpha_{uv} + \beta_{uv}) \le \lambda \quad \forall v \in V \\ & \alpha_{uv} + \beta_{uv} \ge 1 \quad \forall (u,v) \in E \\ & \alpha_{uv}, \beta_{uv} \ge 0 \end{aligned} \]
这个对偶问题有一个直观解释：每条边需要至少分配 1 个单位“压力”到它的两个端点（通过 \(\alpha, \beta\)），而 \(\lambda\) 是顶点的最大总压力。我们要最小化这个最大压力。
步骤2：最优解的结构
可以证明，原线性规划的最优解中，存在一个最优解满足：
- 所有 \(z_v\) 只取 0 或某个常数值。
- 所有 \(w_e = \min(z_u, z_v)\)。
由此可推导出：最大密度子图可以通过贪心算法得到：
- 将所有顶点按度数排序。
- 依次移除当前度数最小的顶点，并重新计算剩余子图的密度。
- 取所有子图中密度最大的一个。
这个贪心算法的正确性依赖于线性规划的对偶互补松弛条件，这里不深入证明。
六、示例计算
考虑一个小图：\(V=\{1,2,3\}\)，边 \(E=\{(1,2), (2,3), (1,3)\}\)（三角形）。
线性规划模型：
\[\begin{aligned} \max \quad & w_{12} + w_{13} + w_{23} \\ \text{s.t.} \quad & w_{12} \le z_1, \quad w_{12} \le z_2 \\ & w_{13} \le z_1, \quad w_{13} \le z_3 \\ & w_{23} \le z_2, \quad w_{23} \le z_3 \\ & z_1 + z_2 + z_3 = 1 \\ & z_i, w_{ij} \ge 0 \end{aligned} \]
求解：
由对称性，猜测最优解是 \(z_1 = z_2 = z_3 = 1/3\)。
则每个 \(w_{ij} \le 1/3\)，取最大值 \(w_{ij} = 1/3\)。
目标函数值 = \(1/3 + 1/3 + 1/3 = 1\)。
验证密度：子图为整个三角形，边数=3，顶点数=3，密度=1。与线性规划最优值一致。
七、总结
- 最大密度子图问题可以转化为一个线性规划。
- 通过变量替换，将分式目标化为线性目标。
- 对偶问题给出了最小化顶点最大压力的解释。
- 最优解对应一个稠密子图，贪心算法可高效求解。
- 这个线性规划模型是理解图稠密性子结构的基础，可扩展至带权图或有向图。
这个例子展示了如何用线性规划建模组合优化问题，并通过对其结构的分析得到有效算法。