最小割的 Karger-Stein 随机收缩算法
字数 4082 2025-12-17 16:08:34

最小割的 Karger-Stein 随机收缩算法

一、题目描述

给定一个无向连通图 \(G = (V, E)\)（允许有平行边，但不允许有自环），每条边 \(e \in E\) 有一个非负的容量（或权重） \(c(e)\)。图的一个割是将顶点集 \(V\) 划分为两个非空子集 \(S\) 和 \(T = V \setminus S\)。割的容量定义为所有一个端点在 \(S\)，另一个端点在 \(T\) 的边的容量之和。我们的目标是找到一个割，使得其容量最小。这个问题称为“全局最小割”（Global Minimum Cut）问题，因为它不指定源点和汇点，目标是找到将图切分为两个部分所需割掉的最小边容量。

你需要理解和实现 Karger-Stein 算法，这是一个随机算法，用于高效地找到全局最小割。

二、解题过程循序渐进讲解

第一步：问题理解与基本定义

  1. 无向图的最小割：在无向图中，一个割是顶点集合 \(V\) 的一个划分 \((S, T)\)，其中 \(S \neq \emptyset, T \neq \emptyset, S \cap T = \emptyset, S \cup T = V\)。割的容量 \(c(S, T) = \sum_{u \in S, v \in T} c(u, v)\)，即所有跨越割的边的容量总和。全局最小割是容量最小的割。
  2. 与最大流的关系：在有向图中，根据最大流最小割定理，从源点 \(s\) 到汇点 \(t\) 的最大流值等于最小 \(s-t\) 割的容量。在无向图中，我们可以将每条无向边替换为两条方向相反、容量均为 \(c(e)\) 的有向边，然后将其视为有向图。此时，我们可以通过固定一个源点 \(s\)，并枚举所有可能的汇点 \(t\)，运行 \(n-1\) 次最大流算法来找到全局最小割（Stoer-Wagner 算法就基于这个思想）。但最大流算法（如 Push-Relabel, Dinic）复杂度较高，对于大规模图可能较慢。
  3. 随机算法的动机：Karger 提出了一种基于“边收缩”的随机算法，其思想简单，但能以高概率找到最小割，且时间复杂度低于确定性算法。

第二步：Karger 基本算法（随机收缩）

Karger 算法的核心是随机边收缩，直到图只剩下两个顶点，那么这两个顶点对应的划分就形成了一个割。

  1. 初始化：从原图 \(G\) 开始。
  2. 随机边收缩：
    • 在每一步，从当前图的边集中随机选择一条边（选择概率与边的容量成正比，即边的容量越大，被选中的概率越大）。
    • 收缩这条边。设选择的边是 \(e = (u, v)\)。收缩操作意味着将顶点 \(u\) 和 \(v\) 合并为一个新的顶点 \(w\)。
    • 所有原来与 \(u\) 或 \(v\) 相连的边现在都与 \(w\) 相连。如果合并后产生了自环（即一条边的两个端点都是 \(w\)），则删除这个自环。如果合并后产生了平行边（多条边连接相同的两个顶点），则将这些平行边合并为一条边，其容量为这些平行边的容量之和。
  3. 终止条件：重复步骤2，直到图中只剩下两个顶点为止。此时，连接这两个顶点的所有边的容量之和，就是本次随机收缩得到的割的容量。
  4. 重复运行：由于算法是随机的，单次运行找到最小割的概率可能不高。Karger 算法需要独立运行多次，并取所有运行中得到的最小割作为最终结果。

时间复杂度：使用邻接表或并查集优化，单次运行可以在 \(O(n^2)\) 或 \(O(m \alpha(n))\) 时间内完成，其中 \(n = |V|, m = |E|\)。

找到最小割的概率：Karger 证明了，对于任意一个无向图，单次运行 Karger 算法找到全局最小割的概率至少为 \(\frac{2}{n(n-1)}\)。这个概率看起来很小，但如果我们重复运行 \(T = \frac{n(n-1)}{2} \ln n\) 次，那么算法失败（即没有一次找到最小割）的概率可以降至 \(1/n\) 以下。

第三步：Karger-Stein 算法（递归收缩）

Karger 和 Stein 对基本算法进行了重要改进，将运行时间从 \(O(n^4 \log n)\) 降低到 \(O(n^2 \log^3 n)\)。核心思想是利用递归，在顶点数较多时，进行更“激进”的收缩，以增加保留最小割的概率。

算法流程如下（函数 KargerStein(G) 返回一个割的容量，但我们可以同时记录割的划分）：

  1. 基础情况：如果图 \(G\) 的顶点数 \(n \leq 6\)（或其他小的常数，比如 6），则使用确定性算法（如运行 \(n-1\) 次最大流，或枚举所有可能的割）找到确切的最小割，并返回。
  2. 递归收缩：
    • 设 \(t = \lceil 1 + n / \sqrt{2} \rceil\)（这是一个关键的参数）。
    • 对原图 \(G\) 执行两次独立的随机收缩过程，但不是收缩到只剩2个顶点，而是收缩到大约 \(t\) 个顶点。具体来说：
      • \(G_1 =\) 对 \(G\) 进行随机边收缩，直到顶点数减少到 \(t\)。
      • \(G_2 =\) 对 \(G\) 进行另一次独立的随机边收缩，直到顶点数减少到 \(t\)。
    • 递归调用：\(\text{cut}_1 = \text{KargerStein}(G_1)\)，\(\text{cut}_2 = \text{KargerStein}(G_2)\)。
    • 返回 \(\min(\text{cut}_1, \text{cut}_2)\)。
  3. 理解参数 \(t\)：\(t\) 的选择是为了平衡递归的深度和成功概率。通过收缩到 \(t\) 个顶点，我们以较高的概率保留了原图的最小割（Karger-Stein 证明了，在收缩到 \(t\) 个顶点的过程中，最小割的边一条都没被收缩掉的概率至少为 \(1/2\)）。因此，我们有两次机会（\(G_1\) 和 \(G_2\)）来“保护”最小割进入下一层递归。

时间复杂度分析：

  • 设 \(T(n)\) 为算法在 \(n\) 个顶点的图上的运行时间。
  • 收缩到 \(t\) 个顶点需要 \(O(n^2)\) 时间（通过维护顶点列表和边列表，并随机选择边进行收缩）。
  • 我们有两次递归调用，每次作用于一个大约 \(t \approx n/\sqrt{2}\) 个顶点的图。
  • 因此，递归式近似为 \(T(n) = 2T(n/\sqrt{2}) + O(n^2)\)。
  • 解这个递归式，得到 \(T(n) = O(n^2 \log n)\)（具体是 \(O(n^2 \log^3 n)\) 或类似，取决于实现细节）。
  • 由于我们运行一次 Karger-Stein 算法找到最小割的概率已经显著提高（比如常数概率），我们通常只需要运行常数次（比如2-3次）Karger-Stein 算法，就能以极高概率找到最小割。因此总时间复杂度为 \(O(n^2 \log^3 n)\) 或 \(O(n^2 \log^2 n)\)。

第四步：算法实现细节

  1. 图的表示：使用适合动态合并的数据结构。一种常见的方法是使用“邻接矩阵”的变体，或者维护一个顶点列表和一个边列表，每个顶点记录其包含的原图顶点集合（用于最后输出割的划分）。
  2. 边的随机选择：
    • 我们需要根据边的容量进行加权随机选择。可以预先计算所有边容量的总和 \(C\)，然后生成一个在 \([0, C)\) 之间的随机数 \(r\)，然后遍历边列表，累加边的容量，直到累加和超过 \(r\)，就选择了对应的边。
    • 为了高效，在收缩过程中，边的总容量会变化，我们需要动态维护。或者，我们可以不严格按容量比例选择，而是均匀随机选择边（对于未加权的图，即所有边容量为1），但在加权图中，这可能会降低找到最小割的概率。Karger-Stein 算法通常针对未加权图（或等价地，所有边容量为1的图）进行分析，但思想可以推广到加权图，此时选择概率应与边权重成正比。
  3. 收缩操作：
    • 合并顶点 \(u\) 和 \(v\) 时，将 \(v\) 合并到 \(u\) 上（或反之）。将所有与 \(v\) 相连的边（除了 \((u, v)\) 本身）重新连接到 \(u\)。
    • 检测并处理平行边：如果 \(u\) 和另一个顶点 \(x\) 之间原来已经有边，现在又因为 \(v\) 与 \(x\) 相连而新增一条边，则合并这两条边，容量相加。
    • 删除自环：检查所有连接到 \(u\) 的边，如果另一端也是 \(u\)，则删除。
  4. 递归实现：实现函数 contract(G, target_size)，将图 \(G\) 随机收缩到 target_size 个顶点。然后递归调用 KargerStein。

第五步：总结与扩展

  • Karger-Stein 算法是一个非常巧妙的随机算法，它展示了如何通过随机性和递归来显著加速经典问题。
  • 对于稠密图，Karger-Stein 的 \(O(n^2 \log^3 n)\) 比 Stoer-Wagner 的 \(O(n^3)\) 更有优势。
  • 算法的随机性意味着它可能失败，但我们可以通过多次独立运行（比如运行 \(O(\log n)\) 次）将失败概率降到任意低（如 \(1/n^c\)）。
  • 这个算法也适用于平行边，但不能有自环。
  • 对于有向图的最小割问题，不能直接应用此算法，因为有向图的割定义和收缩操作与无向图不同。
最小割的 Karger-Stein 随机收缩算法 一、题目描述 给定一个无向连通图 \( G = (V, E) \)（允许有平行边，但不允许有自环），每条边 \( e \in E \) 有一个非负的容量（或权重） \( c(e) \)。图的一个割是将顶点集 \( V \) 划分为两个非空子集 \( S \) 和 \( T = V \setminus S \)。割的容量定义为所有一个端点在 \( S \)，另一个端点在 \( T \) 的边的容量之和。我们的目标是找到一个割，使得其容量最小。这个问题称为“全局最小割”（Global Minimum Cut）问题，因为它不指定源点和汇点，目标是找到将图切分为两个部分所需割掉的最小边容量。 你需要理解和实现 Karger-Stein 算法，这是一个随机算法，用于高效地找到全局最小割。 二、解题过程循序渐进讲解 第一步：问题理解与基本定义 无向图的最小割 ：在无向图中，一个割是顶点集合 \( V \) 的一个划分 \( (S, T) \)，其中 \( S \neq \emptyset, T \neq \emptyset, S \cap T = \emptyset, S \cup T = V \)。割的容量 \( c(S, T) = \sum_ {u \in S, v \in T} c(u, v) \)，即所有跨越割的边的容量总和。全局最小割是容量最小的割。 与最大流的关系 ：在有向图中，根据最大流最小割定理，从源点 \( s \) 到汇点 \( t \) 的最大流值等于最小 \( s-t \) 割的容量。在无向图中，我们可以将每条无向边替换为两条方向相反、容量均为 \( c(e) \) 的有向边，然后将其视为有向图。此时，我们可以通过固定一个源点 \( s \)，并枚举所有可能的汇点 \( t \)，运行 \( n-1 \) 次最大流算法来找到全局最小割（Stoer-Wagner 算法就基于这个思想）。但最大流算法（如 Push-Relabel, Dinic）复杂度较高，对于大规模图可能较慢。 随机算法的动机 ：Karger 提出了一种基于“边收缩”的随机算法，其思想简单，但能以高概率找到最小割，且时间复杂度低于确定性算法。 第二步：Karger 基本算法（随机收缩） Karger 算法的核心是随机边收缩，直到图只剩下两个顶点，那么这两个顶点对应的划分就形成了一个割。 初始化 ：从原图 \( G \) 开始。 随机边收缩 ： 在每一步，从当前图的边集中 随机选择一条边 （选择概率与边的容量成正比，即边的容量越大，被选中的概率越大）。 收缩 这条边。设选择的边是 \( e = (u, v) \)。收缩操作意味着将顶点 \( u \) 和 \( v \) 合并为一个新的顶点 \( w \)。 所有原来与 \( u \) 或 \( v \) 相连的边现在都与 \( w \) 相连。如果合并后产生了 自环 （即一条边的两个端点都是 \( w \)），则删除这个自环。如果合并后产生了 平行边 （多条边连接相同的两个顶点），则将这些平行边合并为一条边，其容量为这些平行边的容量之和。 终止条件 ：重复步骤2，直到图中只剩下两个顶点为止。此时，连接这两个顶点的所有边的容量之和，就是本次随机收缩得到的割的容量。 重复运行 ：由于算法是随机的，单次运行找到最小割的概率可能不高。Karger 算法需要独立运行多次，并取所有运行中得到的最小割作为最终结果。 时间复杂度 ：使用邻接表或并查集优化，单次运行可以在 \( O(n^2) \) 或 \( O(m \alpha(n)) \) 时间内完成，其中 \( n = |V|, m = |E| \)。 找到最小割的概率 ：Karger 证明了，对于任意一个无向图，单次运行 Karger 算法找到全局最小割的概率至少为 \( \frac{2}{n(n-1)} \)。这个概率看起来很小，但如果我们重复运行 \( T = \frac{n(n-1)}{2} \ln n \) 次，那么算法失败（即没有一次找到最小割）的概率可以降至 \( 1/n \) 以下。 第三步：Karger-Stein 算法（递归收缩） Karger 和 Stein 对基本算法进行了重要改进，将运行时间从 \( O(n^4 \log n) \) 降低到 \( O(n^2 \log^3 n) \)。核心思想是利用递归，在顶点数较多时，进行更“激进”的收缩，以增加保留最小割的概率。 算法流程如下（函数 KargerStein(G) 返回一个割的容量，但我们可以同时记录割的划分）： 基础情况 ：如果图 \( G \) 的顶点数 \( n \leq 6 \)（或其他小的常数，比如 6），则使用确定性算法（如运行 \( n-1 \) 次最大流，或枚举所有可能的割）找到确切的最小割，并返回。 递归收缩 ： 设 \( t = \lceil 1 + n / \sqrt{2} \rceil \)（这是一个关键的参数）。 对原图 \( G \) 执行两次独立的随机收缩过程，但 不是 收缩到只剩2个顶点，而是收缩到大约 \( t \) 个顶点。具体来说： \( G_ 1 = \) 对 \( G \) 进行随机边收缩，直到顶点数减少到 \( t \)。 \( G_ 2 = \) 对 \( G \) 进行另一次独立的随机边收缩，直到顶点数减少到 \( t \)。 递归调用：\( \text{cut}_ 1 = \text{KargerStein}(G_ 1) \)，\( \text{cut}_ 2 = \text{KargerStein}(G_ 2) \)。 返回 \( \min(\text{cut}_ 1, \text{cut}_ 2) \)。 理解参数 \( t \) ：\( t \) 的选择是为了平衡递归的深度和成功概率。通过收缩到 \( t \) 个顶点，我们以较高的概率保留了原图的最小割（Karger-Stein 证明了，在收缩到 \( t \) 个顶点的过程中，最小割的边一条都没被收缩掉的概率至少为 \( 1/2 \)）。因此，我们有两次机会（\( G_ 1 \) 和 \( G_ 2 \)）来“保护”最小割进入下一层递归。 时间复杂度分析 ： 设 \( T(n) \) 为算法在 \( n \) 个顶点的图上的运行时间。 收缩到 \( t \) 个顶点需要 \( O(n^2) \) 时间（通过维护顶点列表和边列表，并随机选择边进行收缩）。 我们有两次递归调用，每次作用于一个大约 \( t \approx n/\sqrt{2} \) 个顶点的图。 因此，递归式近似为 \( T(n) = 2T(n/\sqrt{2}) + O(n^2) \)。 解这个递归式，得到 \( T(n) = O(n^2 \log n) \)（具体是 \( O(n^2 \log^3 n) \) 或类似，取决于实现细节）。 由于我们运行一次 Karger-Stein 算法找到最小割的概率已经显著提高（比如常数概率），我们通常只需要运行常数次（比如2-3次）Karger-Stein 算法，就能以极高概率找到最小割。因此总时间复杂度为 \( O(n^2 \log^3 n) \) 或 \( O(n^2 \log^2 n) \)。 第四步：算法实现细节 图的表示 ：使用适合动态合并的数据结构。一种常见的方法是使用“邻接矩阵”的变体，或者维护一个顶点列表和一个边列表，每个顶点记录其包含的原图顶点集合（用于最后输出割的划分）。 边的随机选择 ： 我们需要根据边的容量进行加权随机选择。可以预先计算所有边容量的总和 \( C \)，然后生成一个在 \( [ 0, C) \) 之间的随机数 \( r \)，然后遍历边列表，累加边的容量，直到累加和超过 \( r \)，就选择了对应的边。 为了高效，在收缩过程中，边的总容量会变化，我们需要动态维护。或者，我们可以不严格按容量比例选择，而是均匀随机选择边（对于未加权的图，即所有边容量为1），但在加权图中，这可能会降低找到最小割的概率。Karger-Stein 算法通常针对未加权图（或等价地，所有边容量为1的图）进行分析，但思想可以推广到加权图，此时选择概率应与边权重成正比。 收缩操作 ： 合并顶点 \( u \) 和 \( v \) 时，将 \( v \) 合并到 \( u \) 上（或反之）。将所有与 \( v \) 相连的边（除了 \( (u, v) \) 本身）重新连接到 \( u \)。 检测并处理平行边：如果 \( u \) 和另一个顶点 \( x \) 之间原来已经有边，现在又因为 \( v \) 与 \( x \) 相连而新增一条边，则合并这两条边，容量相加。 删除自环：检查所有连接到 \( u \) 的边，如果另一端也是 \( u \)，则删除。 递归实现 ：实现函数 contract(G, target_size) ，将图 \( G \) 随机收缩到 target_size 个顶点。然后递归调用 KargerStein。 第五步：总结与扩展 Karger-Stein 算法是一个非常巧妙的随机算法，它展示了如何通过随机性和递归来显著加速经典问题。 对于稠密图，Karger-Stein 的 \( O(n^2 \log^3 n) \) 比 Stoer-Wagner 的 \( O(n^3) \) 更有优势。 算法的随机性意味着它可能失败，但我们可以通过多次独立运行（比如运行 \( O(\log n) \) 次）将失败概率降到任意低（如 \( 1/n^c \)）。 这个算法也适用于平行边，但不能有自环。 对于有向图的最小割问题，不能直接应用此算法，因为有向图的割定义和收缩操作与无向图不同。