无向图的最小割的 Karger 算法
字数 2738 2025-12-24 12:54:31

无向图的最小割的 Karger 算法

题目描述

给定一个无向连通图 \(G = (V, E)\)，每条边没有边权（或视为单位边权）。
最小割 是指：将 \(G\) 的顶点划分成两个非空集合 \(S\) 和 \(T\) 时，横跨在 \(S\) 和 \(T\) 之间的边的数量。我们要寻找一种划分，使得这个边的数量最小。

注意：

  • 无向图的最小割在边权为 1 时，即为割边数量的最小值。
  • 这个算法是随机算法，不总是返回最小割，但能以较大概率返回正确结果。

算法思想概述

Karger 算法的核心是随机边收缩：

  1. 在图中随机选择一条边 \((u, v)\)。
  2. 将 \(u\) 和 \(v\) 合并成一个“超级顶点”，消除这条边，合并时保留多重边。
  3. 重复步骤 1 和 2，直到只剩下 2 个超级顶点为止。
  4. 此时连接这两个超级顶点之间的边的数量，就是本次随机收缩得到的一个“割”的大小。
  5. 多次重复这个过程，取得到的最小的割作为答案候选。

关键直觉：每次随机收缩一条边，最终剩下的两个超级顶点之间仍然保留的边，对应一种割。如果最小割的边在过程中从未被选中收缩，那么最后剩下的就是最小割。

逐步讲解

第一步：图的表示

用邻接表或边列表存储图。在实现时，为了方便合并顶点，通常用并查集（Union-Find）表示顶点集合，用边列表表示原始边，并在收缩过程中动态删除/合并边。

第二步：一次随机收缩的过程

  1. 初始化：并查集中每个顶点单独为一个集合。
  2. 当前剩余顶点数 \(n\) 初始为 \(|V|\)。
  3. 当 \(n > 2\) 时：
    • 在当前的边列表中等概率随机选一条边 \((u, v)\)（注意这里“当前”是指两端属于不同集合的边，即横跨不同集合的边）。
    • 如果 \(u\) 和 \(v\) 已属于同一个并查集集合，则这条边已经是“内部边”，丢弃它，重新选边。
    • 否则，合并 \(u\) 和 \(v\) 所在的集合（即收缩它们），并更新边列表，去除内部边。
    • 剩余顶点数 \(n\) 减 1。

实际上为了方便，我们通常不动态删除内部边，而是在选边时检查两端是否在同一集合，如果在则跳过，继续选下一条随机边。
更简单的实现：

  • 用边列表 \(E\) 存储所有原始边。
  • 用并查集维护集合。
  • 随机打乱边的顺序，依次遍历边，如果边的两端不在同一集合，就合并它们，直到剩下 2 个集合为止。
  • 然后计算最终两个集合之间的原始边数量，这就是割的大小。

第三步：一次 Karger 运行示例

假设图有顶点 {1,2,3,4}，边：
(1,2), (2,3), (3,4), (4,1), (1,3)
假设随机顺序是：(1,3), (1,2), (3,4), (2,3), (4,1)

  1. 选 (1,3)，合并 {1,3}。
  2. 选 (1,2)，此时代表 1 的集合是 {1,3}，2 是 {2}，不在同一集合，合并 {1,2,3}。
  3. 选 (3,4)，此时 3 在 {1,2,3}，4 在 {4}，合并 {1,2,3,4} 但此时只剩 1 个集合，提前结束？其实不对，应该继续直到只剩 2 个集合。

更好的流程是：我们不按随机顺序依次收缩，而是随机选边，直到剩下 2 个集合。

我们换一个流程：
初始：{1},{2},{3},{4}，剩余集合数=4。
随机选一条边，比如 (1,3)，合并 {1,3} → 集合：{1,3},{2},{4}，剩余=3。
随机选一条边，比如 (1,2)，此时 1 代表 {1,3}，2 是 {2}，不同，合并 → {1,2,3},{4}，剩余=2，停止。

现在两个集合是 {1,2,3} 和 {4}，看原始边哪些横跨：
(3,4) 是， (4,1) 是，所以割的大小 = 2。

但真实最小割是 2 吗？检查图：实际上这个图最小割是 2（比如割 {4} 与其它顶点，边(3,4),(4,1) 被割）。
所以这次运行得到了正确的最小割 2。

第四步：成功概率分析

重要结论（Karger 证明）：

  • 设最小割的边数为 \(c\)，则单次运行 Karger 算法得到最小割的概率至少为 \(\frac{2}{n(n-1)}\)。
  • 这是一个较小的概率，比如 \(n=100\)，单次成功概率约 \(2/(100*99) \approx 0.000202\)。

但我们重复运行很多次，取最小值，可大幅提高成功率。
如果运行 \(T\) 次，则失败概率（每次都得不到最小割）最多为：

\[\left(1 - \frac{2}{n(n-1)}\right)^T \]

为了让失败概率小于某个 \(\epsilon\)，需 \(T = O(n^2 \log(1/\epsilon))\)。

常用策略：运行 \(n^2 \log n\) 次，则失败概率可降至 \(1/n\) 量级。

第五步：优化版本 Karger-Stein 算法

Karger-Stein 算法是对基本 Karger 的改进，将单次运行时间从 \(O(n^2)\) 降到 \(O(n^2 \log n)\)，但整体成功率大幅提高，因此总体更快。

思想：

  • 当顶点数较多时，更容易保留最小割的边不被收缩。
  • 递归地：运行两次收缩直到剩下大约 \(n/\sqrt{2}\) 个顶点，然后递归地在较小的图上求最小割，最后取较好的结果。
  • 单次运行得最小割概率约 \(1/\log n\)，比基本 Karger 的 \(2/n^2\) 大得多。

实现细节（简述）：

  1. 如果顶点数 \(n \le 6\)，用穷举确定最小割。
  2. 否则，运行随机收缩直到剩下 \(t = \lceil 1 + n/\sqrt{2} \rceil\) 个顶点，得到图 \(G'\)。
  3. 在 \(G'\) 上递归调用两次算法，得到两个割值，取较小的返回。

成功率提高，只需运行 \(O(\log^2 n)\) 次，总时间 \(O(n^2 \log^3 n)\)。

第六步：算法实现要点（基本 Karger）

伪代码：

Karger(G):
    初始化并查集，每个顶点独立
    V_count = n
    边的副本列表 E_copy = E
    随机打乱 E_copy
    for 每条边 (u,v) in E_copy:
        if V_count == 2: break
        if find(u) != find(v):
            union(u, v)
            V_count -= 1
    # 现在有两个集合
    割值 = 0
    for 每条原始边 (u,v) in E:
        if find(u) != find(v):
            割值 += 1
    return 割值

多次运行 Karger，记录最小割值，即为结果。

总结

  • Karger 算法是首个用于最小割的随机收缩算法，简单而巧妙。
  • 单次成功概率低，但重复足够次数可得高正确率。
  • 优化版 Karger-Stein 将成功率提升到 \(1/\log n\)，更实用。
  • 注意：此算法针对无向图全局最小割，边权相等（可推广到正整数权重）。

这样，我们就完成了 Karger 随机算法求无向图最小割的讲解。

无向图的最小割的 Karger 算法 题目描述 给定一个无向连通图 \( G = (V, E) \)，每条边没有边权（或视为单位边权）。 最小割 是指：将 \( G \) 的顶点划分成两个非空集合 \( S \) 和 \( T \) 时， 横跨 在 \( S \) 和 \( T \) 之间的边的数量。我们要寻找一种划分，使得这个边的数量最小。 注意： 无向图的最小割在边权为 1 时，即为割边数量的最小值。 这个算法是 随机算法 ，不总是返回最小割，但能以较大概率返回正确结果。 算法思想概述 Karger 算法的核心是 随机边收缩 ： 在图中随机选择一条边 \((u, v)\)。 将 \( u \) 和 \( v \) 合并成一个“超级顶点”，消除这条边，合并时保留多重边。 重复步骤 1 和 2，直到只剩下 2 个超级顶点为止。 此时连接这两个超级顶点之间的边的数量，就是本次随机收缩得到的一个“割”的大小。 多次重复这个过程，取得到的最小的割作为答案候选。 关键直觉 ：每次随机收缩一条边，最终剩下的两个超级顶点之间仍然保留的边，对应一种割。如果最小割的边在过程中从未被选中收缩，那么最后剩下的就是最小割。 逐步讲解 第一步：图的表示 用邻接表或边列表存储图。在实现时，为了方便合并顶点，通常用 并查集 （Union-Find）表示顶点集合，用边列表表示原始边，并在收缩过程中动态删除/合并边。 第二步：一次随机收缩的过程 初始化：并查集中每个顶点单独为一个集合。 当前剩余顶点数 \( n \) 初始为 \( |V| \)。 当 \( n > 2 \) 时： 在当前的边列表中等概率随机选一条边 \( (u, v) \)（注意这里“当前”是指两端属于不同集合的边，即横跨不同集合的边）。 如果 \( u \) 和 \( v \) 已属于同一个并查集集合，则这条边已经是“内部边”，丢弃它，重新选边。 否则，合并 \( u \) 和 \( v \) 所在的集合（即收缩它们），并更新边列表，去除内部边。 剩余顶点数 \( n \) 减 1。 实际上为了方便，我们通常不动态删除内部边，而是在选边时检查两端是否在同一集合，如果在则跳过，继续选下一条随机边。 更简单的实现： 用边列表 \( E \) 存储所有原始边。 用并查集维护集合。 随机打乱边的顺序，依次遍历边，如果边的两端不在同一集合，就合并它们，直到剩下 2 个集合为止。 然后计算最终两个集合之间的原始边数量，这就是割的大小。 第三步：一次 Karger 运行示例 假设图有顶点 {1,2,3,4}，边： (1,2), (2,3), (3,4), (4,1), (1,3) 假设随机顺序是：(1,3), (1,2), (3,4), (2,3), (4,1) 选 (1,3)，合并 {1,3}。 选 (1,2)，此时代表 1 的集合是 {1,3}，2 是 {2}，不在同一集合，合并 {1,2,3}。 选 (3,4)，此时 3 在 {1,2,3}，4 在 {4}，合并 {1,2,3,4} 但此时只剩 1 个集合，提前结束？其实不对，应该继续直到只剩 2 个集合。 更好的流程是：我们 不按随机顺序依次收缩 ，而是随机选边，直到剩下 2 个集合。 我们换一个流程： 初始：{1},{2},{3},{4}，剩余集合数=4。 随机选一条边，比如 (1,3)，合并 {1,3} → 集合：{1,3},{2},{4}，剩余=3。 随机选一条边，比如 (1,2)，此时 1 代表 {1,3}，2 是 {2}，不同，合并 → {1,2,3},{4}，剩余=2，停止。 现在两个集合是 {1,2,3} 和 {4}，看原始边哪些横跨： (3,4) 是， (4,1) 是，所以割的大小 = 2。 但真实最小割是 2 吗？检查图：实际上这个图最小割是 2（比如割 {4} 与其它顶点，边(3,4),(4,1) 被割）。 所以这次运行得到了正确的最小割 2。 第四步：成功概率分析 重要结论（Karger 证明）： 设最小割的边数为 \( c \)，则单次运行 Karger 算法得到最小割的概率至少为 \( \frac{2}{n(n-1)} \)。 这是一个较小的概率，比如 \( n=100 \)，单次成功概率约 \( 2/(100* 99) \approx 0.000202 \)。 但我们重复运行很多次，取最小值，可大幅提高成功率。 如果运行 \( T \) 次，则失败概率（每次都得不到最小割）最多为： \[ \left(1 - \frac{2}{n(n-1)}\right)^T \] 为了让失败概率小于某个 \( \epsilon \)，需 \( T = O(n^2 \log(1/\epsilon)) \)。 常用策略 ：运行 \( n^2 \log n \) 次，则失败概率可降至 \( 1/n \) 量级。 第五步：优化版本 Karger-Stein 算法 Karger-Stein 算法是对基本 Karger 的改进，将单次运行时间从 \( O(n^2) \) 降到 \( O(n^2 \log n) \)，但整体成功率大幅提高，因此总体更快。 思想： 当顶点数较多时，更容易保留最小割的边不被收缩。 递归地：运行两次收缩直到剩下大约 \( n/\sqrt{2} \) 个顶点，然后递归地在较小的图上求最小割，最后取较好的结果。 单次运行得最小割概率约 \( 1/\log n \)，比基本 Karger 的 \( 2/n^2 \) 大得多。 实现细节（简述）： 如果顶点数 \( n \le 6 \)，用穷举确定最小割。 否则，运行随机收缩直到剩下 \( t = \lceil 1 + n/\sqrt{2} \rceil \) 个顶点，得到图 \( G' \)。 在 \( G' \) 上递归调用两次算法，得到两个割值，取较小的返回。 成功率提高，只需运行 \( O(\log^2 n) \) 次，总时间 \( O(n^2 \log^3 n) \)。 第六步：算法实现要点（基本 Karger） 伪代码： 多次运行 Karger，记录最小割值，即为结果。 总结 Karger 算法是首个用于最小割的 随机收缩算法 ，简单而巧妙。 单次成功概率低，但重复足够次数可得高正确率。 优化版 Karger-Stein 将成功率提升到 \( 1/\log n \)，更实用。 注意：此算法针对 无向图全局最小割 ，边权相等（可推广到正整数权重）。 这样，我们就完成了 Karger 随机算法求无向图最小割的讲解。