无向图的最小度生成树（Minimum Degree Spanning Tree, MDST）问题及其精确解法（Branch and Bound）
问题描述
给定一个无向连通图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集，每条边可能有非负权重（也可能无权，此时权重视为 1）。最小度生成树（MDST）问题要求找到图 \(G\) 的一棵生成树，使得这棵树中所有顶点的最大度数（即树中与顶点相连的边的数量）最小。
换句话说，我们希望找到一棵生成树 \(T\)，使得：
\[\max_{v \in V} \deg_T(v) \]
尽可能小，其中 \(\deg_T(v)\) 是顶点 \(v\) 在树 \(T\) 中的度数。
这个问题是 NP 难的，因此通常采用精确算法（如分支限界）或近似算法来求解。这里我们重点讲解基于分支限界（Branch and Bound, B&B）的精确解法。
问题难点与直观理解
- 生成树约束：解必须是生成树，即连接所有顶点且无环。
- 最小化最大度数：目标不是总权重最小，而是让树中“最繁忙”的顶点尽可能不繁忙。
- 组合爆炸：生成树的数量随顶点数指数增长，穷举不可行。
直观思路：如果我们能猜测一个目标最大度数 \(D\)，问题转化为：是否存在一棵生成树，其中每个顶点的度数都不超过 \(D\)？这是一个判定问题，可以通过约束生成树搜索来求解。分支限界法会系统性地搜索所有可能的生成树，但利用界限剪枝来减少搜索量。
分支限界算法框架
分支限界法包含三个核心部分：
- 分支（Branching）：将问题分解为子问题（例如，决定是否选择某条边）。
- 界限（Bounding）：计算当前部分解的可行解质量下界（对于最小化问题，下界越紧越好）。
- 剪枝（Pruning）：如果当前部分解的下界已经不小于已知最优解的值，则放弃该分支。
步骤 1：问题建模与下界计算
1.1 下界（Lower Bound）
对于 MDST 问题，一个简单的下界是：
\[\text{下界} = \left\lceil \frac{2(n-1)}{n} \right\rceil \]
因为一棵 \(n\) 个顶点的树有 \(n-1\) 条边，总度数为 \(2(n-1)\)，平均度数为 \(\frac{2(n-1)}{n}\)。最大度数至少是平均度数的上取整。
更紧的下界可以通过图本身的属性获得，例如：
- 若图中有顶点 \(v\) 的原始度数（在原图中）很小，则它在生成树中的度数不可能超过其原始度数。
- 初始下界可设为上述计算值。
1.2 上界（初始可行解）
我们可以用贪心或启发式算法快速得到一个可行解，例如：
- 运行 Prim 或 Kruskal 算法得到一棵生成树，计算其最大度数作为初始上界 \(U\)。
步骤 2：分支策略（边选择）
我们采用基于边选择的分支策略：
- 每条边 \(e \in E\) 有三种状态：已选（IN）、已拒（OUT）、未定（FREE）。
- 从空集开始，逐步决定边的状态，构建生成树。
分支过程：
- 选择一个未定（FREE）的边 \(e\)。
- 创建两个子问题：
- 子问题 A：强制选择 \(e\)（状态设为 IN）。
- 子问题 B：强制拒绝 \(e\)（状态设为 OUT）。
步骤 3：可行性检查与度数约束
在分支过程中，我们需要维护：
- 度数约束：每个顶点 \(v\) 的当前度数 \(\text{cur\_deg}[v]\)（基于已选边）不能超过当前目标度数 \(D\)（\(D\) 是搜索过程中尝试的上界）。
- 连通性检查：已选边不能形成环（树的无环性质）。
- 连通分量追踪：使用并查集（Union-Find）维护已选边构成的连通分量。
剪枝条件（当前分支不可能产生可行解时）：
- 某顶点 \(v\) 的当前度数 \(\text{cur\_deg}[v]\) 已等于 \(D\)，但还有未定边与其相连，且这些边必须被选择才能连通图？——需要更精细的检查。
- 已选边形成了环。
- 即使选择所有未定边，也无法使图连通（即剩下的边不足以连接所有连通分量）。
步骤 4：界限计算（关键优化）
对于当前分支，我们需要计算一个下界，表示从该分支出发所能达到的最小最大度数。如果这个下界 ≥ 当前最优解值 \(U\)，则剪枝。
下界计算的一种方法：
- 设当前已选边集合为 \(S\)，未定边集合为 \(F\)。
- 对于每个顶点 \(v\)，计算：
\[ \text{required\_deg}[v] = \text{cur\_deg}[v] + \min(\text{free\_edges}[v], \text{需要额外连接数}) \]
其中 \(\text{free\_edges}[v]\) 是与 \(v\) 相连的未定边数。
- 但更实用的方法是利用连通分量的度数需求：
每个连通分量需要至少一条边连接到其他分量（除非已是整个生成树）。这会导致某些顶点的度数必然增加。
一种有效的界限是：
\[\text{下界} = \max_{v \in V} \left( \text{cur\_deg}[v] + \max(0, \text{cc\_need}[v]) \right) \]
其中 \(\text{cc\_need}[v]\) 是顶点 \(v\) 所在连通分量还需要的最小额外连接数。
步骤 5：搜索策略与整体流程
我们使用深度优先搜索（DFS）进行分支限界，并配合一个全局上界 \(U\)（当前找到的最小最大度数）。
算法流程：
-
初始化 \(U\) 为启发式算法得到的值。
-
调用分支限界搜索函数
search(S, F, cur\_max\_deg)：- 输入：已选边集 \(S\)，未定边集 \(F\)，当前部分解的最大度数 \(cur\_max\_deg\)。
- 步骤：
a. 如果 \(cur\_max\_deg \geq U\)，剪枝返回。
b. 如果 \(S\) 已形成生成树（即 \(|S| = n-1\) 且图连通），更新 \(U = \min(U, cur\_max\_deg)\)，返回。
c. 如果 \(F\) 为空或不可能形成生成树，返回。
d. 选择一条未定边 \(e\)。
e. 分支 1：尝试选择 \(e\)。- 检查加入 \(e\) 是否形成环，或使某顶点度数超过 \(U-1\)（因为我们希望找到比 \(U\) 更好的解）。
- 如果可行，递归调用
search(S ∪ {e}, F \ {e}, max(cur\_max\_deg, new\_deg))。
f. 分支 2：尝试拒绝 \(e\)。 - 检查拒绝后是否还能形成生成树（即剩余边足够连通）。
- 如果可行，递归调用
search(S, F \ {e}, cur\_max\_deg)。
-
搜索结束后，\(U\) 即为最小最大度数，对应的生成树为 MDST。
步骤 6：例子说明
考虑一个简单无向图（无权）：
顶点：1, 2, 3, 4
边：(1,2), (1,3), (1,4), (2,3), (3,4)
我们手工演示分支限界思路：
- 初始上界：用 Prim 算法生成树（如选边 (1,2), (1,3), (1,4)），最大度数 = 3（顶点 1）。所以 \(U = 3\)。
- 下界：平均度数 = \(2(4-1)/4 = 1.5\)，上取整为 2。所以初始下界 = 2。
- 搜索：
- 尝试目标 \(D = 2\)（即希望找到最大度数 ≤ 2 的生成树）。
- 分支限界搜索：
- 选择边 (1,2) IN，则顶点 1 和 2 度数各为 1。
- 后续选择不能使顶点 1 度数超过 2。
- 发现可以构造生成树：选 (1,2), (2,3), (3,4)，度数分布为 [2,2,2,1]，最大度数 = 2。
- 更新 \(U = 2\)。
- 继续搜索可能更优的解（最大度数 = 1？不可能，因为树需要至少两个叶子顶点度数为 1，但最大度数至少为 2 才能连通 4 个顶点）。
- 结果：最小最大度数 = 2，对应生成树如上。
步骤 7：复杂度与优化
- 最坏情况：分支限界仍需指数时间，因为问题是 NP 难的。
- 优化技巧：
- 边选择顺序：优先选择与高度数顶点相连的边，或可能增加最大度数的边，以便早期剪枝。
- 对称性破缺：避免搜索等价解。
- 启发式下界：使用更复杂的图论界限（如基于最小割的度数约束）。
- 提前连通性检查：如果未定边不足以连接所有连通分量，则剪枝。
总结
MDST 是一个经典的 NP 难组合优化问题。分支限界法通过系统地探索边选择的空间，并利用度数下界和可行性检查剪枝，能在合理时间内求解中小规模图。对于大规模图，则需要使用近似算法（如基于最小生成树度数约减的启发式方法）。