1. 概述
在本篇文章中，我们将深入探讨最小生成树（MST）中的 Cut Property（切割性质）。这个性质是构造最小生成树的核心理论之一，也是 Kruskal 和 Prim 等经典算法的基础。
我们会从图论中的“Cut”概念讲起，然后介绍 Cut Property 的定义、示例和证明，最后说明它在最小生成树算法中的实际应用。
2. Cut 的定义
在图论中，Cut（切割）是指将图的顶点集划分为两个不相交子集的操作。这个划分会将图分成两个部分，而连接这两个部分的边构成一个集合，称为Cut Set（切割边集）。
相关术语
- Cut Set（切割边集）：跨越两个顶点子集的所有边的集合。
- Cut Vertex（割点）：如果移除该顶点会使图不再连通。
- Cut Edge（割边）：如果移除该边会使图不再连通。
这些概念在图的连通性分析中非常重要。
3. Cut 的示例
我们来看一个具体的图例，帮助理解 Cut、Cut Set、Cut Vertex 和 Cut Edge。
示例图结构
图 G(V, E) 包含 7 个顶点 V = {V1, V2, V3, V4, V5, V6, V7} 和 9 条边 E = {E1, E2, E3, E4, E5, E6, E7, E8, E9}。
我们定义一个 Cut C(S₁, S₂)，将图划分为两个子集：
- S₁ = {V1, V2, V3}
- S₂ = {V4, V5, V6, V7}
此时，Cut Set 包括所有连接 S₁ 和 S₂ 的边，比如 E4。
Cut Vertex 示例
- V3 和 V4 是 Cut Vertex，因为移除它们中的任何一个都会导致图断开。
- 移除 V3 后，图被分成两部分：{V1, V2} 和 {V4, V5, V6, V7}。
- 移除 V4 后，图也被分成两部分：{V1, V2, V3} 和 {V5, V6, V7}。
Cut Edge 示例
- E4 是 Cut Edge，因为它连接了两个子图，移除它后图不再连通。
4. Cut 的变体
Cut 有两个常见变体：
| 类型 | 含义 |
|---|---|
| 最小割（Min-Cut） | 割边总权重最小，常用于网络流问题 |
| 最大割（Max-Cut） | 割边总权重最大，用于图的划分和组合优化 |
示例分析
考虑一个加权图 G₁(V₁, E₁)，我们定义了 4 个 Cut：
- CUT 1：E1 + E3 + E10 = 8
- CUT 2：E2 + E4 + E6 = 10 ✅ 最大割
- CUT 3：E5 + E7 = 6 ✅ 最小割
- CUT 4：E3 + E4 = 7
5. Cut Property 在最小生成树中的应用
5.1. Cut Property 的陈述
在构造最小生成树时，如果某个 Cut 的 Cut Set 中有一条边的权重最小，那么这条边必须包含在最小生成树中。
5.2. 示例说明
我们来看一个加权图：
- Cut 将图分为 S₁（蓝色）和 S₂（粉色）。
- Cut Set 包括边 {E2, E3, E5, E6}。
- 其中 E5 权重最小。
根据 Cut Property，E5 必须出现在 MST 中。
构造 MST 后验证，E5 确实出现在 MST 中 ✅
5.3. Cut Property 的证明
我们用反证法来证明 Cut Property 的正确性。
假设
- 构造 MST T。
- Cut 将图分为 P 和 Q。
- 边 E_C 是连接 P 和 Q 中权重最小的边。
- 假设 E_C 不在 T 中。
推导过程
- 将 E_C 加入 T 会形成一个环。
- T 中一定存在另一条连接 P 和 Q 的边 K。
- 因为 E_C 是 Cut Set 中最轻的边，所以 K 的权重 > E_C。
- 替换 K 为 E_C 后，总权重降低 ⇒ T 不是最优的 ⇒ 假设不成立。
结论
- Cut Set 中权重最小的边必须出现在 MST 中。
5.4. 实际应用
Cut Property 是以下 MST 构造算法的核心依据：
| 算法 | 应用方式 |
|---|---|
| Prim 算法 | 每次选择连接已选集合与未选集合的最小边 |
| Kruskal 算法 | 按权重排序，选择不形成环的最小边 |
6. 总结
本文介绍了图论中 Cut 的基本概念及其在最小生成树中的 Cut Property。
我们通过图例和数学推导验证了 Cut Property 的正确性，并展示了它在 Prim 和 Kruskal 算法中的实际应用。
✅ 核心结论：
在构造最小生成树时，Cut Set 中权重最小的边必须被包含在 MST 中。
这是 MST 构造算法的理论基石，也是理解图算法的重要一步。