1. 概述
在图论中，有两个非常相关但又有所区别的概念：最小生成树（Minimum Spanning Tree, MST） 和 最小瓶颈生成树（Minimum Bottleneck Spanning Tree, MBST）。
本文将从定义入手，结合图示和示例代码，深入解析这两个概念的含义及其核心区别，帮助读者在实际应用中做出更准确的选择。
2. 最小生成树（MST）定义
给定一个无向、连通、带权图 $ G(V, E) $，其生成树 $ S(V_1, E_1) $ 是包含图中所有顶点 $ V $ 的无环子图，且边集 $ E_1 \subseteq E $。
最小生成树（MST）是指在所有可能的生成树中，总边权最小的那一个。
MST 在实际中有广泛的应用，例如：
- 图像分割
- 手写识别
- 实时人脸追踪
- 聚类分析
- 网络设计
2.1 示例
考虑如下图 $ G_1 $：
该图是一个包含 3 个顶点的完全图。其所有可能的生成树如下：
根据 Cayley 公式，顶点数为 $ N $ 的完全图的生成树总数为 $ N^{N-2} $，因此该图的生成树数量为 $ 3^{3-2} = 3 $。
这三个生成树的总边权分别为：3、4、5。其中，边权总和为 3 的生成树 $ S_1 $ 是 MST。
✅ 结论：$ S_1 $ 是图 $ G_1 $ 的最小生成树。
3. 最小瓶颈生成树（MBST）定义
在生成树中，瓶颈指的是权重最大的那条边。因此，最小瓶颈生成树（MBST） 是指所有生成树中，瓶颈边权重最小的那个。
换句话说，MBST 是使生成树中最“差”的那条边尽可能小的树结构。
3.1 示例
考虑如下图 $ G_2 $：
我们列出其所有生成树及其总边权和瓶颈边：
从图中可以看出，共有 4 个生成树：$ S_1, S_2, S_3, S_4 $。
其中：
- $ S_1 $ 的总边权为 6，是 MST。
- 瓶颈边为 $ (C, D) $，权重为 4。
- 所有包含 $ (C, D) $ 的生成树（$ S_1, S_2, S_4 $）都是 MBST。
✅ 结论：
- $ S_1 $ 是 MST，同时也是 MBST。
- $ S_2 $ 和 $ S_4 $ 是 MBST，但不是 MST。
- 因此，MBST 不一定是 MST，但MST 一定是 MBST。
3.2 MBST 的性质
- ✅ MST 一定是 MBST：因为 MST 的瓶颈边是全局最小的，所以它一定在 MBST 中。
- ❌ MBST 不一定是 MST：如上例中的 $ S_2 $ 和 $ S_4 $。
- ✅ MBST 的总权重 ≥ MST 的总权重：因为 MBST 可能包含非最优边。
4. MST 与 MBST 的核心区别
| 特性 | 最小生成树（MST） | 最小瓶颈生成树（MBST） |
|---|---|---|
| 定义 | 总边权最小的生成树 | 瓶颈边（最大边权）最小的生成树 |
| 是否唯一 | ✅ 是（总边权唯一） | ❌ 否（可能存在多个） |
| 是否包含 MST | ✅ 是 | ❌ 否 |
| 总权重 | ✅ 最小 | ❗ 可能更大 |
| 边数量 | ✅ 恰好 $ N - 1 $ 条 | ❗ 可能超过 $ N - 1 $ 条 |
⚠️ 注意：MBST 的目标是让“最差”的那条边尽可能好，而不是整体最优。
5. 总结
- MST 是所有生成树中总边权最小的，适用于全局最优场景。
- MBST 是所有生成树中瓶颈边最小的，适用于局部瓶颈敏感的场景。
- MST 是 MBST 的子集，但 MBST 不一定是 MST。
- 在实际应用中，应根据问题特性选择 MST 或 MBST。
例如：
- ✅ 网络布线：适合用 MST。
- ⚠️ 实时系统中延迟敏感路径：适合用 MBST。
掌握这两个概念的区别，有助于在图算法设计中做出更合理的决策。