Kruskal正确性定理

概述

Kruskal正确性定理（Kruskal Correctness Theorem）：对于连通无向加权图 $G=(V,E)$，Kruskal 算法（将边按权重非递减排序后，依次选择不成环的最小权重边）生成的生成树是最小生成树（MST）。该定理通过切割性质（cut property）证明每条被选边都是某切割的轻边。

定理陈述

形式化陈述

定理（CLRS Theorem 23.4）：设 $G=(V,E)$ 是一个连通无向加权图，$w:E\to \mathbb{R}$ 是边权函数。Kruskal 算法输出的生成树 $T$ 是 $G$ 的一棵最小生成树。

算法回顾： Kruskal 算法将 $E$ 中的边按权重非递减排序为 $⟨e_1,e_2,\dots ,e_{|E|}⟩$，维护森林 $F$（初始为每个顶点自成一棵树）。依次考察每条边 $e_i=(u,v)$：若 $u$ 和 $v$ 在 $F$ 的不同连通分量中（即加入 $e_i$ 不形成环），则将 $e_i$ 加入 $F$ 并合并两个分量。重复直到 $F$ 成为一棵树。

证明概要

证明思路

证明的关键引理是：Kruskal 算法选择的每条边都是某切割的轻边，因此由 安全边定理 保证其安全性。

关键引理：设 Kruskal 算法正在考察边 $e=(u,v)$，此时 $u$ 和 $v$ 属于森林 $F$ 的不同连通分量 $C_u$ 和 $C_v$。则 $e$ 是横跨切割 $(C_u,V-C_u)$ 的轻边。

引理证明：

考察切割 $(C_u,V-C_u)$。由于 $F$ 中 $C_u$ 是一个连通分量，$F$ 中没有边横跨该切割（否则 $C_u$ 可以通过该边连接到更大的分量）。因此切割 $(C_u,V-C_u)$ 尊重 $F$ 中已选的边集 $A$。

由于 Kruskal 算法按权重非递减顺序考察边，且 $e$ 是当前被考察的第一条横跨切割 $(C_u,V-C_u)$ 的边（所有权重更小的边要么已被选入 $F$，要么被拒绝因为它们连接同一分量内的顶点），所以 $e$ 是横跨该切割的最小权重边，即 $e$ 是该切割的轻边。

定理证明（归纳法）：

• 基例：初始时 $A=\varnothing$，空集显然包含在某棵 MST 中
• 归纳步：假设在考察边 $e$ 之前，$A$ 包含在某棵 MST $T^{\ast }$ 中
• 若 $e$ 连接同一分量内的两个顶点（加入 $e$ 会形成环），则跳过 $e$，$A$ 不变，仍包含在 $T^{\ast }$ 中
• 若 $e$ 连接不同分量 $C_u$ 和 $C_v$，由关键引理，$e$ 是横跨切割 $(C_u,V-C_u)$ 的轻边。由 安全边定理，$e$ 对 $A$ 安全，即 $A\cup \{e\}$ 包含在某棵 MST 中
• 终止：当算法结束时，$|A|=|V|-1$ 且 $A$ 连通所有顶点，$A$ 是一棵生成树。由于 $A$ 始终包含在某棵 MST 中，$A$ 本身就是一棵 MST

证毕。

关键推论

• 贪心选择性质：Kruskal 算法体现了贪心选择性质——全局最优解可以通过局部最优选择（每次选最小权重的不成环边）逐步构建
• 与并查集的配合：Kruskal 算法使用并查集（Union-Find）高效判断两个顶点是否属于同一连通分量，配合按秩合并与路径压缩（按秩合并与路径压缩定理），单次操作接近 $O(1)$
• 时间复杂度：排序 $O(E\lg E)$，并查集操作 $O(E\cdot \alpha (V))$（$\alpha$ 为反 Ackermann 函数），总时间 $O(E\lg E)=O(E\lg V)$
• 与 Prim 的对比：Kruskal 适合稀疏图（$|E|$ 较小），Prim 适合稠密图；Kruskal 基于边排序，Prim 基于顶点扩展
• 唯一性：若所有边权互不相同，则 MST 唯一，Kruskal 算法必然输出这棵唯一的 MST

应用场景

• 算法导论 Ch21：Kruskal 正确性定理与 Prim 正确性定理共同构成 MST 算法的理论基础，两者都是 GENERIC-MST 框架的实例化
• 聚类分析：单链接聚类（single-linkage clustering）通过运行 Kruskal 算法并在连通分量数等于聚类数时停止，实现层次聚类
• 网络设计：在道路规划、电路布线等场景中，Kruskal 算法找到最小成本的连通方案，特别适合边数远小于顶点数平方的稀疏网络
• 障碍物避让的最小连接：在存在障碍物的平面上，Kruskal 算法的变体（配合可见性图）可求解最小 Steiner 树问题的近似解

参见

• 安全边定理 — Kruskal 和 Prim 正确性的统一理论基础
• Prim正确性定理 — 另一种 MST 算法的正确性证明
• 按秩合并与路径压缩定理 — Kruskal 算法中并查集操作的高效性保证
• 贪心算法 — 贪心算法的一般理论
• 图论 — 图论基础概念