基于线性规划的图最小有向生成树（最小树形图）问题的Edmonds算法与对偶解释求解示例
一、问题描述
我们考虑一个有向图的最小有向生成树问题，也称为最小树形图问题。给定一个有向带权图 \(G=(V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是有向边集合，每条边 \(e \in E\) 有一个权重 \(w_e \geq 0\)。指定一个根顶点 \(r \in V\)。目标是从 \(E\) 中选出一个边集 \(T \subseteq E\)，使得：
- 在忽略边方向后，\(T\) 构成一棵以 \(r\) 为根的树；
- 除根 \(r\) 外，每个顶点 \(v \neq r\) 在 \(T\) 中恰好有一条入边（即从某个顶点指向 \(v\) 的边）；
- 边集 \(T\) 的总权重 \(\sum_{e \in T} w_e\) 最小。
这个问题在实际中有着广泛应用，例如网络广播协议设计、电力传输网络规划等。我们需要找出满足上述约束且总权重最小的边集。由于约束“每个非根顶点恰有一条入边”构成了一个拟阵（实际上是分支拟阵），该问题存在多项式时间算法，其中最著名的是Edmonds算法（又称Chu–Liu/Edmonds算法）。该算法可以自然地通过线性规划对偶理论来理解和解释。
二、线性规划建模与对偶问题
1. 整数规划模型
设决策变量 \(x_e \in \{0,1\}\) 表示边 \(e\) 是否被选中。最小树形图问题可建模为：
\[\begin{aligned} \min \quad & \sum_{e \in E} w_e x_e \\ \text{s.t.} \quad & \sum_{e \in \delta^-(v)} x_e = 1, \quad \forall v \in V \setminus \{r\} \\ & \sum_{e \in E(S)} x_e \leq |S| - 1, \quad \forall S \subseteq V \setminus \{r\}, S \neq \emptyset \\ & x_e \in \{0,1\}, \quad \forall e \in E \end{aligned} \]
其中：
- \(\delta^-(v)\) 表示指向顶点 \(v\) 的入边集合。
- \(E(S)\) 表示两个端点都在集合 \(S\) 中的边的集合（不考虑方向）。
第一个约束保证每个非根顶点恰有一条入边。第二个约束是子图无环约束（Subtour Elimination Constraints），它保证了选出的边集不会在非根顶点集合中形成有向环（因为如果有环，则环中每个顶点入度均为1，但整体不连通到根，违反了树结构）。事实上，这些约束保证了选出的边集构成一棵以 \(r\) 为根的有向树。
2. 线性规划松弛
将整数约束松弛为 \(x_e \geq 0\)，得到线性规划（LP）：
\[\begin{aligned} \min \quad & \sum_{e \in E} w_e x_e \\ \text{s.t.} \quad & \sum_{e \in \delta^-(v)} x_e = 1, \quad \forall v \in V \setminus \{r\} \quad (1)\\ & \sum_{e \in E(S)} x_e \leq |S| - 1, \quad \forall S \subseteq V \setminus \{r\}, S \neq \emptyset \quad (2)\\ & x_e \geq 0, \quad \forall e \in E \end{aligned} \]
由于约束数量是指数级的，直接求解不现实。Edmonds算法的思想可以视为原始-对偶方法，通过维护对偶可行解来逐步构造原始整数解。
3. 对偶问题
我们为每个约束引入对偶变量：
- 对每个非根顶点 \(v\)，约束 (1) 对应的对偶变量记为 \(p_v\)（无符号限制，因为是等式约束）。
- 对每个非空集合 \(S \subseteq V \setminus \{r\}\)，约束 (2) 对应的对偶变量记为 \(y_S \geq 0\)。
则对偶问题为：
\[\begin{aligned} \max \quad & \sum_{v \neq r} p_v - \sum_{S \neq \emptyset, S \subseteq V\setminus \{r\}} (|S|-1) y_S \\ \text{s.t.} \quad & p_{v} - \sum_{S: e \subseteq S} y_S \leq w_e, \quad \forall e=(u,v) \in E, v \neq r \\ & p_v \text{ 无限制}, \quad y_S \geq 0 \end{aligned} \]
其中，约束条件是针对每条边 \(e=(u,v)\)（指向 \(v\)），要求其对偶约束满足：\(p_v\) 减去所有包含 \(e\) 两端点的集合 \(S\) 对应的 \(y_S\) 之和不超过边权 \(w_e\)。
三、Edmonds算法（基于对偶思想的分步解释）
Edmonds算法是一个递归算法，其核心思想是通过调整对偶变量“收缩”环，并逐步构造最小树形图。下面我们结合线性规划对偶理论，将算法步骤拆解为对偶上升与原始构造两部分。
步骤1：初始化
- 设当前图 \(G_0 = G\)，权重 \(w_e^{(0)} = w_e\)，根为 \(r\)。
- 初始化对偶变量：所有 \(p_v = 0\)，所有 \(y_S = 0\)。此时对偶可行（因为 \(0 \leq w_e\)）。
步骤2：为每个非根顶点选择最小入边
对于当前图 \(G_k\)（可能是原图或收缩后的图），考虑每个非根顶点 \(v\)，选择其最小权重的入边：
\[\alpha(v) = \arg\min_{e \in \delta^-(v)} w_e^{(k)} \]
记最小权重为 \(m_v = \min_{e \in \delta^-(v)} w_e^{(k)}\)。
对偶调整：将对偶变量 \(p_v\) 增加 \(m_v\)，即令 \(p_v := p_v + m_v\)。为了保持对偶约束成立，同时将每条进入 \(v\) 的边 \(e=(u,v)\) 的权重更新为：
\[w_e^{(k)} := w_e^{(k)} - m_v \]
这一操作对应于将对偶目标值增加了 \(m_v\)，同时使得顶点 \(v\) 的所有入边权重减少 \(m_v\)，从而至少有一条进入 \(v\) 的边权重变为0（即最小入边权重归零）。更新后，对偶约束依然成立，因为对每条边 \(e=(u,v)\)，约束左端 \(p_v\) 增加了 \(m_v\)，右端 \(w_e\) 减少了 \(m_v\)，差值不变。
步骤3：检测有向环
在选出的最小入边集合 \(\{\alpha(v) : v \neq r\}\) 中，忽略根 \(r\)（根无入边），这些边构成一个子图。如果该子图不含有向环，则这些边恰好构成一棵以 \(r\) 为根的有向树（因为每个非根顶点恰有一条入边，且无环），这就是最优解，算法结束。
否则，设存在一个有向环 \(C\)（由顶点集 \(V_C\) 和边集 \(E_C\) 组成）。
步骤4：收缩环
- 收缩操作：将环 \(C\) 中的所有顶点收缩为一个超级顶点 \(c\)。原图中从环外顶点指向环内任意顶点的边，现在变为指向 \(c\)；原图中从环内顶点指向环外顶点的边，现在变为从 \(c\) 指向环外顶点。
- 权重更新：对于新图中进入超级顶点 \(c\) 的边 \(e=(u, c)\)（对应原图中边 \((u, v)\)，其中 \(v \in V_C\)），其权重更新为：
\[w_e' = w_e^{(k)} - w_{\alpha(v)}^{(k)} \]
其中 \(\alpha(v)\) 是环 \(C\) 中顶点 \(v\) 在步骤2中选择的最小入边（注意在环 \(C\) 中，每个顶点有一条入边来自环内上一个顶点，这些边权重已变为0）。由于 \(w_{\alpha(v)}^{(k)}=0\)，实际上 \(w_e' = w_e^{(k)}\)。这个调整的意义在于对偶变量 \(y_S\) 的引入：当我们收缩环 \(C\) 时，相当于设置对偶变量 \(y_{V_C} = \min_{v \in V_C} m_v\)（即环中最小入边调整量），并将环内所有顶点的 \(p_v\) 减少该值，从而使得环内某些边的对偶约束变紧。
3. 记录环信息：保存环 \(C\) 的结构，以便最后展开。
步骤5：递归求解
在收缩后的新图 \(G_{k+1}\) 上递归调用算法，寻找以 \(r\)（如果 \(r\) 不在环中）或以超级顶点 \(c\)（如果 \(r\) 在环中）为根的最小树形图。
步骤6：展开环，构造最终解
递归返回后，得到收缩后图的最小树形图 \(T'\)。
- 若 \(T'\) 中包含进入超级顶点 \(c\) 的边 \(e=(u, c)\)，则在原图中对应边 \((u, v)\) 加入最终解，并删除环 \(C\) 中顶点 \(v\) 原本在环内的入边（即环中指向 \(v\) 的边）。
- 若 \(T'\) 中不包含进入 \(c\) 的边，则说明根在环内，此时直接加入环 \(C\) 中除根外所有顶点的最小入边（这些边构成环）。
- 最后，加入递归解中其他不在环上的边。
四、算法正确性解释（对偶视角）
Edmonds算法实际上是在隐式地求解线性规划对偶问题：
- 步骤2中对 \(p_v\) 的增加对应于对偶上升，目的是增加对偶目标值。
- 收缩环对应于引入一个对偶变量 \(y_S\)（\(S\) 为环的顶点集），并调整相关边的权重，使得对偶约束继续保持。
- 算法保证在每一步，选出的0权边集合（最小入边）满足每个非根顶点入度恰好为1，并且通过收缩打破环，最终得到的无环解对应于原始可行解。
- 由于对偶问题始终可行，且最终构造的原始解与对偶解满足互补松弛条件，因此原始解是最优的。
互补松弛条件：
- 若边 \(e=(u,v)\) 被选中（\(x_e=1\)），则对应的对偶约束必须取等号：\(p_v - \sum_{S \ni u,v} y_S = w_e\)。
- 若对偶变量 \(y_S > 0\)，则对应集合 \(S\) 的原始不等式必须取等号：\(\sum_{e \in E(S)} x_e = |S|-1\)（即 \(S\) 导出子图恰好是一棵树）。
算法中，选中的边权重均为0（调整后），且对偶变量调整使得这些边的对偶约束恰好取等号；每次收缩环对应 \(y_S > 0\)，且环上选中的边数正好是 \(|S|-1\)，满足互补松弛。
五、算法复杂度与示例
- 时间复杂度：每轮递归至少减少一个顶点，每轮需要检查环（可用DFS），总复杂度 \(O(VE)\) 或使用更优实现 \(O(E + V \log V)\)。
- 示例：考虑一个简单有向图，顶点集 \(\{r, a, b, c\}\)，边及权重：\((r,a)=2, (r,b)=3, (a,b)=1, (b,a)=4, (b,c)=2, (c,a)=5\)，根为 \(r\)。
- 初始：选最小入边：\(a\): \((r,a)=2\)；\(b\): \((a,b)=1\)；\(c\): \((b,c)=2\)。无环，得到树形图边集 \(\{(r,a), (a,b), (b,c)\}\)，总权重5。
- 若权重调整后出现环（例如修改权重使 \((a,b)=0, (b,a)=0)\)，则收缩环 \(\{a,b\}\)，在新图上递归，最后展开得到最优树。
六、总结
通过线性规划对偶的角度，Edmonds算法可以视为一种原始-对偶算法：它通过逐步提升对偶变量，构造对偶可行解，同时在原始问题中构造整数解，并满足互补松弛条件。这种视角不仅解释了算法的正确性，也揭示了最小树形图问题的组合结构与线性规划对偶之间的深刻联系。该算法高效地解决了这一经典问题，并成为许多网络优化算法的基础。