图论中的最小割问题（Karger算法）
字数 2177 2025-11-05 08:30:59

图论中的最小割问题（Karger算法）

题目描述
给定一个无向连通图 \(G = (V, E)\)，每条边可能带有权重（权重最小割问题）或无权（默认边权为1）。最小割（Minimum Cut）的目标是找到一种划分，将顶点集 \(V\) 分成两个非空子集 \(S\) 和 \(T\)，使得连接 \(S\) 和 \(T\) 的边的权重之和最小。Karger算法是一种基于随机化的算法，特别适用于解决无权图的最小割问题，并以高概率返回正确结果。

解题过程

1. 核心思想：随机边收缩
Karger算法的基本思路是通过反复随机选择一条边并将其“收缩”（Contract），逐步减少图中的顶点数量，直到图中仅剩两个顶点。此时，连接这两个顶点的边集即为一个候选割集。通过多次重复这一过程，选择权重最小的割作为最终结果。

关键定义：

  • 边收缩：将边 \(e = (u, v)\) 收缩意味着将顶点 \(u\) 和 \(v\) 合并为一个新顶点，并保留所有与 \(u, v\) 相连的边（合并后产生的自环需删除，因为自环不连接不同顶点集）。

2. 算法步骤详解
输入：无向图 \(G = (V, E)\)（权重可选）。
输出：一个割的权重值（或割集本身）。

步骤：

  1. 初始化：复制原图 \(G\) 为 \(G'\)，避免修改原图。
  2. 循环收缩：当 \(G'\) 中剩余顶点数大于 2 时：
    a. 在 \(G'\) 的边集中随机选择一条边 \(e = (u, v)\)（每条边被选中的概率与权重成比例）。
    b. 收缩边 \(e\)：将 \(u\) 和 \(v\) 合并为一个新顶点，删除 \(e\)，并将所有与 \(u\) 或 \(v\) 相连的边连接到新顶点。
    c. 删除合并后产生的自环（即连接新顶点自身的边）。
  3. 终止条件：当 \(G'\) 只剩两个顶点 \(s\) 和 \(t\) 时，连接 \(s\) 和 \(t\) 的所有边的权重之和即为当前割的权重。
  4. 重复实验：独立重复上述过程 \(T\) 次（\(T\) 的取值后文讨论），保留所有尝试中的最小割值。

3. 关键细节与正确性分析

  • 为什么随机收缩有效？
    设最小割的权重为 \(k\)，即原图有 \(k\) 条边连接割集 \(S\) 和 \(T\)。在收缩过程中，如果从未选中这 \(k\) 条边中的任何一条，那么最终得到的割就是最小割。

    • 计算一次运行成功概率：
      设顶点数为 \(n\)，边数为 \(m\)。在第一次收缩时，选中最小割边的概率为 \(\frac{k}{m}\)，需避免选中。每次收缩后顶点数减少 1，边数可能减少（但非严格递减）。可以证明，单次运行找到最小割的概率至少为 \(\frac{2}{n(n-1)}\)。
    • 例如，当 \(n=10\) 时，成功概率约 \(1/45 \approx 2.2\%\)，虽然低，但通过重复实验可提高成功率。

  • 重复次数 \(T\) 的设定：
    为保证算法以至少 \(1 - \frac{1}{n}\) 的概率成功，需重复 \(T = O(n^2 \log n)\) 次。具体可取 \(T = \frac{n(n-1)}{2} \ln n\)。

4. 实例演示
考虑一个简单图：4个顶点 \(\{A, B, C, D\}\)，边为 \((A,B), (A,C), (B,C), (B,D), (C,D)\)（无权）。最小割为 2（割集 \(\{A\}\) 与其余顶点，或 \(\{D\}\) 与其余顶点）。

  • 一次运行可能场景：
    1. 随机选边 \((B,C)\) 收缩，合并 \(B\) 和 \(C\) 为新顶点 \(BC\)。
    2. 图变为顶点 \(\{A, BC, D\}\)，边为 \((A,BC)\)（重边合并为一条）、\((BC,D)\)。
    3. 随机选边 \((A,BC)\) 收缩，合并 \(A\) 和 \(BC\) 为 \(ABC\)。
    4. 最终顶点 \(\{ABC, D\}\)，边为 \((ABC,D)\)（权重 2），得到割值 2（成功）。
  • 若某次运行误删了最小割边（如第一步选 \((A,B)\)），可能得到错误割值（如 3）。

5. 优化：Karger-Stein算法
原始Karger算法成功率低，Karger-Stein通过递归优化将成功率提升至 \(O(1/\log n)\)。

  • 思想：在收缩到 \(n/\sqrt{2}\) 个顶点时，克隆当前图并独立继续两次递归实验，取最优结果。
  • 递归深度为 \(O(\log n)\)，总时间复杂度 \(O(n^2 \log n)\)，远优于原始算法的多次重复。

6. 总结

  • Karger算法通过随机化避免暴力枚举所有割（共 \(2^{n-1}\) 种可能），以概率换时间。
  • 适用于稀疏图的最小割近似求解，尤其在教学和理论分析中重要。
  • 实际应用中，若需高精度最小割，常结合确定性算法（如Stoer-Wagner算法）。
图论中的最小割问题（Karger算法） 题目描述 给定一个无向连通图 \( G = (V, E) \)，每条边可能带有权重（权重最小割问题）或无权（默认边权为1）。最小割（Minimum Cut）的目标是找到一种划分，将顶点集 \( V \) 分成两个非空子集 \( S \) 和 \( T \)，使得连接 \( S \) 和 \( T \) 的边的权重之和最小。Karger算法是一种基于随机化的算法，特别适用于解决无权图的最小割问题，并以高概率返回正确结果。 解题过程 1. 核心思想：随机边收缩 Karger算法的基本思路是通过反复随机选择一条边并将其“收缩”（Contract），逐步减少图中的顶点数量，直到图中仅剩两个顶点。此时，连接这两个顶点的边集即为一个候选割集。通过多次重复这一过程，选择权重最小的割作为最终结果。 关键定义 ： 边收缩 ：将边 \( e = (u, v) \) 收缩意味着将顶点 \( u \) 和 \( v \) 合并为一个新顶点，并保留所有与 \( u, v \) 相连的边（合并后产生的自环需删除，因为自环不连接不同顶点集）。 2. 算法步骤详解 输入 ：无向图 \( G = (V, E) \)（权重可选）。 输出 ：一个割的权重值（或割集本身）。 步骤 ： 初始化 ：复制原图 \( G \) 为 \( G' \)，避免修改原图。 循环收缩 ：当 \( G' \) 中剩余顶点数大于 2 时： a. 在 \( G' \) 的边集中随机选择一条边 \( e = (u, v) \)（每条边被选中的概率与权重成比例）。 b. 收缩边 \( e \)：将 \( u \) 和 \( v \) 合并为一个新顶点，删除 \( e \)，并将所有与 \( u \) 或 \( v \) 相连的边连接到新顶点。 c. 删除合并后产生的自环（即连接新顶点自身的边）。 终止条件 ：当 \( G' \) 只剩两个顶点 \( s \) 和 \( t \) 时，连接 \( s \) 和 \( t \) 的所有边的权重之和即为当前割的权重。 重复实验 ：独立重复上述过程 \( T \) 次（\( T \) 的取值后文讨论），保留所有尝试中的最小割值。 3. 关键细节与正确性分析 为什么随机收缩有效？ 设最小割的权重为 \( k \)，即原图有 \( k \) 条边连接割集 \( S \) 和 \( T \)。在收缩过程中，如果从未选中这 \( k \) 条边中的任何一条，那么最终得到的割就是最小割。 计算一次运行成功概率： 设顶点数为 \( n \)，边数为 \( m \)。在第一次收缩时，选中最小割边的概率为 \( \frac{k}{m} \)，需避免选中。每次收缩后顶点数减少 1，边数可能减少（但非严格递减）。可以证明，单次运行找到最小割的概率至少为 \( \frac{2}{n(n-1)} \)。 例如，当 \( n=10 \) 时，成功概率约 \( 1/45 \approx 2.2\% \)，虽然低，但通过重复实验可提高成功率。 重复次数 \( T \) 的设定 ： 为保证算法以至少 \( 1 - \frac{1}{n} \) 的概率成功，需重复 \( T = O(n^2 \log n) \) 次。具体可取 \( T = \frac{n(n-1)}{2} \ln n \)。 4. 实例演示 考虑一个简单图：4个顶点 \( \{A, B, C, D\} \)，边为 \( (A,B), (A,C), (B,C), (B,D), (C,D) \)（无权）。最小割为 2（割集 \( \{A\} \) 与其余顶点，或 \( \{D\} \) 与其余顶点）。 一次运行可能场景 ： 随机选边 \( (B,C) \) 收缩，合并 \( B \) 和 \( C \) 为新顶点 \( BC \)。 图变为顶点 \( \{A, BC, D\} \)，边为 \( (A,BC) \)（重边合并为一条）、\( (BC,D) \)。 随机选边 \( (A,BC) \) 收缩，合并 \( A \) 和 \( BC \) 为 \( ABC \)。 最终顶点 \( \{ABC, D\} \)，边为 \( (ABC,D) \)（权重 2），得到割值 2（成功）。 若某次运行误删了最小割边（如第一步选 \( (A,B) \)），可能得到错误割值（如 3）。 5. 优化：Karger-Stein算法 原始Karger算法成功率低，Karger-Stein通过递归优化将成功率提升至 \( O(1/\log n) \)。 思想 ：在收缩到 \( n/\sqrt{2} \) 个顶点时，克隆当前图并独立继续两次递归实验，取最优结果。 递归深度为 \( O(\log n) \)，总时间复杂度 \( O(n^2 \log n) \)，远优于原始算法的多次重复。 6. 总结 Karger算法通过随机化避免暴力枚举所有割（共 \( 2^{n-1} \) 种可能），以概率换时间。 适用于稀疏图的最小割近似求解，尤其在教学和理论分析中重要。 实际应用中，若需高精度最小割，常结合确定性算法（如Stoer-Wagner算法）。