🍵高级算法—最大、最小、稀疏割

status
Published
type
Post
date
Sep 3, 2025
slug
aa-cut
summary
介绍了三类图割问题，最小割的 Karger 随机收缩算法及 FastCut 改进，最大割的贪心算法和去随机化分析，以及简要的稀疏割介绍。
tags
高级算法
category
课程笔记
icon
password

Min Cut, Max Cut, and Spectral Cut

🗒️
这篇笔记是南京大学 高级算法 (Fall 2025) 课程的 lecture note，此部分为 尹一通 老师讲授。尹老师负责的部分都配有非常详尽的课后笔记，对应的链接在这里。本文结合课后笔记、授课内容以及个人理解的基础上整理而成，欢迎访问 理论计算机科学组 的主页获取更多信息。
Min Cut, Max Cut, and Spectral CutGraph CutMin-Cut问题简介Karger’s Contraction AlgorithmKarger 算法的准确度分析概率法的推论Fast Min-CutFastCut 算法分析Max-Cut问题简介Greedy algorithm近似比（Approximation ratio）通过条件期望去随机化通过成对独立性进行去随机化Sparsest-Cut

Graph Cut

给定一个图 ， 是 的一个 bipartition，满足:
割 定义为 ，表示 和 中各有一个端点的交叉边集合:

Min-Cut

问题简介

最小割问题：把 二分到不相交的非空子集 和 ，使得 最小
多重图（multi-graph）：两个顶点 和 之间可能存在平行边，但是不存在自环
最小割的确定性算法（deterministic algorithm）：最大流最小割算法，该算法可以找到一个最小的 - 割，其中 。需要通过穷举法找到任意固定源点和所有可能的汇点的最小割，需要的时间为 最大流算法需要的时间。无权简单图具有边数近线性时间复杂度的最小割算法。

Karger’s Contraction Algorithm

Karger 算法是一个简单的求最小割的随机算法。
contraction operator Contraction(, ): 给定无向图 中的一条边 ，将顶点 和 收缩，是指：
  1. 将 和 合并为一个新的顶点（记为 ）
  1. 原来与 或 相连的所有边，现在都连接到
  1. 如果出现自环，则将其删除
  1. 如果出现多重边，则保留这些边
Karger 算法的伪代码：
使用适当的数据结构，Contract(, ) 可以在 时间实现。（邻接矩阵）
在算法中，恰好收缩 次，因此算法的时间复杂度为

Karger 算法的准确度分析

我们希望严格地从理论上计算，算法返回一个最小割的概率（）至少是多少？（概率下界）
为了计算这个问题，考虑一个更强的命题，也就是算法返回特定的一个最小割 的概率（）最少是多少？这个概率显然是上一个问题概率的下界。
引入以下符号： 表示 RandomContract 算法时选择收缩的随机边序列， 表示原始输入的图， 表示第 次收缩之后的图。
命题 1：收缩不会创造新的割（如果 是 的一个最小割，，那么 是收缩图 的最小割）。因此，可将 contract 理解为一个缩小解空间的过程。
下面分析原图中确定的一个最小割 的概率。根据命题 1， 被返回等价于选择的这 条边均不属于 ，即：
接下来计算 . 我们考虑最大的 最小割，计算出概率的一个下界：
命题 2：多重图 的最小割 满足 .
  • 证明：图上顶点平均度数为 , 根据平均原则，必然存在一个顶点的度数 . 因此 ( 是图中最小度数顶点的度数)。又因为和最小度数的顶点相连的边集必然是一个割，因此 , 从而 .
根据命题 2，有：
因此：
即：
这个概率很低，但这是一个指数级到多项式级的改进！因为 的非空子集是指数级的，这些子集都对应着一个割。只要独立运行该算法 次，并返回遇到的最小割集，那么算法找到最小割集的概率为：
因此，这是一个以高概率（with high probability）找到最小割的一个 算法.
w.h.p (with high probability):
a.a.s (asymptotically almost surely):

概率法的推论

Corollary: 对一个 个顶点的图 ， 中不同最小割的数量最多为 .
  • 证明：设 是 所有不同最小割的集合，设 ，随机算法返回 的事件为 ，概率为 。对任意 ， 和 是不相交事件（disjoint events），因此 就是随机算法返回最小割的概率 。由于概率的可加性，有：
      • 由于概率的幺正性（unitarity of probability），有：
      因此：
也就是说，随机算法返回最小割的概率实际上暗示了图上最小割的数量。这个不等式是紧的，当图是一个环时取最大值 .
这个推论本身的表述没有任何的“随机性”，但是其证明过程是一个随机化的过程，这就是一个典型的概率法（the probabilistic method）.

Fast Min-Cut

在分析 RandomContract 算法时，我们通过以下这个“伸缩乘积”（telescopic product）来限定算法返回最小割概率的下限：
伸缩乘积在数学中指的是有如下特点的连乘式：中间的大部分项会相互抵消，就像一根收缩自如的望远镜（telescope）一样，最终只剩下开头和结尾的少数几项。
这里的 指的是第 次收缩，观察到 随着 的增加而减少，这是一个比较符合直觉的结论。因为当图“过于收缩”时，割 的边占全部边的比例增加，因此更容易选到 中的边，导致将 淘汰。这样的观察启发我们改进算法：首先使用随机收缩将顶点数量减少到一个相对较小的值，然后在这个较小的实例中递归地寻找最小割。
以上这个改进算法的方法是 Lecture Notes 中说的，我认为这里 Fast-Cut 算法的精髓在于独立生成两个实例。对于确定性算法，这样做纯粹是浪费时间，但是对于随机算法，这样做的改进却是巨大的。

FastCut 算法分析

我们仍研究与给定最小割 相关的概率，但这次是 RandomContract 算法运行到 的情况：
设 表示 RandomContract(, ) 收缩的边都不是 中的边，为了让这个概率至少是 （其他值也可以）, 我们取 ，那么：
设 和 表示以下事件：
有 ，且 .
用 表示 FastCut 算法对于 个顶点的 multi-graph 成功的概率，这里的成功指的是 FastCut() 返回图中任意一个最小割，注意这里我们已经将研究对象从某个割转移为任意一个割。因此我们有：
然后，使用对立事件将概率转换为 . FastCut() 没有返回最小割（失败）是因为生成的两个子实例都没有返回最小割（请注意这里的措辞，我并没有说 FastCut() 失败的原因是 FastCut() 失败或 FastCut() 失败，是因为即使它们均成功，若生成子图 的过程中已经将原图的最小割淘汰，那么后续递归调用再怎么操作 FastCut() 也只能失败。这里的一个子实例表示生成子图过程+在子图上递归调用 FastCut 两个步骤，这两个子实例是相互独立的）
根据上面的分析，我们有：
以产生 的子实例为例，失败的原因有两种：一种是 RandomContract 的过程中淘汰了所有的最小割（），所以不管后续递归如何操作也不能返回 的最小割；另一种原因是虽然 RandomContract 没有改变原图最小割大小（），但是 FastCut() 没有返回最小割，因此有：
为了方便计算，再用一次对立事件，得到：
将上面的分析综合起来，我们得到（第一步在 Lecture Notes 中写的是 ，我认为应该是 ）：
根据数学归纳法，得：
时间复杂度：由递推式 , 得 .
也就是说，FastCut 算法在 的时间内以概率 返回最小割。这个算法并没有比 RandomContract 快，但是将概率从 提高到了 .
独立重复运行 FastCut 次，就可以在 的时间内以概率 返回最小割，即 w.h.p.

Max-Cut

问题简介

最大割问题和最小割问题类似，它是一个典型的约束满足问题（CSP）的优化版本，即 MAX-CSP。
CSP 指的是这样一类问题：
  • 一组从有限域中取值的变量：
  • 一组定义在变量上的谓词（约束）：
MAX-CSP 要求找到变量 的赋值，使得满足的约束数量最多。
我们将变量的取值范围限制在 （表示割所对应的 ），仅定义一系列不等约束 ，若 和 在图上有边则定义一个约束 . 在此定义下的 MAX-CSP 问题就是最大割问题。
最大割问题是一个 NP-hard 问题，因此我们允许算法找到次优解。但我们仍然希望算法在所有可能的实例上返回一个相对较好的答案，这一点使用近似比来严格定义。

Greedy algorithm

为了描述算法，重新定义 : 对于任意两个不相交的子集 , 定义 .
由于无法保证算法返回的解与最优解的近似程度，因此该算法只是一种启发式算法，而不是近似算法。

近似比（Approximation ratio）

设 为图 最大割的大小， 为算法返回的最大割的大小。定义 GreedyMaxCut 算法的近似比为 ，或者说对某些 $ 0< $, GreedyMaxCut 是一个 近似算法，当且仅当对所有的 都有 . 这个比值是算法的最坏情况，因为 的取值必须对所有的 成立.
我们在分析 GreedyMaxCut 的近似比时，不与最优解相比较（因为最优解是 NP-Hard），而是与最优解的上界进行比较（在这里是 ），因此有：
设 为初始图， 和 分别代表第 个顶点加入 或 后的集合。因此，最大割为：
命题 1: 可以通过 的贡献来表示图上边的数量
  • 证明：考虑输入的顶点顺序 ， 指向所有 () 的边 的和就是整个图上的边
命题 2: 可以分解为各个 的贡献
  • 证明：由贪心算法的运行过程可得
根据命题 1, 2 有：
  • 其中第二步用到了平均原则
因此，GreedyMaxCut 是一个针对最大割的 近似算法（贪心算法的近似比为 ）

通过条件期望去随机化

这是贪心算法的一个概率解释，这是另一种审视贪心算法的视角，这也解释了贪心算法的 intuition.
设 是一个均匀独立的随机 bit，指示了 在 或 中。那么割的大小可以表示为：
  • 其中 是一个指示变量，指示事件 是否发生。 的一个很好的性质是 .
对每一条边，有 的概率不在割里面（ 在同一集合），同时有 的概率在割里面，因此得根据期望的线性（linearity of expectation），有：
是最大割 的一个平凡上界，因此有如下结论：
定理：对 的一个均匀随机的割
根据平均原则，必然存在一个 bipartition , 使得割集的大小至少为 , 接下来就要找到这样一个 bipartition.
将顶点固定为任意顺序 , 我们逐个固定 的值，从第一个 开始，根全总期望定理：
根据平均原则，.
因此，我们将每一步选择的 视为一条“单调路径”，这里的单调体现在：
这里每选择一个 , 就是对整个的期望进行了一步“去随机化”，而且每一步去随机化得到的期望是单调增加的。这个过程可以用下面的图展示：
notion image
将这个构建单调路径的过程总结为以下算法：
可以验证，MonotonePath 在每一步 的选择必然和 GreedyMaxCut 算法中所选的 相同.
最大割的贪婪算法实际上是由于平均情况的去随机化.

通过成对独立性进行去随机化

重要观察：在条件期望的计算中，结果为 的决定性因素是一条边在割中的概率为 1/2，而不是解空间的大小，能不能缩小解空间 ？
答：通过成对独立性.
对每个顶点 使用随机变量 表示 与 或 连接，根据期望的线性：
为了使得 , 需要使得 , 这只要求 是均匀分布且成对独立，而不是相互独立。
接下来通过 个相互独立的随机 bits 构造 个成对独立的随机 bits :
notion image
我们称 是均匀且两两独立的（uniform and pairwise independent），即：
  1. 均匀：对任意 和 , 都有 .
  1. 两两独立：对任意 满足 和任意 , 都有 .
      • 解释：每个 是若干独立变量 的模 2 和，因此其分布仍为均匀的 01 分布。下证对任意两个不同的子集 , 对应的 是独立的，即证：
          • 我们已知 是均匀分布，因此 . 现设 , , . 现在 三个集合没有重叠的元素，因此 集合的模 2 和是均匀独立的。将所有可能的结果列出：
          A
          B
          C
          a
          b
          0
          0
          0
          0
          0
          0
          0
          1
          0
          1
          0
          1
          0
          1
          1
          0
          1
          1
          1
          0
          1
          0
          0
          1
          0
          1
          0
          1
          1
          1
          1
          1
          0
          0
          1
          1
          1
          1
          0
          0
          因此：
通过上面这种产生两两独立的变量的方法，我们将解空间从 缩小至 , 这便是下面的算法：
notion image
  • 注：这里 实际上指的是 的二进制中第 位是 ，对向量 中下标为 的元素异或，就相当于使用 产生所有 的子集.
  • 时间复杂度: . 外循环 次内循环 次，产生 的一个子集的代价为 .

Sparsest-Cut

谱图理论：图的“谱”（）与“组合性质”（）紧密相关。 接近 意味着图有瓶颈。
应用：图像分割（使用“最稀疏割”选出内部相似性高且边界差异大的分割）
 
Loading...

© Qiyue Zhang 2026