最小度生成树（Minimum Degree Spanning Tree, MDST）的精确算法（Branch and Cut）
1. 问题描述
给定一个无向连通图 \(G = (V, E)\)，其中 \(|V| = n\)， \(|E| = m\)。图的度是图中顶点的最大度数。一个生成树（Spanning Tree）的度被定义为该树中所有顶点的最大度数。最小度生成树（Minimum Degree Spanning Tree, MDST）问题旨在找到一个生成树，使得这个生成树的度最小。我们将这个最小可能的度记为 \(d^*\)。
这个问题是NP难的。为了精确求解它，我们需要使用组合优化中的强大工具：分支切割法（Branch and Cut）。它是一种结合了分支定界（Branch and Bound）和割平面法（Cutting Planes）的精确算法框架。
2. 问题建模：整数线性规划（ILP）公式
我们引入二元决策变量：
- \(x_e \in \{0, 1\}, \forall e \in E\): 如果边 \(e\) 在生成树中，则为1，否则为0。
- \(y_v \in \{0, 1, 2, ..., n-1\}, \forall v \in V\): 表示顶点 \(v\) 在生成树中的度数。
- 我们需要一个辅助的目标变量 \(d\)，它表示生成树的最大度数。我们的目标是最小化 \(d\)。
基本约束：
- 边数约束：一棵生成树恰好有 \(n-1\) 条边。
\[ \sum_{e \in E} x_e = n-1 \]
- 连通性/无环约束：这组边必须构成一棵树（连通且无环）。一个等价的关键约束是：对于图的任意非空真子集 \(S \subset V, S \neq \emptyset\)，生成树中连接 \(S\) 和 \(V \setminus S\) 的边数至少为1（连通性），且恰好为1时该约束与边数约束结合可保证无环。更严格的“子环消除约束”通常写作：
\[ \sum_{e \in E(S)} x_e \le |S| - 1, \quad \forall S \subset V, 2 \le |S| \le n-1 \]
其中 \(E(S)\) 是两端点都在 \(S\) 内的边集。这个约束防止了在顶点子集 \(S\) 内形成环。
3. 度数链接约束：对于每个顶点 \(v\)，其度数 \(y_v\) 等于与它相连的、被选中的边的数量。
\[ y_v = \sum_{e \in \delta(v)} x_e, \quad \forall v \in V \]
其中 \(\delta(v)\) 表示与顶点 \(v\) 关联的边集。
4. 最大度约束：目标变量 \(d\) 必须不小于任何顶点的度数。
\[ y_v \le d, \quad \forall v \in V \]
- 变量类型：
\[ x_e \in \{0, 1\}, \quad y_v \in \mathbb{Z}^+_0, \quad d \in \mathbb{Z}^+_0 \]
目标函数：
\[\text{Minimize } d \]
3. 分支切割法（Branch and Cut）框架
直接求解这个ILP非常困难，因为约束(2)的数量是指数级的。分支切割法的核心思想是逐步添加必要的约束。
- 初始松弛问题：我们开始时忽略所有指数级的子环消除约束(2)，只包含约束(1), (3), (4)和变量的连续性松弛（即 \(x_e \in [0, 1]\), \(y_v \ge 0\), \(d \ge 0\)）。这样我们得到一个线性规划（LP）松弛，它可以在多项式时间内求解，但它的解通常不是合法的生成树（可能包含环）。
- 割平面（Cutting Planes）：在求解LP松弛后，我们检查其解 \(x^*\)。如果 \(x^*\) 违反了一些子环消除约束（即存在某个顶点集 \(S\)，使得 \(\sum_{e \in E(S)} x^*_e > |S| - 1\)），我们就将这个被违反的约束作为一个割平面添加到当前的LP模型中。这个割平面“切掉”了当前的分数解，但不会切掉任何合法的整数解（生成树）。然后，我们重新求解这个增强了约束的LP。
- 分离问题（Separation Problem）：关键是如何高效地找到被违反的子环消除约束。这被称为分离问题。对于子环消除约束，我们可以将 \(x^*_e\) 视为边 \(e\) 的容量，然后对于图中的每一对顶点 \((u, v)\)，计算最大流/最小割。如果从 \(u\) 到 \(v\) 的最小割值小于1，那么最小割定义的集合 \(S\)（包含 \(u\) 但不包含 \(v\) 的顶点集）就违反了约束 \(\sum_{e \in E(S)} x^*_e \ge 1\)（这是连通性约束的一种形式，与子环消除约束是等价的，在生成树背景下可以互相推导）。更高效的方法是使用专门的最小割算法来枚举所有“x-值大于1”的连通分量，并检查每个这样的分量是否违反了约束。在实践中，这可以在多项式时间内完成。
- 分支定界（Branch and Bound）：当我们无法再找到有效的割平面，且当前LP松弛的解 \(x^*\) 仍然不是全整数（即存在 \(x_e \notin \{0,1\}\)）时，我们进入分支阶段。我们选择一个分数变量（比如 \(x_{uv}\) 的值是0.6），然后创建两个子问题：
- 子问题A：强制 \(x_{uv} = 0\)。
- 子问题B：强制 \(x_{uv} = 1\)。
这就形成了一个搜索树。对于每个子问题，我们再次求解其LP松弛（可能添加新的割平面），并递归地进行这个过程。
- 定界与剪枝：
- 如果某个节点的LP松弛的解是整数且满足所有约束（即构成了一棵合法的生成树），我们就得到了一个可行解，其目标值 \(d\) 是一个上界（Upper Bound, UB）。
- 当前节点的LP松弛的最优目标值 \(d_{LP}\) 是下界（Lower Bound, LB）。如果 \(d_{LP} \ge\) 当前全局最佳上界，那么我们可以剪枝这个节点，因为它的任何子问题都不会给出更好的解。
- 迭代：算法不断重复“求解LP -> 寻找割平面 -> 必要时分支”的过程，直到搜索树被完全探索。最后得到的最佳可行解就是MDST，其对应的 \(d\) 就是 \(d^*\)。
4. 算法步骤详解
步骤1: 初始化
创建根节点，其初始LP松弛问题包含约束(1), (3), (4)，变量连续性松弛。设置全局上界 \(UB = +\infty\)，全局最优解为空。
步骤2: 处理活动节点
从活动节点列表中选取一个节点（通常使用最佳下界优先策略）。
步骤3: 求解节点LP
使用线性规划求解器（如单纯形法）求解当前节点的LP松弛。如果问题不可行，则剪枝该节点。
步骤4: 割平面生成（切割阶段）
- 设当前LP解为 \((x^*, y^*, d^*)\)。
- 分离子环消除约束：将 \(x^*\) 作为边权，在图上运行算法，寻找满足 \(\sum_{e \in E(S)} x^*_e > |S| - 1\) 的顶点子集 \(S\)。
- 如果找到这样的 \(S\)，将对应的割平面 \(\sum_{e \in E(S)} x_e \le |S| - 1\) 添加到当前节点的LP中，返回步骤3。
- 如果找不到违反的约束，进入下一步。
步骤5: 定界与可行性检查
- 当前节点的下界 \(LB = d^*_{LP}\)。
- 如果 \(LB \ge UB\)，剪枝该节点，返回步骤2处理下一个节点。
- 如果 \(x^*\) 是全整数的（即 \(x^*_e \in \{0,1\}\)），那么它对应一棵生成树。计算该树的实际最大度数 \(d_{cand}\)。
- 如果 \(d_{cand} < UB\)，则更新 \(UB = d_{cand}\)，并记录该生成树为当前最优解。
- 剪枝该节点（因为它已经给出了整数解）。
- 否则（\(x^*\) 包含分数值），进入分支步骤。
步骤6: 分支
选择一个分数变量 \(x_{uv}\)（其值在0和1之间）。创建两个新的子节点：
- 左子节点：添加约束 \(x_{uv} = 0\)。
- 右子节点：添加约束 \(x_{uv} = 1\)。
将这两个新节点加入活动节点列表。
步骤7: 循环与终止
重复步骤2-6，直到活动节点列表为空。此时，全局上界 \(UB\) 对应的解就是最优的MDST，\(d^* = UB\)。
5. 复杂度与总结
- 分支切割法是解决NP难组合优化问题的精确算法框架。它的效率高度依赖于：
- 初始LP松弛的紧致性。
- 割平面的有效性（能否快速提升下界）。
- 分支策略的好坏。
- 对于MDST问题，由于子环消除约束的分离问题可以在多项式时间内解决，分支切割法在实践中对于中等规模的图（几十到上百个顶点）可能是可行的。
- 然而，在最坏情况下，搜索树可能非常大，导致算法只能处理小规模实例。对于大规模图，通常需要使用启发式或近似算法（如之前讲过的近似算法）。
这个算法展示了如何将图论中的一个困难组合问题，通过精妙的建模（ILP）和强大的通用求解框架（分支切割）联系起来，从而在理论上和实用上寻求精确解。