xxx 最小割的 Gomory-Hu 树算法

题目描述
最小割问题是图论中的一个经典问题，旨在将图的顶点划分为两个集合，使得连接这两个集合的边的总权重（容量）最小。Gomory-Hu 树算法通过构建一棵树（称为 Gomory-Hu 树）来高效表示图中所有顶点对之间的最小割。该树具有以下性质：对于树中任意两个顶点，连接它们唯一路径上的最小权重边恰好对应原图中这两个顶点之间的最小割容量。算法通过递归分割图并计算最小割来构建这棵树，最终实现 O(n) 次最大流计算（n 为顶点数）即可得到所有顶点对的最小割信息。

解题过程

1. 基础概念

   • 最小割：对于无向连通图 G=(V,E)，割是将 V 划分为两个非空集合 S 和 V\S，割的容量是连接 S 和 V\S 的所有边的权重和。最小割是容量最小的割。
   • Gomory-Hu 树：一棵带权树 T=(V,E')，其中任意两点 u,v 在 T 中路径的最小边权重等于原图中 u 和 v 之间的最小割容量。

2. 算法核心思想

   • Gomory-Hu 树通过递归地“收缩”图并计算最小割来构建。每次选择一个顶点对，计算它们之间的最小割，然后根据割将图分割为两部分，递归处理每个部分。
   • 关键步骤包括：
     • 选择顶点对并计算最小割。
     • 根据割收缩图，生成子问题。
     • 将子问题的解合并为全局的 Gomory-Hu 树。

3. 详细步骤
   步骤 1：初始化

   • 从原图 G 开始，设当前顶点集合为 V，初始 Gomory-Hu 树为空。

   步骤 2：选择顶点对与计算最小割

   • 从当前顶点集合中任选两个顶点 s 和 t（例如 s 为固定顶点，t 为其他顶点）。
   • 使用最大流算法（如 Edmonds-Karp 或 Dinic）计算 s 和 t 之间的最小割（即最大流值）。记录割 (S, V\S)，其中 s ∈ S，t ∈ V\S。

   步骤 3：收缩图与递归构建

   • 将集合 S 收缩为一个超级顶点 s'，将 V\S 收缩为另一个超级顶点 t'。在新图中，保留原图中连接 S 和 V\S 的边，权重为最小割容量。
   • 递归地对 S 和 V\S 两个子图执行步骤 2-3，直到子图只剩一个顶点。

   步骤 4：合并子树

   • 将递归得到的子树通过边连接起来，边的权重为对应最小割的容量。例如，若子图 S 的 Gomory-Hu 树为 T_S，子图 V\S 的树为 T_{V\S}，则用一条权重为最小割容量的边连接 T_S 和 T_{V\S} 中代表 s 和 t 的顶点。

   步骤 5：验证与输出

   • 最终得到的树即为 Gomory-Hu 树，其中任意两顶点间路径的最小权重边对应原图中它们的最小割容量。

4. 实例演示
   考虑一个无向图，顶点集 {A,B,C,D}，边及权重：

   • (A,B): 3, (A,C): 2, (B,C): 1, (B,D): 4, (C,D): 5
   • 以 A 为根，计算 A 与 B 的最小割（容量为 3，割为 {A} 和 {B,C,D}）。
   • 递归处理 {A} 和 {B,C,D}，在 {B,C,D} 中计算 B 与 C 的最小割（容量为 1，割为 {B} 和 {C,D}）。
   • 继续递归，最终得到 Gomory-Hu 树：边 (A,B):3, (B,C):1, (C,D):5。验证任意两点（如 A 和 D）路径最小边权重为 1，与原图最小割一致。

5. 算法复杂度

   • 需计算 n-1 次最小割（最大流），每次最大流计算复杂度取决于所用算法（如 O(VE²) 用于 Edmonds-Karp）。总复杂度为 O(n * T_maxflow)，其中 T_maxflow 是单次最大流的复杂度。

6. 应用场景

   • 网络可靠性分析、图像分割、社交社区发现等需要快速查询任意两点间连接强度的场景。