Karger 最小割算法

Karger 最小割算法(Karger's Algorithm)是一种基于随机边收缩的蒙特卡洛算法,用于求无向图的全局最小割,由美国计算机科学家大卫·卡格(David Karger)于 1993 年在斯坦福大学读博期间提出。它以简洁的随机化思想取代复杂的最大流计算,成为随机化算法领域最著名的例子之一。

概述

全局最小割问题要求把图的顶点分成两个非空集合,使跨越两侧的边数(或权重)最小,反映了网络最脆弱的断裂处。传统做法是固定一个源点,对其余每个顶点求一次最小 s-t 割,需要多次最大流计算。Karger 的洞察是:随机收缩一条边时,只要它不属于最小割,最小割就被完整保留;而最小割的边只占少数,因此随机收缩有相当的概率一路避开它们。

核心原理

• 收缩操作:随机等概率选一条边,把两个端点合并成一个超级顶点,删除自环、保留重边。
• 反复收缩:直到只剩两个超级顶点,剩余边即给出一个割。
• 成功概率:单次运行恰好得到某个最小割的概率至少为 2/(n(n-1)),重复约 n² ln n 次并取最小值,失败概率可降到 1/n 以下。

1996 年卡格与克利福德·斯坦(Clifford Stein)提出改进的 Karger-Stein 算法:收缩到约 n/√2 个顶点后分成两支递归,把总复杂度降到 O(n² log³ n),显著优于朴素重复。

应用场景

最小割用于评估网络可靠性(找出通信网或电网最薄弱的切断方式)、图像分割、社区发现中的图划分,以及编译与并行计算中的任务切分。Karger 算法本身还常被用作讲授随机化算法与概率分析的入门案例。

常见问题

问:它是蒙特卡洛算法还是拉斯维加斯算法？答:蒙特卡洛算法,运行时间确定但结果可能不是最优,只能以高概率正确;无法便宜地验证所得割是否真的最小。

问:单次运行成功率那么低,算法还有意义吗？答:有,失败概率随独立重复次数指数下降,总代价仍是多项式;这种“廉价试验多次重复”正是随机化算法的典型威力。

问:它支持带权图吗？答:支持,按边权比例随机选边收缩即可,概率分析同样成立。