Prim正确性定理

概述

Prim正确性定理（Prim Correctness Theorem）：对于连通无向加权图 $G=(V,E)$，Prim 算法生成的生成树是最小生成树（MST）。该定理通过将 Prim 算法的每一步选择与安全边定理联系起来，证明贪心策略的全局最优性。

定理陈述

形式化陈述

定理（CLRS Theorem 23.5）：设 $G=(V,E)$ 是一个连通无向加权图，$w:E\to \mathbb{R}$ 是边权函数。Prim 算法（以任意起始顶点 $r\in V$ 开始）输出的生成树 $T$ 是 $G$ 的一棵最小生成树。

算法回顾： Prim 算法维护一个顶点集合 $S\subseteq V$（初始为 $\{r\}$）和边集 $A$（初始为空）。在每一步，算法选择连接 $S$ 与 $V-S$ 的最小权重边 $(u,v)$（其中 $u\in S$，$v\in V-S$），将 $v$ 加入 $S$，将 $(u,v)$ 加入 $A$。重复直到 $S=V$。

证明概要

证明思路

证明的核心是验证 Prim 算法的每一步选择都满足 安全边定理 的条件，从而保证算法始终沿着正确的方向构建 MST。

步骤 1：建立 Prim 算法与安全边定理的联系

在 Prim 算法的任意执行时刻，设 $S$ 为已选顶点集，$A$ 为已选边集。考虑割 $(S,V-S)$：

• $A$ 中的所有边都连接 $S$ 内部的顶点（因为 Prim 每次只添加从 $S$ 到 $V-S$ 的边），因此 $A$ 中没有边横跨割 $(S,V-S)$
• 这意味着割 $(S,V-S)$ 尊重 $A$

步骤 2：验证轻边条件

Prim 算法在每一步选择的是连接 $S$ 与 $V-S$ 的最小权重边 $(u,v)$，即： $w(u,v)=\min \{w(x,y)\mid x\in S,y\in V-S,(x,y)\in E\}$

因此 $(u,v)$ 恰好是横跨割 $(S,V-S)$ 的轻边。

步骤 3：应用安全边定理

由 安全边定理，由于割 $(S,V-S)$ 尊重 $A$，且 $(u,v)$ 是该割的轻边，因此 $(u,v)$ 对 $A$ 是安全的，即 $A\cup \{(u,v)\}$ 仍包含在某棵 MST 中。

步骤 4：归纳论证

• 基例：初始时 $S=\{r\}$，$A=\varnothing$。空集显然包含在每棵 MST 中
• 归纳步：假设在算法的某一步，$A$ 包含在某棵 MST 中。由步骤 3，新选择的边 $(u,v)$ 对 $A$ 安全，因此 $A\cup \{(u,v)\}$ 也包含在某棵 MST 中
• 终止：当 $S=V$ 时，$|A|=|V|-1$ 且 $A$ 连通所有顶点，因此 $A$ 是一棵生成树。由于 $A$ 始终包含在某棵 MST 中，且 $A$ 本身就是生成树，所以 $A$ 就是一棵 MST

证毕。

关键推论

• Prim 算法的贪心最优性：Prim 算法是贪心算法在 MST 问题上的成功实例，其正确性不依赖于边的处理顺序（与 Kruskal 不同），而是依赖于”局部最优导致全局最优”的性质
• 与 Kruskal 的统一视角：Prim 和 Kruskal 都是 GENERIC-MST 框架的实例化，区别在于维护割的方式不同——Prim 维护以顶点集 $S$ 定义的割，Kruskal 维护以连通分量定义的割
• 起始顶点的无关性：Prim 算法的输出与起始顶点 $r$ 的选择无关（当所有边权互不相同时），因为无论从哪个顶点开始，安全边定理都保证每一步的正确性
• 唯一性问题：若存在权重相同的边，Prim 可能产生不同的 MST（取决于起始顶点和相同权重边的选择顺序），但所有输出的 MST 权重之和相同

应用场景

• 算法导论 Ch21：Prim 正确性定理是 GENERIC-MST 理论框架的核心组成部分，与 Kruskal 正确性定理并列
• 网络设计：在铺设光缆、设计管道网络等场景中，Prim 算法（配合二叉堆或斐波那契堆实现）能高效找到最小成本连通方案
• 稠密图的最优选择：当图为稠密图（$|E|\approx |V{|}^2$）时，Prim 算法使用斐波那契堆的时间复杂度为 $O(E+V\lg V)$，优于 Kruskal 的 $O(E\lg E)$
• 图像分割：在图像处理中，Prim 算法的变体用于基于图的最优分割

参见

• 安全边定理 — Prim 和 Kruskal 正确性的统一理论基础
• Kruskal正确性定理 — 另一种 MST 算法的正确性证明
• 贪心算法 — 贪心算法的一般理论
• 图论 — 图论基础概念