安全边定理

概述

安全边定理（Cut Property / Safe Edge Theorem）：设 $A$ 是某棵最小生成树（MST）的边的子集，$(u,v)$ 是横跨割 $(A,V-A)$ 的一条轻边，则 $(u,v)$ 对 $A$ 是安全的。这是 Kruskal 和 Prim 算法正确性的统一理论基础。

定理陈述

形式化陈述

定理（CLRS Theorem 23.1）：设 $G=(V,E)$ 是一个连通无向加权图，$A\subseteq E$ 是包含在某棵 MST 中的边的子集。设 $(S,V-S)$ 是 $G$ 中尊重 $A$ 的一个割（即 $A$ 中没有边横跨该割），$(u,v)$ 是横跨割 $(S,V-S)$ 的一条轻边（即 $w(u,v)=\min \{w(x,y)\mid x\in S,y\in V-S,(x,y)\in E\}$）。则边 $(u,v)$ 对 $A$ 是安全的，即 $A\cup \{(u,v)\}$ 也包含在某棵 MST 中。

术语说明：

• 割 $(S,V-S)$：将顶点集 $V$ 划分为两个不相交子集 $S$ 和 $V-S$
• 尊重 $A$ 的割：$A$ 中没有任何边横跨该割
• 轻边：横跨割的所有边中权重最小的边

证明概要

证明思路

证明的核心是”交换论证”（exchange argument）：假设轻边不在某棵 MST 中，通过替换操作构造包含该轻边的新 MST。

步骤 1：选择包含 $A$ 的 MST

设 $T$ 是一棵包含 $A$ 的最小生成树（由假设，这样的 $T$ 存在）。

步骤 2：分情况讨论

情况 1：$(u,v)\in T$。则 $A\cup \{(u,v)\}\subseteq T$，$(u,v)$ 对 $A$ 显然安全。无需进一步论证。

情况 2：$(u,v)\notin T$。将 $(u,v)$ 添加到 $T$ 中，得到 $T^{\prime }=T\cup \{(u,v)\}$。

步骤 3：分析环结构

$T$ 是树（$|V|-1$ 条边），添加 $(u,v)$ 后 $T^{\prime }$ 含有唯一一个简单回路 $C$。由于 $u\in S$，$v\in V-S$，回路 $C$ 必须从 $S$ “穿越”到 $V-S$ 再”穿越”回来。因此 $C$ 中至少存在另一条横跨割 $(S,V-S)$ 的边，设为 $(x,y)$，其中 $x\in S$，$y\in V-S$。

步骤 4：证明 $(x,y)\notin A$

由于割 $(S,V-S)$ 尊重 $A$（$A$ 中没有边横跨该割），而 $(x,y)$ 横跨该割，所以 $(x,y)\notin A$。

步骤 5：交换边并验证

令 $T^{\prime \prime }=T^{\prime }-\{(x,y)\}=(T-\{(x,y)\})\cup \{(u,v)\}$。

• $T^{\prime \prime }$ 是生成树：删除 $(x,y)$ 打破了回路 $C$，$T^{\prime \prime }$ 有 $|V|-1$ 条边且连通
• $T^{\prime \prime }$ 包含 $A\cup \{(u,v)\}$：$A\subseteq T$，$(x,y)\notin A$，所以 $A\subseteq T^{\prime \prime }$
• $T^{\prime \prime }$ 是最小生成树：$w(T^{\prime \prime })=w(T)-w(x,y)+w(u,v)\le w(T)$（因为 $(u,v)$ 是轻边，$w(u,v)\le w(x,y)$）。但 $T$ 已经是 MST，所以 $w(T^{\prime \prime })=w(T)$

因此 $(u,v)$ 对 $A$ 是安全的。

学术参考：该证明与知识库中 11.5 节 Prim 算法正确性证明的交换论证思路一致，详见 11.5 最小生成树。

关键推论

• Kruskal 算法的正确性：Kruskal 算法维护的边集 $A$ 始终是某 MST 的子集。每次选择的最小权不成环边恰好是横跨某个尊重 $A$ 的割的轻边，因此对 $A$ 安全
• Prim 算法的正确性：Prim 算法维护的割 $(S,V-S)$（$S$ 为已选顶点集）天然尊重 $A$，每次选择的最小关联边就是轻边，因此安全
• 唯一性判定：若每条横跨割的轻边都是唯一的（即所有边权互不相同），则 MST 唯一

应用场景

• 算法导论 Ch21：安全边定理是 GENERIC-MST 框架的理论基础，Kruskal 和 Prim 算法都是该框架的实例化
• 网络设计：在设计通信网络时，安全边定理保证贪心策略能找到最小成本的连通方案
• 聚类分析：单链接聚类（single-linkage clustering）利用最小生成树的性质，其理论基础也来自安全边定理

参见

• 贪心算法 — 贪心选择性质与最优子结构
• 图论 — 图论基础概念
• 加权图 — 带权图的定义与表示
• 11.5 最小生成树 — Prim/Kruskal 算法的详细说明与正确性证明