Kruskal

Kruskal

性质: MST增量更新

在处理动态图或增量更新的最小生成树问题时，有一个非常深刻且有用的性质。这个性质是许多优化算法（例如题目 csp-s 2025 T2 道路修复 中可能用到的方法）的理论基础。

性质描述

假设我们有一个边集 $e_m$ 和另一个边集 $e_s$。我们想要计算 $e_m$ 和 $e_s$ 并集的最小生成树。该性质指出，我们可以先计算 $e_m$ 的最小生成树，然后用这个结果和 $e_s$ 一起计算最终的最小生成树。

用数学公式表达为：

$$\text{Cost}(\text{MST}(\text{e}_m \cup \text{e}_S)) = \text{Cost}(\text{MST}(\text{MST}(\text{e}_m) \cup \text{e}_S))$$

直观理解

这个性质的直观理解是：

任何不在 $e_m$ 的最小生成树里的边（我们称之为“无用边”），都因为它在 $e_m$ 内部的某个环路中是“最差”（最重）的边。

后来加入 $e_s$ 可能会提供 新 的环路，但这并不会改变那条“无用边”在它 原来 的环路中是“最差”的事实。

既然 $e_m$ 内部已经有了一条更优的路径（$MST(e_m)$ 中的路径）来连接那条“无用边”的两个端点，那么在求全局MST时，算法就永远不会选择那条“无用边”，因为它总能找到更优的替代方案。

---

证明

为了方便，我们定义几个术语：

• $E_m = \text{MST}(\text{e}_m)$：只使用 $e_m$ 算出的MST的边的集合。
• $E_m' = \text{e}_m \setminus E_m$：所有 $e_m$ 中没有被 $E_m$ 选中的边（“无用边”）。
• $G_1 = \text{e}_m \cup \text{e}_S = E_m \cup E_m' \cup \text{e}_S$： 包含所有边的完整图。
• $G_2 = E_m \cup \text{e}_S$： 只包含 $E_m$ 和新边集的“优化图”。
• $T_1 = \text{MST}(G_1)$：完整图的MST（这是我们真正想求的）。
• $T_2 = \text{MST}(G_2)$：“优化图”的MST。

我们要证明的是：$\text{Cost}(T_1) = \text{Cost}(T_2)$。

这个证明分为两个部分：

1. 证明 $\text{Cost}(T_1) \leqslant \text{Cost}(T_2)$

这部分很简单。

• $G_2$ 的边集（$E_m \cup \text{e}_S$）是 $G_1$ 边集（$E_m \cup E_m' \cup \text{e}_S$）的一个子集。
• $T_2$ 是 $G_2$ 的一个最小生成树。
• $T_2$ 本身也是 $G_1$ 的一个（不一定是最小的）生成树，因为它连接了所有节点。
• $T_1$ 是 $G_1$ 的最小生成树。根据定义，$T_1$ 的成本必须小于或等于 $G_1$ 中任何其他生成树的成本。
• 因此，$\text{Cost}(T_1) \leqslant \text{Cost}(T_2)$。

一句话: 集合大的小

另一种:

1. 因为集合$G_2 \subseteq G_1$,考虑幂集,得出$P(G_2) \subseteq P(G_1)$
2. $Cost(T_1)$本质是符合条件的幂集的最小值
3. 任何在$P(G_2)$的最小值都会出现在$P(G_1)$中
4. 显然，$\text{Cost}(T_1) \leqslant \text{Cost}(T_2)$。

2. 证明 $\text{Cost}(T_1) \geqslant \text{Cost}(T_2)$

这是证明的关键。我们将使用一个“交换论证”（Exchange Argument）。

我们从 $T_1$（完整图的MST）出发，一步一步地把它变成一个只使用 $G_2$ 中边的生成树，并且成本不会增加。

分情况讨论:

情况1: 只由$G_2$中的边组成

如果 $T_1$ 已经只包含 $G_2$ 中的边（即 $T_1$ 中没有任何来自 $E_m'$ 的边），那么 $T_1$ 本身就是 $G_2$ 的一个生成树。因为 $T_2$ 是 $G_2$ 的 最小 生成树，所以 $\text{Cost}(T_1) \geqslant \text{Cost}(T_2)$。结合第1部分，我们得到 $\text{Cost}(T_1) = \text{Cost}(T_2)$。

情况2: 先断开,然后重新连

1. 如果 $T_1$ 中包含了一条（或多条）来自 $E_m'$ 的边，我们任选一条这样的边 $e = (u, v)$。

   • $e$ 在 $e_m$ 中，但 $e \notin E_m$(e在原图中,但是不在原图MST中)。
   • 根据MST的环路性质：将 $e$ 添加到 $E_m$ 中，必然会形成一个环路 $C$。
   • 在这个环路 $C$ 中， $e$ 一定是权重最大（或之一）的边。环路 $C$ 上的所有其它边 $e_i$ 都满足 $\text{Cost}(e_i) \leqslant \text{Cost}(e)$，并且所有这些 $e_i$ 都在 $E_m$ 中。

2. 现在，我们回到 $T_1$。$T_1$ 是一个树，它包含了 $e$。

   • 如果我们从 $T_1$ 中移除 $e$， $T_1$ 会断裂成两个连通分量 $A$ 和 $B$（$u \in A, v \in B$）。
   • 但是，我们在上面知道 $e$ 所在的环路 $C$ 中，除了 $e$ 之外，还有一条 只由 $E_m$ 中的边构成的 路径 $P = C \setminus \{e\}$ 也能连接 $u$ 和 $v$。
   • 由于 $P$ 上的所有边都属于 $E_m$，而 $T_1$ 也是一个连接所有节点的生成树， $T_1$ 不可能包含了 $P$ 上的所有边（否则 $T_1$ 中会有一个环）。
   • 因此，$P$ 上必定存在至少一条边 $e_k$，它的两个端点分别位于 $A$ 和 $B$ 中。

3. 让我们来构造一个新的生成树 $T_1' = (T_1 \setminus \{e\}) \cup \{e_k\}$。

   • $T_1'$ 也是一个生成树（我们断开了 $e$，又用 $e_k$ 连上了）。
   • 我们来比较成本：$\text{Cost}(T_1') = \text{Cost}(T_1) - \text{Cost}(e) + \text{Cost}(e_k)$。
   • 因为 $e_k$ 在环路 $C$ 上，我们从第2步知道 $\text{Cost}(e_k) \le \text{Cost}(e)$。
   • 因此，$\text{Cost}(T_1') \le \text{Cost}(T_1)$。

4. 我们成功地将 $e$（一条 $E_m'$ 中的边）替换为了 $e_k$（一条 $E_m$ 中的边），并且总成本没有增加（反而可能降低了）。

   • 由于 $T_1$ 本来就是 最小生成树，它的成本不可能再降低了，所以必定有 $\text{Cost}(T_1') = \text{Cost}(T_1)$。
   • 这意味着 $T_1'$ 也是 $G_1$ 的一个最小生成树。

5. 我们可以对 $T_1$ 中所有来自 $E_m'$ 的边重复这个“交换”过程。最终，我们会得到一个新的最小生成树 $T_1^*$，它具有 $\text{Cost}(T_1^*) = \text{Cost}(T_1)$，并且 $T_1^*$ 只包含来自 $E_m$ 和 $e_s$ 的边。

   • 换句话说，$T_1^*$ 是一个完全由 $G_2$ 中的边构成的生成树。(这就变成了情况1)

6. 因为 $T_1^*$ 是 $G_2$ 的一个生成树，而 $T_2$ 是 $G_2$ 的最小生成树，所以 $\text{Cost}(T_2) \leqslant \text{Cost}(T_1^*)$。

7. 结合 $\text{Cost}(T_1^*) = \text{Cost}(T_1)$，我们得到 $\text{Cost}(T_2) \le \text{Cost}(T_1)$。

---

结论

• 在第1部分，我们证明了 $\text{Cost}(T_1) \leqslant \text{Cost}(T_2)$。
• 在第2部分，我们证明了 $\text{Cost}(T_1) \geqslant \text{Cost}(T_2)$。

唯一的可能是 $\text{Cost}(T_1) = \text{Cost}(T_2)$。

证明完毕。 这意味着我们可以安全地丢弃所有 $E_m'$ 中的边，只在 $E_m \cup \text{e}_S$ 上运行MST算法，这极大地降低了边的数量，从而优化了算法。