xxx 最小割的Karger算法

题目描述
给定一个无向连通图，每条边有一个权重（或容量），要求找到图的一个最小割。最小割是指将图的所有顶点划分成两个非空集合S和T，使得连接S和T的边的权重之和最小。Karger算法是一种基于随机收缩边的蒙特卡洛算法，通过多次随机执行来高概率找到最小割。

解题过程

1. 算法核心思想

   • 通过反复随机选择一条边并“收缩”它（将边的两个端点合并为一个超顶点），逐步减少顶点数量，直到图中只剩两个超顶点。此时连接这两个超顶点的边集即为一个割。
   • 由于收缩过程是随机的，单次运行可能无法得到最小割，但重复运行多次并取权重最小的割，可以高概率找到正确解。

2. 边的收缩操作

   • 假设选择边(u, v)，收缩操作将u和v合并为一个新顶点w。
   • 所有原本与u或v相连的边改为连接到w（若边连接u和v自身，则形成自环，直接删除）。
   • 收缩后，图的顶点数减少1，但割的权重信息保留在剩余边上（合并边的权重相加）。

3. 单次算法步骤

   • 输入：无向图G(V, E)，边权重函数w。
   • 过程：
     a. 初始化：将每个顶点视为一个独立集合。
     b. 当图中剩余顶点数大于2时：
     i. 以概率正比于边权重随机选择一条边（e.g., 权重越大的边被选中的概率越高）。
     ii. 收缩这条边，合并两个端点，移除自环。
     c. 终止时，剩余两个超顶点之间的边权重之和即为当前割的权重。
   • 输出：割的权重及对应的顶点划分（通过记录收缩历史可还原集合）。

4. 成功率与重复次数

   • 单次运行找到最小割的概率至少为2/(n(n-1))（n为顶点数），概率较低。
   • 通过独立重复运行算法T次（T通常取O(n² log n)），失败概率可降至1/n（即成功率接近1）。
   • 实际中常取T = n²，再结合优化（如Karger-Stein算法通过递归提高效率）。

5. 实例演示（简例）

   • 假设图有4个顶点{1,2,3,4}，边权重均匀。
   • 第一次运行：随机收缩边(1,3)→顶点{1-3,2,4}，再收缩(2,4)→{1-3,2-4}，最后割为边(1-3,2-4)的权重和。
   • 多次运行后，取所有结果中的最小权重作为最终解。

关键点

• 收缩需保留权重合并，确保割计算正确。
• 随机性要求边选择需权重加权随机（避免偏向轻边）。
• 算法适用于无向图，最小割可能不唯一，但权重唯一。