xxx 无向图的最小割的 Karger 算法
字数 2221 2025-12-10 21:55:18

xxx 无向图的最小割的 Karger 算法

问题描述
给定一个无向图 \(G = (V, E)\)，每条边 \(e \in E\) 有一个非负权重 \(w(e)\)（若未指定权重，可视为单位权重）。图的一个割（cut）是将顶点集 \(V\) 划分成两个非空子集 \(S\) 和 \(T = V \setminus S\) 的分割。割的容量（capacity）是连接 \(S\) 和 \(T\) 的所有边的权重之和，记作 \(c(S, T) = \sum_{e \in E, e \text{ 连接 } S \text{ 与 } T} w(e)\)。最小割问题是找到容量最小的割。Karger 算法是一种随机算法，通过随机边收缩来求解最小割，能以高概率返回正确的最小割。

解题过程

  1. 核心思想
    Karger 算法的基本思想是：随机选择一条边并将其“收缩”（contract），即将这条边的两个端点合并为一个超级顶点，并移除产生的自环（self-loop），但保留连接超级顶点与其他顶点的多条边（即允许重边）。重复收缩过程，直到图中只剩下两个超级顶点，此时剩下的边对应一个割。由于收缩是随机的，多次运行算法能提高得到最小割的概率。

  2. 算法步骤

    • 初始化：复制原图 \(G\) 到临时图 \(G'\)，避免修改原图。
    • 当 \(G'\) 中顶点数大于 2 时：
      a. 在 \(G'\) 中随机均匀选择一条边（权重不影响选择概率，可视为按边等概率选取）。
      b. 收缩这条边：将边的两个端点 \(u\) 和 \(v\) 合并为一个新顶点 \(uv\)；删除连接 \(u\) 和 \(v\) 的所有边（自环）；将与 \(u\) 或 \(v\) 相连的边改为连接 \(uv\)，并保留重边。
    • 结束时，\(G'\) 只剩下两个顶点，它们之间的边构成一个割，其权重和即为返回的割容量。

  3. 细节说明

    • 边的选择：在无向图中，通常维护一个边列表，每次从列表中等概率随机选取一条边执行收缩。
    • 收缩操作：实现时常用并查集（Union-Find）来跟踪顶点所属的超级顶点，但需注意处理重边——合并后，两个超级顶点之间的多条边可合并为一条边，其权重为原多条边权重之和。
    • 返回结果：多次（如 \(O(n^2 \log n)\) 次）独立运行算法，取所有运行中得到的最小割值作为最终答案。

  4. 正确性分析

    • 关键点：最小割的边数至少为 1。在收缩过程中，如果从未选中最小割中的边进行收缩，则最后得到的割就是原图的最小割（因为最小割的边始终保留）。
    • 概率下界：设原图的最小割容量为 \(c\)，即最小割有 \(c\) 条边。原图的边数至少为 \(\frac{c n}{2}\)（因为每个顶点至少连出 \(c\) 条边到另一部分），所以随机选到最小割边的概率至多为 \(\frac{c}{|E|} \leq \frac{2}{n}\)。
    • 一次运行得到最小割的概率：通过分析，概率至少为 \(\frac{2}{n(n-1)}\)，即 \(\Omega(1/n^2)\)。
    • 提高概率：重复运行算法 \(T = n^2 \log n\) 次，则至少有一次得到最小割的概率为 \(1 - (1 - \frac{2}{n^2})^{T} \approx 1 - e^{-2 \log n} = 1 - \frac{1}{n^2}\)，非常高。

  5. 时间复杂度

    • 一次运行的时间复杂度为 \(O(n^2)\)，若用邻接矩阵或动态边列表实现收缩。
    • 运行 \(O(n^2 \log n)\) 次，总时间复杂度为 \(O(n^4 \log n)\)，这看起来很高，但实际中通过优化（如 Karger-Stein 算法）可降到 \(O(n^2 \log^3 n)\)。

  6. 示例演示
    考虑一个简单无向图：顶点集 \(\{A, B, C, D\}\)，边为 \((A,B), (A,C), (A,D), (B,C), (B,D)\)，权重均为 1。最小割容量为 2（例如割 \(S = \{A\}, T = \{B,C,D\}\)，边为 \((A,B), (A,C), (A,D)\) 容量 3；割 \(S = \{A,B\}, T = \{C,D\}\) 边为 \((A,C), (A,D), (B,C), (B,D)\) 容量 4；实际最小割是 \(S = \{A,B,C\}, T = \{D\}\) 边为 \((A,D), (B,D)\) 容量 2）。

    • 随机运行 1：可能依次收缩边 \((A,B)\)、然后 \((AB,C)\)，最后剩下 \((ABC)\) 和 \(D\)，割边为 \((A,D)\) 和 \((B,D)\)，容量 2，即得到最小割。
    • 随机运行 2：若先收缩 \((A,D)\)，可能丢失最小割边，最后得到更大容量的割。

总结
Karger 算法通过随机边收缩，以多项式时间、高概率求解无向图最小割。其核心在于重复运行以放大成功概率，体现了随机算法的典型思路。虽然理论复杂度较高，但易于实现，且可通过优化（如 Karger-Stein 算法）提升效率，是理解随机图算法的重要范例。

xxx 无向图的最小割的 Karger 算法 问题描述 给定一个无向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个非负权重 \( w(e) \)（若未指定权重，可视为单位权重）。图的一个割（cut）是将顶点集 \( V \) 划分成两个非空子集 \( S \) 和 \( T = V \setminus S \) 的分割。割的容量（capacity）是连接 \( S \) 和 \( T \) 的所有边的权重之和，记作 \( c(S, T) = \sum_ {e \in E, e \text{ 连接 } S \text{ 与 } T} w(e) \)。最小割问题是找到容量最小的割。Karger 算法是一种随机算法，通过随机边收缩来求解最小割，能以高概率返回正确的最小割。 解题过程 核心思想 Karger 算法的基本思想是：随机选择一条边并将其“收缩”（contract），即将这条边的两个端点合并为一个超级顶点，并移除产生的自环（self-loop），但保留连接超级顶点与其他顶点的多条边（即允许重边）。重复收缩过程，直到图中只剩下两个超级顶点，此时剩下的边对应一个割。由于收缩是随机的，多次运行算法能提高得到最小割的概率。 算法步骤 初始化：复制原图 \( G \) 到临时图 \( G' \)，避免修改原图。 当 \( G' \) 中顶点数大于 2 时： a. 在 \( G' \) 中 随机均匀 选择一条边（权重不影响选择概率，可视为按边等概率选取）。 b. 收缩这条边：将边的两个端点 \( u \) 和 \( v \) 合并为一个新顶点 \( uv \)；删除连接 \( u \) 和 \( v \) 的所有边（自环）；将与 \( u \) 或 \( v \) 相连的边改为连接 \( uv \)，并保留重边。 结束时，\( G' \) 只剩下两个顶点，它们之间的边构成一个割，其权重和即为返回的割容量。 细节说明 边的选择：在无向图中，通常维护一个边列表，每次从列表中等概率随机选取一条边执行收缩。 收缩操作：实现时常用并查集（Union-Find）来跟踪顶点所属的超级顶点，但需注意处理重边——合并后，两个超级顶点之间的多条边可合并为一条边，其权重为原多条边权重之和。 返回结果：多次（如 \( O(n^2 \log n) \) 次）独立运行算法，取所有运行中得到的最小割值作为最终答案。 正确性分析 关键点：最小割的边数至少为 1。在收缩过程中，如果从未选中最小割中的边进行收缩，则最后得到的割就是原图的最小割（因为最小割的边始终保留）。 概率下界：设原图的最小割容量为 \( c \)，即最小割有 \( c \) 条边。原图的边数至少为 \( \frac{c n}{2} \)（因为每个顶点至少连出 \( c \) 条边到另一部分），所以随机选到最小割边的概率至多为 \( \frac{c}{|E|} \leq \frac{2}{n} \)。 一次运行得到最小割的概率：通过分析，概率至少为 \( \frac{2}{n(n-1)} \)，即 \( \Omega(1/n^2) \)。 提高概率：重复运行算法 \( T = n^2 \log n \) 次，则至少有一次得到最小割的概率为 \( 1 - (1 - \frac{2}{n^2})^{T} \approx 1 - e^{-2 \log n} = 1 - \frac{1}{n^2} \)，非常高。 时间复杂度 一次运行的时间复杂度为 \( O(n^2) \)，若用邻接矩阵或动态边列表实现收缩。 运行 \( O(n^2 \log n) \) 次，总时间复杂度为 \( O(n^4 \log n) \)，这看起来很高，但实际中通过优化（如 Karger-Stein 算法）可降到 \( O(n^2 \log^3 n) \)。 示例演示 考虑一个简单无向图：顶点集 \( \{A, B, C, D\} \)，边为 \( (A,B), (A,C), (A,D), (B,C), (B,D) \)，权重均为 1。最小割容量为 2（例如割 \( S = \{A\}, T = \{B,C,D\} \)，边为 \( (A,B), (A,C), (A,D) \) 容量 3；割 \( S = \{A,B\}, T = \{C,D\} \) 边为 \( (A,C), (A,D), (B,C), (B,D) \) 容量 4；实际最小割是 \( S = \{A,B,C\}, T = \{D\} \) 边为 \( (A,D), (B,D) \) 容量 2）。 随机运行 1：可能依次收缩边 \( (A,B) \)、然后 \( (AB,C) \)，最后剩下 \( (ABC) \) 和 \( D \)，割边为 \( (A,D) \) 和 \( (B,D) \)，容量 2，即得到最小割。 随机运行 2：若先收缩 \( (A,D) \)，可能丢失最小割边，最后得到更大容量的割。 总结 Karger 算法通过随机边收缩，以多项式时间、高概率求解无向图最小割。其核心在于重复运行以放大成功概率，体现了随机算法的典型思路。虽然理论复杂度较高，但易于实现，且可通过优化（如 Karger-Stein 算法）提升效率，是理解随机图算法的重要范例。