最小割的近似算法：Karger–Stein 随机收缩算法
字数 3481 2025-12-12 06:13:03

最小割的近似算法：Karger–Stein 随机收缩算法

我们来看一个关于图最小割的随机算法，它是 Karger 算法的一个更高效的版本。这个算法以其简洁性和理论意义而闻名，特别适合用来讲解随机算法在图论中的应用。

1. 问题描述

在一个无向连通图 \(G = (V, E)\) 中，每条边 \(e\) 有一个正整数权值 \(w(e)\)（简单图可视为所有权值为1）。图的割（Cut）定义为将顶点集 \(V\) 划分为两个非空子集 \(S\) 和 \(T\) 的一个划分。割的权值（或大小）是所有横跨 \(S\) 和 \(T\) 之间的边的权值之和。最小割问题就是要求找到一个权值最小的割。

例如，一个简单的环（Cycle）有 4 个顶点，那么它的最小割大小是 2（割断任意两条边即可将图分成两部分）。

2. 算法核心思想：随机边收缩

Karger 算法的基础操作是 边收缩（Edge Contraction）：

  • 随机选择一条边 \(e = (u, v)\)（按边权比例随机，等权图则均匀随机）。
  • 将边 \(e\) 的两个端点 \(u\) 和 \(v\) 合并成一个新的“超级顶点”。
  • 删除 \(e\) 自身。
  • 原来与 \(u\) 或 \(v\) 相连的边，现在都连到这个新的超级顶点上。
  • 注意：这个过程可能会产生平行边（多重边），这是允许的。

关键观察：

  1. 收缩一条边会减少一个顶点。
  2. 如果收缩的边不是最小割中的边，那么最小割的大小不会改变（因为割的边集仍然完整存在于收缩后的图中）。
  3. 当图中只剩下两个“超级顶点”时，它们之间的边就对应原始图的一个割。如果我们一直避免收缩最小割中的边，最后剩下的边就是整个最小割。

问题：如何提高找到最小割的概率？

3. 基础 Karger 算法

基础版本非常简单：

  1. 初始化图 \(G\)。
  2. 当图中顶点数大于 2 时：
    • 随机选择一条边（按权值比例）进行收缩。
  3. 当只剩下两个顶点时，它们之间的边的总权值就是当前找到的割的权值。
  4. 重复运行上述过程很多次（例如 \(O(n^2 \log n)\) 次），取所有运行中得到的最小权值作为答案。

为什么有效？

  • 设最小割的权值为 \(c\)，即恰好有 \(c\) 条边连接割的两边。
  • 图的总边权至少为 \(n \cdot c / 2\)（因为每个顶点的度数至少为 \(c\)）。
  • 在第一次随机选边时，选到最小割中的边的概率为：

\[ \frac{c}{\text{总边权}} \le \frac{c}{n c / 2} = \frac{2}{n} \]

  • 因此，单次运行成功（始终未收缩最小割的边）的概率至少为：

\[ \prod_{i=n}^{3} \left(1 - \frac{2}{i}\right) = \frac{2}{n(n-1)} \]

这个概率很低（比如 \(n=100\) 时约为 \(1/4950\)），所以需要重复很多次。

4. Karger–Stein 改进：递归收缩

基础版本需要运行 \(O(n^2 \log n)\) 次，总时间复杂度为 \(O(n^4 \log n)\)（因为每次收缩是 \(O(n^2)\)）。Karger 和 Stein 提出一个关键思想：当顶点数较多时，我们更容易“犯错”（收缩了最小割的边），所以可以提前“分支”运行，增加找到正确割的机会。

递归算法描述：
定义一个递归函数 Contract(G, t)：

  • 输入：图 \(G\)（允许平行边），目标顶点数 \(t\)。
  • 输出：将图收缩到只剩 \(t\) 个顶点后得到的图。

主算法 KargerStein(G)：

  1. 如果图 \(G\) 的顶点数 \(n \le 6\)：
    • 直接用枚举所有划分的方法计算最小割（因为 \(2^{n-1}\) 种割，此时很小）。
  2. 否则：
    • 令 \(t = \lceil 1 + n / \sqrt{2} \rceil\)（这个数的选择是为了优化概率）。
    • 独立运行两次 Contract(G, t)，得到两个较小的图 \(G_1\) 和 \(G_2\)。
    • 递归调用 KargerStein(G_1) 和 KargerStein(G_2)。
    • 返回两个递归结果中较小的那个割。

为什么这样设计？

  • 从 \(n\) 个顶点收缩到 \(t\) 个顶点的过程中，完全避开最小割边的概率相对较高（计算可得至少 \(1/2\) 左右）。
  • 我们做两次独立的收缩（到 \(t\) 个顶点），然后分别在两个较小的图上递归寻找最小割。这样，只要至少一次在收缩过程中避开了最小割边，递归下去就能找到全局最小割。
  • 通过递归，我们将成功概率从 \(O(1/n^2)\) 提升到了 \(O(1/\log n)\)。

5. 成功概率分析

  • 设 \(P(n)\) 为对 \(n\) 个顶点的图运行 KargerStein 算法找到最小割的概率。
  • 从 \(n\) 收缩到 \(t\) 的过程中，完全避开最小割边的概率至少为 \(1/2\)（通过精心选择的 \(t\) 值证明）。
  • 递归关系：

\[ P(n) \ge 1 - \left(1 - \frac{1}{2} P(t)\right)^2 \]

其中 \(t \approx n/\sqrt{2}\)。

  • 解此递归不等式可得 \(P(n) = \Omega\left(\frac{1}{\log n}\right)\)。
  • 因此，我们只需要运行 KargerStein 算法 \(O(\log^2 n)\) 次（每次独立），就可以以高概率（如 \(1 - 1/n\)）找到最小割。

6. 时间复杂度

  • 单次 Contract(G, t) 操作可以用邻接表实现，每次随机选边、合并顶点、维护边权，时间复杂度为 \(O(n^2)\)。
  • 递归树深度为 \(O(\log n)\)，每层总工作量约为 \(O(n^2)\)，所以单次 KargerStein 运行时间为 \(O(n^2 \log n)\)。
  • 由于我们需要运行 \(O(\log^2 n)\) 次来保证高概率成功，总时间复杂度为 \(O(n^2 \log^3 n)\)。
  • 这比 Stoer–Wagner 算法的 \(O(nm + n^2 \log n)\) 在某些稠密图上更有优势（因为 \(m = O(n^2)\) 时，Stoer–Wagner 是 \(O(n^3)\)，而 Karger–Stein 是 \(O(n^2 \log^3 n)\)）。

7. 算法步骤举例

假设有一个 8 个顶点的环图（最小割大小为 2）：

  1. 第一次递归调用：当前 \(n=8\)，计算 \(t = \lceil 1 + 8/\sqrt{2} \rceil \approx \lceil 1+5.66\rceil = 7\)。
  2. 进行两次独立的随机收缩，将图从 8 个顶点收缩到 7 个顶点。每次收缩随机选边、合并端点。
  3. 对得到的两个 7 顶点图，分别递归：
    • 对于 7 顶点图，计算 \(t = \lceil 1+7/1.414\rceil \approx \lceil 1+4.95\rceil = 6\)。
    • 再分别独立收缩到 6 顶点，得到四个 6 顶点图，继续递归……
  4. 当顶点数 ≤ 6 时，直接枚举所有可能的割（划分），找到最小割。
  5. 所有递归路径返回的割中，取最小值输出。

通过多次独立运行上述递归过程，我们有很大的机会命中那个全局最小割（权值为 2）。

8. 总结

  • Karger–Stein 算法是一个随机算法，它以高概率返回正确的最小割。
  • 核心是通过递归收缩和独立重复运行，将成功概率从指数级提高到多项式级。
  • 它在理论上有重要意义，展示了随机化在图论难题上的威力。
  • 虽然实际中 Stoer–Wagner 确定性算法更常用，但 Karger–Stein 在大规模稠密图上可能有更好的理论时间复杂度。

你可以将此算法看作一种“随机抽样然后精细搜索”的策略：先通过随机收缩快速减小问题规模，然后在较小的问题上递归搜索，最终通过多次实验确保结果可靠。

最小割的近似算法：Karger–Stein 随机收缩算法 我们来看一个关于图最小割的随机算法，它是 Karger 算法的一个更高效的版本。这个算法以其简洁性和理论意义而闻名，特别适合用来讲解随机算法在图论中的应用。 1. 问题描述 在一个 无向连通图 \( G = (V, E) \) 中，每条边 \( e \) 有一个正整数权值 \( w(e) \)（简单图可视为所有权值为1）。图的割（Cut）定义为将顶点集 \( V \) 划分为两个非空子集 \( S \) 和 \( T \) 的一个划分。割的权值（或大小）是所有横跨 \( S \) 和 \( T \) 之间的边的权值之和。 最小割问题 就是要求找到一个权值最小的割。 例如，一个简单的环（Cycle）有 4 个顶点，那么它的最小割大小是 2（割断任意两条边即可将图分成两部分）。 2. 算法核心思想：随机边收缩 Karger 算法的基础操作是 边收缩（Edge Contraction） ： 随机选择一条边 \( e = (u, v) \)（按边权比例随机，等权图则均匀随机）。 将边 \( e \) 的两个端点 \( u \) 和 \( v \) 合并 成一个新的“超级顶点”。 删除 \( e \) 自身。 原来与 \( u \) 或 \( v \) 相连的边，现在都连到这个新的超级顶点上。 注意：这个过程可能会产生 平行边 （多重边），这是允许的。 关键观察 ： 收缩一条边会减少一个顶点。 如果收缩的边 不是 最小割中的边，那么最小割的大小 不会改变 （因为割的边集仍然完整存在于收缩后的图中）。 当图中只剩下两个“超级顶点”时，它们之间的边就对应原始图的一个割。如果我们一直避免收缩最小割中的边，最后剩下的边就是整个最小割。 问题 ：如何提高找到最小割的概率？ 3. 基础 Karger 算法 基础版本非常简单： 初始化图 \( G \)。 当图中顶点数大于 2 时： 随机选择一条边（按权值比例）进行收缩。 当只剩下两个顶点时，它们之间的边的总权值就是当前找到的割的权值。 重复运行上述过程很多次（例如 \( O(n^2 \log n) \) 次），取所有运行中得到的最小权值作为答案。 为什么有效？ 设最小割的权值为 \( c \)，即恰好有 \( c \) 条边连接割的两边。 图的总边权至少为 \( n \cdot c / 2 \)（因为每个顶点的度数至少为 \( c \)）。 在第一次随机选边时，选到最小割中的边的概率为： \[ \frac{c}{\text{总边权}} \le \frac{c}{n c / 2} = \frac{2}{n} \] 因此， 单次运行成功（始终未收缩最小割的边）的概率至少为 ： \[ \prod_ {i=n}^{3} \left(1 - \frac{2}{i}\right) = \frac{2}{n(n-1)} \] 这个概率很低（比如 \( n=100 \) 时约为 \( 1/4950 \)），所以需要重复很多次。 4. Karger–Stein 改进：递归收缩 基础版本需要运行 \( O(n^2 \log n) \) 次，总时间复杂度为 \( O(n^4 \log n) \)（因为每次收缩是 \( O(n^2) \)）。Karger 和 Stein 提出一个关键思想： 当顶点数较多时，我们更容易“犯错”（收缩了最小割的边），所以可以提前“分支”运行，增加找到正确割的机会 。 递归算法描述 ： 定义一个递归函数 Contract(G, t) ： 输入：图 \( G \)（允许平行边），目标顶点数 \( t \)。 输出：将图收缩到只剩 \( t \) 个顶点后得到的图。 主算法 KargerStein(G) ： 如果图 \( G \) 的顶点数 \( n \le 6 \)： 直接用枚举所有划分的方法计算最小割（因为 \( 2^{n-1} \) 种割，此时很小）。 否则： 令 \( t = \lceil 1 + n / \sqrt{2} \rceil \)（这个数的选择是为了优化概率）。 独立运行两次 Contract(G, t) ，得到两个较小的图 \( G_ 1 \) 和 \( G_ 2 \)。 递归调用 KargerStein(G_1) 和 KargerStein(G_2) 。 返回两个递归结果中较小的那个割。 为什么这样设计？ 从 \( n \) 个顶点收缩到 \( t \) 个顶点的过程中， 完全避开最小割边的概率 相对较高（计算可得至少 \( 1/2 \) 左右）。 我们做两次独立的收缩（到 \( t \) 个顶点），然后分别在两个较小的图上递归寻找最小割。这样，只要 至少一次 在收缩过程中避开了最小割边，递归下去就能找到全局最小割。 通过递归，我们将成功概率从 \( O(1/n^2) \) 提升到了 \( O(1/\log n) \)。 5. 成功概率分析 设 \( P(n) \) 为对 \( n \) 个顶点的图运行 KargerStein 算法找到最小割的概率。 从 \( n \) 收缩到 \( t \) 的过程中，完全避开最小割边的概率至少为 \( 1/2 \)（通过精心选择的 \( t \) 值证明）。 递归关系： \[ P(n) \ge 1 - \left(1 - \frac{1}{2} P(t)\right)^2 \] 其中 \( t \approx n/\sqrt{2} \)。 解此递归不等式可得 \( P(n) = \Omega\left(\frac{1}{\log n}\right) \)。 因此，我们只需要运行 KargerStein 算法 \( O(\log^2 n) \) 次（每次独立），就可以以高概率（如 \( 1 - 1/n \)）找到最小割。 6. 时间复杂度 单次 Contract(G, t) 操作可以用邻接表实现，每次随机选边、合并顶点、维护边权，时间复杂度为 \( O(n^2) \)。 递归树深度为 \( O(\log n) \)，每层总工作量约为 \( O(n^2) \)，所以 单次 KargerStein 运行时间为 \( O(n^2 \log n) \) 。 由于我们需要运行 \( O(\log^2 n) \) 次来保证高概率成功，总时间复杂度为 \( O(n^2 \log^3 n) \)。 这比 Stoer–Wagner 算法的 \( O(nm + n^2 \log n) \) 在某些稠密图上更有优势（因为 \( m = O(n^2) \) 时，Stoer–Wagner 是 \( O(n^3) \)，而 Karger–Stein 是 \( O(n^2 \log^3 n) \)）。 7. 算法步骤举例 假设有一个 8 个顶点的环图（最小割大小为 2）： 第一次递归调用：当前 \( n=8 \)，计算 \( t = \lceil 1 + 8/\sqrt{2} \rceil \approx \lceil 1+5.66\rceil = 7 \)。 进行两次独立的随机收缩，将图从 8 个顶点收缩到 7 个顶点。每次收缩随机选边、合并端点。 对得到的两个 7 顶点图，分别递归： 对于 7 顶点图，计算 \( t = \lceil 1+7/1.414\rceil \approx \lceil 1+4.95\rceil = 6 \)。 再分别独立收缩到 6 顶点，得到四个 6 顶点图，继续递归…… 当顶点数 ≤ 6 时，直接枚举所有可能的割（划分），找到最小割。 所有递归路径返回的割中，取最小值输出。 通过多次独立运行上述递归过程，我们有很大的机会命中那个全局最小割（权值为 2）。 8. 总结 Karger–Stein 算法是一个 随机算法 ，它以高概率返回正确的最小割。 核心是通过 递归收缩 和 独立重复运行 ，将成功概率从指数级提高到多项式级。 它在理论上有重要意义，展示了随机化在图论难题上的威力。 虽然实际中 Stoer–Wagner 确定性算法更常用，但 Karger–Stein 在大规模稠密图上可能有更好的理论时间复杂度。 你可以将此算法看作一种“随机抽样然后精细搜索”的策略：先通过随机收缩快速减小问题规模，然后在较小的问题上递归搜索，最终通过多次实验确保结果可靠。