图的割与连通度 图论中， 割 是研究图连通性的重要工具，它通过删除边或顶点来破坏图的连通结构，从而量化图的“脆弱性”。以下将逐步介绍相关概念。 1. 边割与边连通度 （1）边割的定义 设图 \( G = (V, E) \) 为无向图，若删除边集 \( S \subseteq E \) 后图变得不连通，且 \( S \) 是满足此条件的极小集合（即 \( S \) 的任一真子集均不能使图不连通），则称 \( S \) 为 边割 。 示例 ：树中任意一条边均构成边割，因为删除后树会分裂为两个连通分支。 （2）边连通度的定义 图 \( G \) 的 边连通度 （记为 \( \lambda(G) \)）是使图不连通需删除的 最少边数 。若 \( G \) 本身不连通，则 \( \lambda(G) = 0 \)；若 \( G \) 为平凡图（仅一个顶点），约定 \( \lambda(G) = 0 \)。 性质 ： 对任意图，\( \lambda(G) \leq \delta(G) \)（其中 \( \delta(G) \) 为最小度）。 若 \( \lambda(G) \geq k \)，则称 \( G \) 是 k-边连通 的。 2. 点割与点连通度 （1）点割的定义 若删除顶点集 \( T \subseteq V \) 后图变得不连通（或顶点数减少），且 \( T \) 是极小的，则称 \( T \) 为 点割 。 注意 ：删除顶点时需同时删除与其关联的边。 （2）点连通度的定义 图 \( G \) 的 点连通度 （记为 \( \kappa(G) \)）是使图不连通需删除的 最少顶点数 （保留孤立点的情况需特殊处理）。 若 \( G \) 为完全图 \( K_ n \)，删除少于 \( n-1 \) 个顶点不会破坏连通性，故约定 \( \kappa(K_ n) = n-1 \)。 性质 ： 对任意非完全图，\( \kappa(G) \leq \lambda(G) \leq \delta(G) \)。 若 \( \kappa(G) \geq k \)，则称 \( G \) 是 k-连通 的。 3. 门格尔定理 该定理揭示了割与连通路径的内在联系： 边形式 ：对于无向图中两个顶点 \( u, v \)，使 \( u \) 和 \( v \) 不连通所需删除的最少边数，等于它们之间边不交路径的最大数量。 点形式 ：使 \( u \) 和 \( v \) 不连通所需删除的最少顶点数（不含 \( u, v \)），等于它们之间内部顶点不交路径的最大数量。 4. 应用与算法 网络可靠性分析 ：通过边连通度评估通信网络抗链路故障的能力。 最小割算法 ：例如 Ford-Fulkerson 算法 求最大流（等价于最小割），用于解决网络分割问题。 哈拉里图 ：若 \( \kappa(G) = \lambda(G) = \delta(G) \)，则称 \( G \) 为哈拉里图，这类图在连通性研究中具有对称性。 5. 进阶概念 全局最小割 ：不指定顶点对时，图的最小边割大小。可使用 Stoer-Wagner 算法 在 \( O(|V||E| + |V|^2 \log |V|) \) 时间内求解。 Whitney 定理 ：对任意无向图，有 \( \kappa(G) \leq \lambda(G) \leq \delta(G) \)。 通过理解割与连通度，可深入分析图的冗余性、脆弱性及优化网络设计。