COMP5270 Week 5 总结：Graph Algorithms（题解 + 知识点）

Posted on 2026-06-02 Edited on 2026-06-14 In Course Notes , COMP5270 Word count in article: 9.6k Reading time ≈ 35 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms 学期: S1 2026 来源: Week 5 - Graph algorithms, Week 5 - Tutorial 5 (Solutions)

这周到底在学什么？（先看这里）

Week 5 的关键词是 随机化图算法。这周不只是在学 Karger 算法的步骤，而是在训练一种分析思维：

随机做一个看似危险的操作（随机选边、收缩），然后证明它破坏最优解的概率不大。概率不大 → 重复几次就能成功。

这周有两条主线：

Minimum Cut（最小割）：用随机 contraction（收缩边）来找图里最小的 cut。
Minimum Spanning Tree（最小生成树，MST）：用随机采样 + cut/cycle property 来删除不可能属于 MST 的边，做到期望线性时间。

别被名词吓到。下面把每个概念都用大白话解释清楚。

先统一语言：图论基础词汇

图记作。是顶点（点）的集合，是边（连线）的集合。
（有多少个点），（有多少条边）。
cut（割）：把顶点分成两组，比如。"把一群人分成两队"就是 cut。
crossing edge（跨割边）：一端在左边组、一端在右边组的边。
cut 的大小：crossing edges 的数量。加权图里是 crossing edges 的权重和。
min-cut（最小割）：大小最小的 cut。记最小割的值为。

举个例子：5 个朋友要分成两个微信群。如果 Alice 和 Bob 关系特别好，把他们放不同群就是"一条 crossing edge"。如果你能找到一种分法，让跨群的好友对数最少，这就是 min-cut。

Karger contraction 的核心直觉：把点"捏"到一起

想象你有一张图。Karger 的做法很简单：

反复随机挑一条边，把这条边两端的点合并成一个"大点"（supervertex）。

如果挑到的边两端本来就在同一组（比如都在 min-cut 的左边），捏合它们没事，min-cut 还活着。
如果挑到的边横跨了 min-cut（一端在左、一端在右），那就糟了 —— min-cut 被破坏。

关键转化：只要从头到尾没挑到 min-cut 的 crossing edge，最后剩下的两个 supervertices 就正好对应 min-cut 的左右两组。

这就是 Karger 的全部直觉。后面的分析只是在算：每一步不挑到 min-cut 边的概率有多大。

Part 1: Tutorial 5 详细题解

Tutorial 开头的难度/要求说明

Tutorial 5 开头说明了每题的投入要求，并解释了星号含义：标记的题在所属级别内偏难；标记的题非常难或很耗时。

题目	所属部分	Tutorial 原文难度/要求	复习时怎么安排
Problem 1	Warm-up	lecture 前也应该可以尝试并解决	先做，练 cut 的定义和计数
Problem 2	Warm-up	Karger-Stein 的概率递推部分 difficult；主要是读 lecture proof 并检查自己是否理解，不要求自己凭空想出	时间递推要会推；概率递推重点看懂结构
Problem 3	Warm-up	需要读 lecture notes 或看 lecture	理解为什么 Karger-Stein 选择 2 个递归分支，以及改成 1/3 个分支会怎样
Problem 4	Problem Solving	lecture 前也应该可以尝试并解决	必做，练如何在时间内 uniform sample 一条边
Problem 5	Problem Solving	标记；接近课上算法和分析，但需要几个 non-trivial ideas；值得 tutorial 前尝试，不用因为独立做不出而沮丧	难题，练把 Karger 的证明改到 -cut
Problem 6	Problem Solving	标记；“fun” 且 conceptually interesting，但在 difficult side	概念题，重点看 MST/Kruskal 与 contraction 的关系
Problem 7	Advanced	不一定 hard，但需要深入检查课上算法证明，看看加权情形要改哪里；good practice	练把“边数”推广成“权重”

Warm-up

Problem 1: 一个图有多少个不同的 cut？

Tutorial 难度/要求: Warm-up；lecture 前也应该可以尝试并解决。重点是把 cut 看成顶点集合的二分，并处理与是同一个 cut。

题目：个顶点的无向图恰好有多少个不同的 cut？（不要求是 minimum cut，随便什么 cut 都算。）

先理解 cut 到底是什么：

一个 cut 就是把个顶点分成两组。比如，分成和就是一个 cut。

注意：cut 没有方向。把顶点分成和，跟分成和是同一个 cut —— 你不关心哪组叫 A 哪组叫 B。

解题思路：

你想把个顶点分成非空的两组。先考虑怎么选左边那组。

从个顶点中选任意子集当左边组，有种选法（每个顶点可以"在左边"或"不在左边"）。

但有两个选法不合法：

左边组是空集：那右边就是全集，不是"分成两组"。
左边组是全集：那右边就是空集，也不是"分成两组"。

所以合法的子集数是：

但 cut 没有方向。和是同一个 cut，每个 cut 被数了两次。所以要除以 2：

结论：

验证一下：时，应该有个 cut。三个顶点，可以分成： - vs - vs - vs

确实 3 个。✓

本题学到的：

cut = 顶点集的一个二分。
计数时注意：和是同一个 cut。
要去掉空集和全集，再除以 2。

Problem 2: Karger-Stein 的运行时间和成功概率递推

Tutorial 难度/要求: Warm-up；概率递推部分 difficult，官方主要要求你读懂 lecture proof 并确认自己理解，不要求自己凭空想出来。时间递推要尽量会自己展开。

题目：推导 Karger-Stein 算法的时间递推和成功概率递推。

先回忆：Karger-Stein 和 basic Karger 有什么区别？

Basic Karger 一路 contract 到只剩 2 个点。问题在于：最后几步（点很少时）选中 min-cut 边的概率很高。比如只剩 3 个点时，选中坏边的概率高达 2/3。

Karger-Stein 的改进：不要一路 contract 到底。先 contract 到大约个点（此时 min-cut 还有大约 50% 概率存活），然后停下来。停下来之后，复制成两个独立的子问题，分别递归。

为什么选这个数？因为从个点 contract 到个点，min-cut 存活概率约等于。如果取，存活概率约，正好是常数。

运行时间递推

每一层做两次 ModifiedKarger（每次 contraction 到），每次成本。然后递归到两个规模约的子问题：

展开看（设常数部分为）：

再展开一层：

规律：第层有个子问题，但该层总工作量仍是。因为子问题规模缩小了倍，工作量。

递归深度是，每层，所以：

直观理解：虽然子问题越来越多，但每个子问题也越来越小，各层总工作量不变。

成功概率递推

设是 Karger-Stein 在个点上成功返回某个固定 min-cut 的概率。

从个点 contract 到约个点，min-cut 存活概率至少。然后递归调用成功的概率是。

单个分支成功的概率至少：

两个分支独立运行。算法失败当且仅当两个分支都失败：

讲义证明这个递推的解是：

这比 basic Karger 好多少？

算法	单次成功率	重复多少次才能高概率成功
Basic Karger		次
Karger-Stein		次

差距巨大！比如时，basic Karger 成功概率约 1/10000，Karger-Stein 约 1/5。

本题学到的：

Karger-Stein 停在规模后分两支递归。
时间递推中，每层总工作量不变（子问题变多但每个变小）。
成功概率递推用"两个分支都失败"的补事件来分析。
概率递推看懂结构即可，考试不要求从零推导。

Problem 3: 改递归分支数会怎样？

Tutorial 难度/要求: Warm-up；需要读 lecture notes 或看 lecture。重点是理解 Karger-Stein 为什么用 2 个递归分支，以及改成 1 个或 3 个分支时运行时间和成功概率如何变化。

题目：如果 Karger-Stein 每层只做 1 次递归（不是 2 次），或者做 3 次递归，会发生什么？

这道题在训练你看懂 递归分支数 ↔︎ 运行时间 ↔︎ 成功概率 三者之间的 trade-off。

只做 1 次递归

那就退化成了"basic Karger，只是每 contract 一段检查一次"。没有利用"两条独立路径降低失败概率"的结构。

成功概率：每层乘约，递归深度，整体成功概率会非常小 —— 比 basic Karger 好不到哪去。

运行时间：，展开后只有一层在干活，总时间。运行时间确实更低了，但成功概率很差，需要重复很多次来弥补。

结论：分支数太少 → 成功概率低 → 需要大量重复 → 得不偿失。

做 3 次递归

时间递推变成：

展开看：

第层有个子问题，每个子问题规模。该层总成本：

深度，总和是一个等比数列：

（因为。）

，所以运行时间约，比好不少！

成功概率：三个分支全失败才失败，所以成功概率比 2 分支更高。

trade-off 总结：

分支数	时间	成功概率
1		很差
2		✓
3		更好

所以 2 分支是一个不错的平衡点。为什么不用 3 分支？因为 2 分支的时间已经够好（），3 分支虽然渐进更快但实现更复杂，而且要选合适的阈值（的常数需要调整）。

本题学到的：

分支数直接影响中的。
用层级展开分析。
多分支随机算法用"全部失败"的补事件分析成功概率。

Problem Solving

Problem 4: 在时间内均匀随机采样一条边

Tutorial 难度/要求: Problem Solving；lecture 前也应该可以尝试并解决。重点是先按 degree 采样顶点，再从该顶点的邻边里均匀采样，从而保证每条边概率相同。

题目：给定一个 multigraph ，不管是 adjacency matrix 还是 adjacency list 表示，如何在时间内均匀随机选一条边？

为什么不能直接"随机选两个点"？

如果你均匀随机选两个顶点，然后看它们之间有没有边——这样选到 degree 高的顶点的边的概率会偏大。比如一个点有 100 条边，另一个点只有 1 条边，前者的边显然更容易被选中。

目标是：每条边被选中的概率完全相等，都是 。

方法：按 degree 加权采样顶点

设顶点的 degree 为（即有多少条邻边）。

第一步：按概率采样一个顶点。

也就是说，degree 高的顶点更容易被选中。这合理，因为 degree 高的顶点"拥有"更多条边。

第二步：在的邻接边中均匀选一条，概率。

为什么这样每条边概率相等？

考虑任意一条边。它可以通过两个端点被选中：

通过端点：概率 =
通过端点：概率 =

根据 handshaking lemma（握手引理），所有顶点的 degree 之和等于：

所以每条边被选中的概率是：

完美！每条边概率相等。

时间复杂度：

扫描所有顶点计算 degree 和前缀和：
根据采样位置找到对应顶点：
在邻接表中找对应边：

总共。

adjacency matrix 的 rejection sampling 版本

如果图是连通的，则。在 adjacency matrix 中均匀随机选一个坐标。如果那条边存在，返回；如果不存在，重试。

一次命中的概率约，期望尝试次数。因为连通图，所以。

总期望时间：。

本题学到的：

按 degree 加权采样，然后用抵消。
Handshaking lemma：。
Rejection sampling 的期望时间 = 命中概率的倒数。

Problem 5: k-Min-Cut（Karger 推广到 k 组）

Tutorial 难度/要求: Problem Solving，标记；接近课上 Karger 算法和分析，但需要几个 non-trivial ideas。值得 tutorial 前尝试，做不出也正常，关键是看清证明哪里要改。

题目：把 min-cut 推广到组。-min-cut 要把分成个非空部分，让跨 component 的边数最少。

直觉：basic Karger 是 contract 到 2 个 supervertices。-min-cut 就是 contract 到个 supervertices。

这里把当作常数（如果不是常数，运行时间会变成，不是 polynomial）。

a) 算法

随机 contract 边，直到剩下个顶点；
在个顶点上 brute force 枚举所有可能的 -partition；
返回其中 cut value 最小的那个。

为什么停在而不是？因为最后几步杀掉 min-cut 的概率太高，不如提前停下用 brute force。

由于是常数，个点上的 brute force 也是常数时间。

b) 成功概率分析

设固定的 optimal -cut 是，大小为。

算法成功的条件仍然是：contract 过程中从没选到的跨部分边。

在某一步，当前有个 supervertices。Solution 的核心下界是：

这个下界从哪来？ 把当前顶点分成若干组，每组最多个。如果某组的 total degree 小于，那把整组切出来就得到一个比更小的 -cut，与是 min -cut 矛盾。所以每组的 degree 至少。

于是选到坏边的概率：

从个点缩到个点，存活概率乘起来：

重复次，取最小 cut，失败概率降到。

每次 contraction 到成本，总时间大致。

c) -min-cuts 的数量上界

如果一个固定的 optimal -cut 被单次算法输出的概率至少，而不同 optimal -cuts 的输出事件互斥，总概率不超过 1。所以：

$最多个$

更精细的分析：可以用对角线排列法（tutorial solution 里那个行列的表），得到存活概率约，所以 -min-cuts 最多个。但对本题来说就够了。

本题学到的：

Karger contraction 的核心条件：不 contract 目标 cut 的边。
用 min-cut 性质推出 degree/edge 数下界。
概率乘法链：每一步条件存活概率相乘。
由算法输出概率推结构性定理（min-cuts 数量上界）。

Problem 6: 随机权重 MST 算法 = Karger？

Tutorial 难度/要求: Problem Solving，标记；官方说它 “fun” 且 conceptually interesting，但属于 difficult side。重点是理解随机 contraction 和 MST/Kruskal 过程之间的关系。

题目：给每条边独立赋一个均匀随机权重，求 MST，删去 MST 中最重边，返回剩下两个 component 对应的 cut。证明这和 basic Karger 等价，并给出实现。

这道题很漂亮，它在揭示：MST 算法和 contraction 算法本质上在做同一件事。

为什么随机权重等价于随机边序？

每条边独立地从中均匀取值。因为是连续分布，几乎不可能有两条边权重相同。

按权重从小到大排序，就等价于对所有边做一个种可能中的 uniformly random permutation（均匀随机排列）。

Kruskal 在干什么？

Kruskal 算法按权重从小到大扫描每条边：

如果这条边连接两个不同的 component（当前不在同一棵树里），就加入 MST。
如果连接同一个 component（会形成 cycle），就跳过。

这和 contraction 一模一样！

加入一条边 → 两个 component 合并成一个 → 这就是 contraction！
跳过的边 → 两个端点已经在一个 component 里 → 这就是 contraction 后的 self-loop，不处理。

而且关键是：剩余未被处理的边的相对顺序仍然是 uniformly random。所以每一步等价于"在当前 multigraph 中均匀随机选一条边并 contract"。

为什么删去 MST 最大边就得到 cut？

Kruskal 最终选出条边（一棵 spanning tree）。

Basic Karger contract 到只剩 2 个 supervertices 时，做了次有效 contraction。

Kruskal 多做了一次：把最后两个 component 也合并成了一棵树。所以 MST 中最后加入的那条边，就是把最后两个 component 连起来的那条边。

删去 MST 的最大权重边（也就是最后加入的边），就把图恢复成两个 component —— 正是 Karger 的输出！

时间复杂度

给每条边生成随机权重：
按权重排序：
Kruskal + union-find：，被排序主导

总时间：

本题学到的：

连续独立随机权重 → uniformly random ordering。
Kruskal 的 component merge = contraction。
MST 去掉最大边 = 两个 component。
Kruskal 复杂度由排序主导。

Advanced

Problem 7: 加权图上的 Karger / Karger-Stein

Tutorial 难度/要求: Advanced；不一定 hard，但需要深入回到课上算法证明，逐步检查加权图情形中哪些地方要把“边数”替换成“权重”。这是 good practice。

题目：证明 Karger 和 Karger-Stein 可以修改为处理带非负权重的无向图。

核心思想：把"均匀随机选边"改成"按权重比例选边"。

加权版 contraction

在当前图中，选边的概率不再是均匀的，而是：

权重大的边更容易被选中，这很自然。

选到后，把这条边 contract（合并两端点，保留 parallel edges，删 self-loops）。

分析为什么会成立

设某个固定的 minimum weighted cut 是，权重为。

危险边就是中的 crossing edges，它们被选中的总概率为：

现在需要证明：当前图的总权重和至少是。

为什么？ 因为是 minimum cut weight，所以任意单个顶点的 weighted degree 至少是（否则把这个顶点单独切出来就是一个比更小的 cut）。

全部顶点的 weighted degree 之和至少是。每条边被两个端点各算一次，所以：

因此：

$选到坏边$

这和非加权 Karger 的关键不等式完全一样！后续的乘法链、Karger-Stein 的递推全部照搬。

总结：Karger/Karger-Stein 的分析只依赖"每一步选到坏边的概率 "，加权版也能证明这一点。所以加权图直接成立。

本题学到的：

加权版按采样边。
用 min weighted cut 推出所有 weighted degree 。
Karger 分析的本质只需要"每步坏概率上界"，不关心均匀还是加权。

Part 2: Week 5 讲义知识点详解

1. Min-Cut 是什么？为什么要随机化？

![[Pasted image 20260611214546.png]]

问题：给定一张连通无向图，找到把图"切开"需要的最少边数。

这个"切开"就是 cut：把顶点分成两组，数跨组的边有多少条。

确定性算法能做吗？ 能。计算次 Max-Flow 就行，。

那为什么还要学 Karger？因为 Karger 的 contraction 算法：

极简单：只做一件事 —— 随机挑边、合并两端。
极快：单次。
可分析：成功概率不是指数小，而是多项式小。

这体现了随机化算法的核心理念：用一个很简单的随机过程，以可接受的概率得到正确答案。

2. Contraction 是怎么回事？

Contraction（收缩）一条边 ：

把和合并成一个新点（叫 supervertex）；
原来连到或的边，现在都连到这个新点；
删掉 self-loops（新点连回自己的边，不跨任何 cut）；
保留 parallel edges（两个 supervertices 之间可能有多条边，必须全保留）。

为什么必须保留 parallel edges？因为你需要准确数 crossing edges 的数量。如果合并成一条，cut value 就算错了。

Contraction 后得到一个 multigraph： - 允许两个顶点之间有多条边（parallel edges）。 - 不允许 self-loops。

为什么 contraction 最后一定会给出一个 cut？

每次 contraction 都是在把原始顶点分组。比如原图顶点是： - 先 contract → supervertex - 再 contract → supervertex - ……

最后只剩两个 supervertices 时，这两个集合就自然构成了原图顶点集的一个二分 —— 也就是一个 cut。

最后两个 supervertices 之间有多少条 parallel edges，就是原图中跨 cut 有多少条边。

3. Basic Karger 算法

while |V| > 2:
    从当前所有边中均匀随机选一条 e
    G ← G/e  (contract e)
return 最后两个 supervertices 定义的 cut

为什么要"均匀随机选边"而不是"随机选两个点"？

因为分析依赖 cut 的边数。min-cut 的 crossing edges 最少 → 选中它的概率最小 → 它最难被破坏。

如果随机选两个点，就跟 cut 的边数没关系了。两个点之间可能根本无边，完全不反映 cut 的大小。

单次运行时间：次 contraction，每次，总共。

4. 成功概率分析（最重要的部分）

分析的核心技巧：

不要问"算法最后输出什么"。而是固定一个真正的 min-cut ，问" 活到最后的概率有多大"。

为什么活着 = 算法输出？

设是某个固定的 min-cut。

如果算法从头到尾都没 contract 过的 crossing edge，那么： - 所有 contraction 只发生在内部或内部。 - 和的顶点永远不会混到同一个 supervertex。 - 最后只剩两个 supervertices → 它们只能是和。

所以：

$输出整个过程中没的边$

每步安全概率

假设当前还剩个 supervertices，还活着。

因为仍然是大小为的 cut，当前图不可能有更小的 cut。

关键推论：每个 supervertex 的 degree 至少是 。为什么？如果某个 supervertex 的 degree 小于，把它单独切出来就是一个比更小的 cut，矛盾。

所有个 supervertices 的 degree 之和至少是。每条边贡献 2 个 degree（一端一个），所以：

危险边只有中的条 crossing edges。

所以这一轮选到危险边的概率最多：

安全概率至少：

全部步骤乘起来

从个点缩到 2 个点，经过：

这是一个 telescoping product（望远镜乘积），中间所有项都消掉了：

这个概率不大，但不是指数小！ 对于，约 1/5000。

重复放大

单次成功概率，独立重复次，全失败的概率：

如果希望失败概率最多，取：

总运行时间：

5. Karger-Stein：为什么不要一路 contract 到底？

Basic Karger 的问题在哪？

看每步选中坏边的概率上界：

当前点数	选到坏边的概率上限
	2%
	4%
	20%
	67%

前期很安全，后期非常危险！Basic Karger 把所有步骤平等对待，其实很不公平。

Karger-Stein 的想法：

前期 contraction 便宜且安全，后期 contraction 危险。那就只做前期！做到一定程度后，分两条路递归。

为什么停在？

从收缩到，min-cut 存活概率约：

取，存活概率约 —— 常数级别。

然后复制成两个独立分支。每个分支有约 1/2 概率保留了 min-cut。两个分支只要有一个成功，整体就成功。

和 basic Karger 的区别可视化：

Basic Karger:    n ──────────────────────────→ 2   (一路到底)

Karger-Stein:    n ───→ n/√2 ─┬─→ ··· ─→ 2   (先到中间，分两支)
                               └─→ ··· ─→ 2

运行时间：

成功概率：

重复次，达到高概率成功，总时间。

6. Minimum Cuts 的数量上界

Karger 的分析不仅可以用来设计算法，还能推出图的结构性质。

一个图最多有多少个不同的 min-cuts？

所有 cuts 的数量是，指数级。

但 min-cuts 的数量最多只有 ，二次级。

证明：如果有个不同的 min-cuts，每个被 Karger 输出的概率至少。这些事件互斥（一次运行只能输出一个 cut），所以：

这个界是紧的：cycle graph （一个圈）恰好有个 min-cuts。在一个圈上，min-cut 大小是 2（必须切断两条边才能分开）。任选两条边切断，就有种选法。

7. MST 部分：先掌握两个 property

接下来进入 Week 5 的第二条主线：Minimum Spanning Tree（MST）。

MST 是什么：在连通加权图中，选条边把所有顶点连起来，让总权重最小。

两个最重要的性质，做题时必须会用： ![[Pasted image 20260611214404.png]] #### Cut Property（割性质）

对任意 cut，跨过这个 cut 的最轻边一定可以出现在某棵 MST 中。

直觉：假设你把顶点分成两边。任何 spanning tree 都必须用至少一条边跨过这个 cut。如果跨 cut 的最轻边是，而某棵 MST 没选它，那这棵树一定选了另一条更重的跨 cut 边。把那条重边换成，树仍然连通且总权重更小 → 矛盾。所以必须能被选中。

用途：证明某条边"安全可选"。Boruvka 算法就是反复用 cut property。

Cycle Property（环性质）

任意 cycle 中最重的边一定不在 MST 中。

直觉：在一个环里，最重边是"多余"的。删掉它，环上其他边仍然能让两端连通。如果某棵 MST 包含了这条最重边，删掉它树会断成两部分。环上一定还有另一条边跨过这两部分，而且更轻 → 替换后更优 → 矛盾。

用途：证明某条边"安全可删"。Kruskal 算法跳过的边就是用 cycle property 排除的。

8. F-heavy Edge：哪些边一定不在 MST 里？

给定一个 forest（还没连成树的森林）。

把一条不在中的边加入，会形成一个 cycle。如果是这个 cycle 上最重的边，就叫是 -heavy。

根据 cycle property：-heavy 的边不可能在原图 MST 中。

所以可以安全删除所有 -heavy edges。

为什么要搞这个概念？

如果我们已经知道真正的 MST ，那不在中的边都可以评估：加入后形成 cycle，如果比 cycle 上其他边都重就能删。

但问题是：正是我们要找的东西！

KKT 的做法：先用一个随机抽样的子图求出一个 forest ，然后拿当"参考答案"。相对是 heavy 的边，在原图 MST 中也一定是 heavy → 可以安全删除。

9. KKT MST 的三个组件

KKT（Karger-Klein-Tarjan）算法的目标是：期望时间求 MST。

它用三个工具：

① MSTVerification（MST 验证器）

给定和 forest ，在时间内找出所有 -heavy edges。

这是确定性黑盒。你给它一个 forest 当参考，它告诉你相对于哪些边太重、可以删。

② Random Subsampling Lemma（随机采样引理）

从中每条边以概率独立保留，得到子图。令为的 MSF（最小生成森林）。则原图中不是 -heavy 的边，期望数量最多 。

翻译成大白话：虽然只是在抽样子图上求的，不一定是原图 MST，但足够好 —— 原图里大部分边相对于都是 heavy，可以删。不能删的边期望很少（条）。

比如取，不能删的边期望只有条。原图可能有条边，一下子就删掉了绝大部分！

③ Boruvka Steps（Boruvka 缩点）

运行轮 Boruvka，每轮每个 component 选自己的最轻出边并 contract。轮后顶点数至少缩小倍。

Boruvka 利用 cut property：每个 component 选最轻出边，这些边一定在 MST 中，可以安全地 contract。

运行轮 Boruvka 成本，顶点数从降到。

10. KKT 算法流程

一次递归调用做这几步：

Step 1: Boruvka 缩点 - 运行轮 Boruvka，把图缩小。 - 缩掉的边是安全的，一定属于 MST。

Step 2: 随机采样 - 每条边以概率保留，得到更小的随机子图。 - 比如，的边数期望只有原来一半。

Step 3: 递归求 MSF - 在上递归求 MSF，得到 forest 。 - 虽然不是原图 MST，但根据采样引理，它是个不错的"参考答案"。

Step 4: 删 heavy edges - 用 MSTVerification 在原图中找所有 -heavy edges。 - 删掉这些边，得到。 - 这些边由 cycle property 保证不在 MST 中，删了不碍事。

Step 5: 递归求解 - 在上递归求 MSF，得到。

最终输出：（Boruvka 缩掉的边 + 剩余问题的 MSF）。

为什么期望线性？

运行时间递推的直觉： - 非递归部分（Boruvka + 验证）是。 - 第一个递归：边数期望。 - 第二个递归：边数期望（采样引理）。 - Boruvka 把顶点数缩小了倍。

选，，可以证明：

（连通图中，所以。）

这是 Las Vegas 算法：随机性只影响运行时间，不影响正确性。输出的一定是正确 MST。

11. 讲义定理速查

编号	类型	内容
Fact 25.1	Fact	Min-Cut 可用次 Max-Flow 解决
Def 25.1	Def	Edge contraction
Thm 26	Thm	Basic Karger 成功率
Thm 27	Thm	Best-of- Karger 高概率版
Thm 28	Thm	Karger-Stein 时间，成功率
Cor 28.1	Cor	Best-of- Karger-Stein
Thm 29	Thm	最多个 min-cuts
Def 29.1	Def	-heavy edge
Fact 29.1	Fact	MSTVerification
Lemma 29.1	Lemma	Random Subsampling Lemma
Lemma 29.2	Lemma	-step Boruvka 缩点
Thm 30	Thm	KKT MST expected

12. 本周证明套路总结

Week 5 的证明看起来多，但反复用同样的套路：

场景	证明套路
Karger 保留某个 min-cut	固定一个最优 cut，证明每一步不破坏它
每步不破坏概率	用 min degree 推出总边数下界
重复放大	用
min-cuts 数量上界	每个 min-cut 被输出概率下界 × 数量 ≤ 1
MST 必选边	用 cut property（跨切边最轻者必选）
MST 可删边	用 cycle property（环中最重者可删）
KKT 删大量边	随机采样得参考 forest → 删 -heavy edges

做题卡住时的自查清单：

这是 Min-Cut 题还是 MST 题？
Min-Cut 题：是不是要固定一个 cut，分析它是否存活？
MST 题：是在问"这条边一定能选"（cut property）还是"一定不能选"（cycle property）？
要证明高概率 → 重复独立运行 + 。

本周核心记忆卡

主题	关键结论	怎么理解
cut 数量	所有 cut 有个	选一边顶点子集，去空集/全集，除以 2
contraction	合并边两端，保留 parallel edges	supervertex = 一组原始顶点
Basic Karger	，成功率	不 contract min-cut 的边就能输出它
每步安全概率	点时坏概率	min degree → 总边数
放大 Karger	高概率	独立重复取最小 cut
Karger-Stein	，成功率	先到，再分两支递归
min-cuts 数量	最多个	每个被输出概率，总概率
weighted Karger	按边权比例采样	"边数"换成"权重和"即可
cut property	cut 最轻边必在 MST	不选它就能用更轻的替换跨边
cycle property	cycle 最重边必不在 MST	删它仍连通，有更轻替代
-heavy edge	相对 forest 成环且最重	cycle property 直接应用，安全可删
KKT MST	expected	Boruvka 缩点 + 随机采样 + 删 heavy edges

Week 5 一句话总结：Karger 告诉你随机 contraction 能以多项式概率找到 min-cut；Karger-Stein 告诉你聪明地递归可以把成功率从提升到；KKT 告诉你用随机采样 + cycle property 可以在期望线性时间内求 MST。三条线都在用随机化把"看起来危险的操作"变成"以可控概率成功的算法"。

Part 3: Week 5 Quiz 回顾

来源：Canvas Quiz，整理自 5270-questions-organized.md。

Question 1

[EN] Min-Cut is NP-Hard.

[CN] Min-Cut 是 NP-Hard。

选项	答案
False	✅
True	❌

知识点：Min-Cut 是多项式时间可解的（Karger 算法、Max-Flow 方法）。

Question 2

[EN] Min-Cut can be solved using calls to a Max-Flow algorithm, where is equal to...

[CN] Min-Cut 可以用次 Max-Flow 算法调用求解，其中等于

选项	答案
	❌
1	❌
	✅

Question 3

[EN] If is a minimum cut, then Karger's algorithm returns it with probability at least...

[CN] 若是最小割，Karger 算法返回它的概率至少为

选项	答案
	❌
	❌
	✅

Question 4

[EN] If is a minimum cut, then Karger-Stein's algorithm returns it with probability at least...

[CN] 若是最小割，Karger-Stein 算法返回它的概率至少为

选项	答案
	✅
	❌
	❌

注：Organized 文件中标记为，但实际 Karger-Stein 概率为，这里使用正确值。

Question 5

[EN] To achieve constant probability of success, Karger's algorithm runs in time:

[CN] 为达到常数成功概率，Karger 算法运行时间为

选项	答案
	❌
	❌
	❌
	✅

Question 6

[EN] The key idea behind Karger's algorithm is that if is a minimum cut, it is ____ likely to be killed than other cuts because it has ____ edges.

[CN] Karger 算法的核心思想：若是最小割，它被收缩掉的概率比其它割更_，因为它有更_条边。

选项	答案
more/fewer	❌
more/more	❌
less/fewer	✅

Question 7

[EN] Every undirected graph on vertices has ___ many distinct cuts.

[CN] 个顶点的无向图有____个不同的割。

选项	答案
	✅
	❌
	❌
	❌

Question 8

[EN] The idea behind the Karger-Stein algorithm is that Karger's algorithm makes ____ progress in ___ iterations.

[CN] Karger-Stein 算法的思想是：Karger 算法在_次迭代中取得_进展。

选项	答案
good/later	❌
good/earlier	✅
good/all	❌
little/earlier	❌

知识点：收缩前期边多，不容易误杀；后期边少易误杀。Karger-Stein 用递归改进后期。

Question 9

[EN] The analysis of Karger's algorithm can be used to immediately show an upper bound on the number of maximum cuts in an undirected graphs.

[CN] Karger 算法的分析可立即推出无向图中最大割数量的上界。

选项	答案
True	❌
False	✅

Question 10

[EN] Karger's algorithm can be modified to work on weighted undirected graphs.

[CN] Karger 算法可以扩展到加权无向图。

选项	答案
True	✅
False	❌

Week 5 Quiz 速查表

题号	核心概念	正确答案
1	Min-Cut 是 NP-Hard	False
2	Min-Cut 用 Max-Flow 次数
3	Karger 成功概率
4	Karger-Stein 成功概率
5	Karger 运行时间
6	最小割不易被收缩	less/fewer
7	图中割的数量
8	Karger 前期进展好	good/earlier
9	Karger 分析→最大割上界	False
10	Karger 加权图	True

高频混淆点： - Karger 成功概率 ，运行次 → 总时间（Q3, Q5） - Karger-Stein 改进到 （Q4） - 割的总数是 （Q7）

这周到底在学什么？（先看这里）

先统一语言：图论基础词汇

Karger contraction 的核心直觉：把点"捏"到一起

Part 1: Tutorial 5 详细题解

Tutorial 开头的难度/要求说明

Warm-up

Problem 1: 一个图有多少个不同的 cut？

Problem 2: Karger-Stein 的运行时间和成功概率递推

运行时间递推

成功概率递推

Problem 3: 改递归分支数会怎样？

只做 1 次递归

做 3 次递归

Problem Solving

Problem 4: 在 时间内均匀随机采样一条边

方法：按 degree 加权采样顶点

adjacency matrix 的 rejection sampling 版本

Problem 5: k-Min-Cut（Karger 推广到 k 组）

a) 算法

b) 成功概率分析

c) -min-cuts 的数量上界

Problem 6: 随机权重 MST 算法 = Karger？

为什么随机权重等价于随机边序？

Kruskal 在干什么？

为什么删去 MST 最大边就得到 cut？

时间复杂度

Advanced

Problem 7: 加权图上的 Karger / Karger-Stein

加权版 contraction

分析为什么会成立

Part 2: Week 5 讲义知识点详解

1. Min-Cut 是什么？为什么要随机化？

2. Contraction 是怎么回事？

3. Basic Karger 算法

4. 成功概率分析（最重要的部分）

为什么 活着 = 算法输出 ？

每步安全概率

全部步骤乘起来

重复放大

5. Karger-Stein：为什么不要一路 contract 到底？

6. Minimum Cuts 的数量上界

7. MST 部分：先掌握两个 property

Cycle Property（环性质）

8. F-heavy Edge：哪些边一定不在 MST 里？

9. KKT MST 的三个组件

① MSTVerification（MST 验证器）

② Random Subsampling Lemma（随机采样引理）

③ Boruvka Steps（Boruvka 缩点）

10. KKT 算法流程

11. 讲义定理速查

12. 本周证明套路总结

本周核心记忆卡

Part 3: Week 5 Quiz 回顾

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Week 5 Quiz 速查表

Problem 4: 在时间内均匀随机采样一条边

为什么活着 = 算法输出？