xxx 无向图的最小割的 Karger 算法

题目描述
给定一个无向连通图 G=(V,E)，每条边可能带有权重（也可以是无权图，即所有边权重为1）。图的一个割是将顶点集 V 划分成两个非空子集 S 和 V\S。割的大小是连接 S 和 V\S 子集的所有边的权重之和（对于无权图，就是边的数量）。最小割问题是寻找一个割，使得割的大小最小。Karger 算法是一个随机算法，用于求解无向图的最小割问题。它通过随机边收缩来减少顶点数量，最终以一定概率输出最小割。

解题过程

1. 基本思想
   Karger 算法的核心思想是随机收缩图中的边，逐步减少顶点数量，直到只剩下两个顶点。此时，连接这两个顶点的边集就对应原图的一个割。通过多次独立运行该过程，并取所有运行中得到的最小割作为结果，可以以高概率找到真正的最小割。

2. 关键概念：边收缩
   边收缩是指将一条边 e=(u,v) 收缩成一个新的顶点。具体步骤：

   • 移除边 e
   • 将顶点 u 和 v 合并为一个新顶点 w
   • 所有原本与 u 或 v 相连的边现在都与 w 相连（注意：如果某顶点同时与 u 和 v 相连，则合并后与 w 有两条边，即产生重边）
   • 移除自环（即连接 w 与 w 的边）

3. 算法步骤
   Karger 算法的一次运行包含以下步骤：

   • 输入：无向图 G=(V,E)
   • 当 |V| > 2 时：
     a. 随机均匀选择一条边 e∈E
     b. 收缩边 e
   • 输出：当前图中剩余的边集作为候选割

4. 正确性分析

   • 关键点：最小割在收缩过程中得以保留的概率
   • 设图 G 的最小割大小为 k，则每个顶点的度至少为 k（因为最小割分离该顶点与其余顶点需要至少 k 条边）
   • 因此，图的总边数 |E| ≥ (k·|V|)/2
   • 在第一次收缩时，随机选择的边属于最小割的概率 ≤ k/|E| ≤ 2/|V|
   • 所以不属于最小割的概率 ≥ 1 - 2/|V|
   • 递归分析，最终得到最小割的概率 ≥ 1/(C(|V|,2)) = 2/(|V|(|V|-1))

5. 概率放大
   单次运行成功概率较低，但通过重复运行可以放大成功概率：

   • 重复运行算法 N 次，取所有运行中得到的最小割
   • 若希望成功概率 ≥ 1-ε，则需要运行次数 N = O(|V|² log(1/ε))
   • 例如：运行 |V|² log|V| 次，成功概率可达 1 - 1/|V|

6. 时间复杂度

   • 单次运行时间复杂度：使用邻接表表示时，可通过联合查找数据结构优化到 O(|V|²)
   • 总时间复杂度：O(|V|⁴ log|V|) 对于高概率结果
   • 注意：这是一个蒙特卡洛算法——可能出错，但概率可控

7. 实际实现技巧

   • 使用联合查找数据结构来高效管理顶点合并
   • 维护动态边列表，在收缩时更新边信息
   • 对于有权图，需要适当处理边权重的合并

总结
Karger 算法通过随机边收缩和概率放大，为最小割问题提供了一个简单而优雅的随机解决方案。虽然理论最坏情况复杂度较高，但在实践中对于中等规模图表现良好，且算法思想深刻影响了后续的随机图算法发展。