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

Posted on Edited on In , Word count in article: 5.5k Reading time ≈ 20 mins.

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

Part 1: Tutorial 5 详细题解

Warm-up

Problem 1: 无向图有多少个不同 cut?

题目: 解释为什么 个顶点的无向图恰好有 个不同 cut。这里不要求是 minimum cut。

题解:

一个 cut 本质上是把顶点集 分成两个非空部分：

其中 ，并且 ，。

所有子集一共有 个。去掉两个非法子集：

  • ：另一边是 ，不是两个非空部分；
  • ：另一边是空集。

所以合法子集数是：

但是 cut 没有方向， 和 是同一个 cut，因此每个 cut 被数了两次。于是不同 cut 的数量是：

结论：

本题用到的知识点:

  1. cut 是顶点集的二分 partition。
  2. 与 表示同一个无向 cut。
  3. 子集计数时要去掉空集和全集，再除以 2。

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

题目: 求 Karger-Stein algorithm 的两个 recurrence：运行时间递推和成功概率递推。

题解:

Karger-Stein 的思想是：不要把 Karger contraction 一路做到 2 个点，因为最后几步杀掉 min-cut 的概率太高。它先收缩到大约

个顶点，然后递归跑两次，最后取较小 cut。

1. 运行时间递推

每一层做两次 ModifiedKarger，每次 contraction 总成本是 ；然后递归到两个规模约为 的子问题，所以：

展开：

再展开一层：

注意：

所以每一层贡献都是 。规模每次变成 ，层数是 ，因此：

2. 成功概率递推

设 是在 个点上成功返回某个固定 min-cut 的概率。ModifiedKarger 收缩到 左右时，固定 min-cut 存活概率至少 。之后递归调用成功概率是 。

单个分支成功概率至少：

两个分支独立，最终失败当且仅当两个分支都失败，因此：

课程证明这个递推给出：

所以单次 Karger-Stein 比 basic Karger 的 成功率好很多。

本题用到的知识点:

  1. Karger-Stein 停在 规模后递归。
  2. 运行时间递推 。
  3. min-cut 存活概率乘法分析。
  4. 两次递归用“两个都失败”的补事件分析成功概率。

Problem 3: Karger-Stein 改成 1 次或 3 次递归会怎样?

题目: 如果 Karger-Stein 每层只做 1 次递归而不是 2 次，会发生什么？如果做 3 次呢？

题解:

1. 只做 1 次递归

如果每层只保留一个递归分支，那么算法大致变成“跑 basic Karger，只是每隔一段检查一次”。它没有利用“两条独立递归路径降低失败概率”的结构。

成功概率会在每层乘上约 ，递归深度是 ，整体仍会变得很小，无法得到 Karger-Stein 的 保证。

运行时间会更低，但成功概率明显变差。

2. 做 3 次递归

若每层做 3 次 ModifiedKarger 和 3 次递归，运行时间递推变成：

用 Master-style 展开。第 层有 个子问题，每个子问题规模约为 ，该层总成本：

深度是 ，因此总和：

这等于：

因为 。

成功概率会变好，因为现在需要 3 个分支全失败才失败；但运行时间更大。

本题用到的知识点:

  1. Karger-Stein 的递归次数直接影响时间递推。
  2. 型递推的层级展开。
  3. 多分支随机算法用补事件分析成功概率。

Problem Solving

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

题目: 给定 multigraph ，无论是 adjacency matrix 还是 adjacency list 表示，说明如何在 时间均匀随机采样一条边，其中 。

题解:

关键是：均匀采样 edge 不能简单地均匀采样 vertex 后再均匀采样邻边，因为高/低度顶点被选中的概率不同。正确方法要让每条边最终概率相同。

方法 1: 按 degree 加权采样端点

设顶点 的 degree 是 。先按概率

采样一个顶点 ，然后在 的邻接边里均匀采样一条边，即概率 。

考虑任意边 。它可以通过端点 被选到，也可以通过端点 被选到：

因为无向图中：

所以：

每条边概率相同，所以是均匀采样。

时间复杂度

如果 degree 可 查询，扫描所有顶点计算前缀和需要 。再根据采样位置找到对应顶点， 足够。选邻边也可以在 内完成。

因此总时间：

adjacency matrix 的 rejection sampling 版本

如果图连通，则 。在 adjacency matrix 中可以随机采样坐标 ，若对应边存在则返回，否则重试。一次命中概率大约是 ，期望尝试次数是 。

本题用到的知识点:

  1. Handshaking lemma：。
  2. 按 degree 加权采样可以抵消后续 。
  3. rejection sampling 的期望时间等于命中概率的倒数。

Problem 5: -Min-Cut 的 Karger 推广

题目: -Min-Cut 要把 分成 个非空部分，使跨 component 的边数最少。要求：

  1. 改造 basic Karger algorithm；
  2. 分析成功概率和运行时间；
  3. 给出 -min-cuts 数量上界。

题解:

这里把 视为常数。若 不是常数，运行时间会出现 ，不再是通常意义上的 polynomial。

a) 算法

basic Karger 对 2-cut 是一直 contract 到 2 个 supervertices。对 -cut，自然做法是 contract 到 个 supervertices。

但为了保证成功概率更容易分析，solution 中使用：

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

因为 是常数， 个点上的 brute force 是常数级：

b) 成功概率

设固定的 optimal -cut 为：

其 cut size 是 。算法成功的充分条件是：contract 过程中从不 contract 中的跨部分边。

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

直觉是：把当前顶点分成若干个大小最多为 的组。每个完整大小为 的组，如果这些点的总 degree 小于 ，就能把这一组切出来得到比 更小的 -cut，矛盾。

因此当前一步选中坏边的概率满足：

所以存活概率至少是：

整理后可得：

所以重复

次，取最小 cut，即可让失败概率降到 。

每次 contraction 到 的成本仍是 ，所以总时间大致是：

对常数 是 polynomial。

c) -min-cuts 个数上界

如果某个固定 optimal -cut 被单次算法输出概率至少 ，而所有不同 optimal -cuts 的输出事件互斥，总概率不超过 1，那么 optimal -cuts 的个数最多是：

更精细的分析可以把存活概率写成约 ，但本题需要的上界是 。

本题用到的知识点:

  1. Karger contraction 的成功条件：不 contract 目标 cut 的边。
  2. 用 minimum cut 性质推出 degree/edge 数下界。
  3. 概率乘法链：每一步条件存活概率相乘。
  4. 由算法输出概率推出结构性定理：minimum cuts 数量上界。

Problem 6: 随机权重 MST 算法等价于 Karger

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

题解:

这个算法看起来像 MST，但本质上是在用 Kruskal 模拟 Karger contraction。

1. 随机权重给出随机 edge ordering

每条边的权重独立连续均匀，因此几乎不会打平。按权重从小到大排序，就是对所有边的一个 uniformly random permutation。

Kruskal 按这个随机顺序扫描边：

  • 如果边连接两个不同 component，就加入 MST；
  • 如果边在同一 component 内，就跳过，因为会形成 cycle。

2. Kruskal 的“加入边”对应 contraction

Karger 每一步均匀随机选一条当前 multigraph 的边并 contract。

在 Kruskal 中：

  • 若当前扫描到的边连接两个不同 component，它就把两个 component 合并；
  • 这正是 contraction；
  • 若边在同一个 component 内，它相当于 contraction 后形成的 self-loop，应被忽略。

因为剩余边的相对顺序仍然是 uniformly random，所以每一步等价于在当前图中均匀随机选一条可 contraction 的边。

3. 为什么删去 MST 最大边得到 cut?

Kruskal 最终会选出 条边。Karger basic algorithm contract 到 2 个 supervertices 时其实只做了 次有效 contraction。

Kruskal 多做了最后一次，把两个 component 合成一个 spanning tree。删去 MST 中最后加入的那条边，即最大权重边，就回到 Karger 停在两个 component 的状态。

因此返回的 cut 分布与 basic Karger 相同。

4. 时间复杂度

实现方式：

  1. 给每条边生成随机权重：；
  2. 按权重排序：；
  3. Kruskal + union-find：，被排序主导。

总时间：

本题用到的知识点:

  1. 连续独立随机权重诱导 uniformly random ordering。
  2. Kruskal 的 component merge 等价于 contraction。
  3. MST 去掉最大边得到两个 component。
  4. Kruskal 复杂度由排序 主导。

Advanced

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

题目: 证明 Karger 算法可以修改为适用于非负加权无向图。Karger-Stein 也同理。

题解:

非加权图中，每条边被均匀选中。加权图中，一个自然的修改是：按边权比例采样边。

对当前图 ，选边 的概率设为：

然后 contract 这条边。

设固定的最小加权 cut 为 ，权重为：

算法失败的唯一方式仍然是 contract 到 cut 中的边。当前一步选到 cut 边的概率是：

因为 是 minimum cut weight，所以当前图中任何单点 cut 的权重都至少是 。于是每个顶点的 weighted degree 至少 ，从而：

因此：

这与非加权 Karger 的关键不等式完全相同。后续概率乘法不变：

Karger-Stein 的分析也只用到“每一步杀掉 cut 的概率 ”，所以加权版本直接成立。

本题用到的知识点:

  1. 加权 contraction 中按 采样边。
  2. minimum weighted cut 推出所有 weighted degree 至少为 cut weight。
  3. Karger 分析本质只需要每一步 bad probability 上界。
  4. Karger-Stein 对加权图同样适用。

Part 2: Week 5 讲义知识点

0. 基础版导读：这周到底在学什么?

Week 5 的主题是 随机化图算法。这周不是只背 Karger 或 MST 的步骤，而是训练一种分析方式：

随机做一个看起来危险的操作，然后证明它破坏最优解的概率不大。

这周有两条主线：

  1. Minimum cut：用随机 contraction 找最小割。
  2. Minimum spanning tree (MST)：用随机采样和 cut/cycle property 删除不可能属于 MST 的边。

先把图论语言统一：

  • 图记作 ， 是顶点集合， 是边集合。
  • ，。
  • 一个 cut 是把顶点分成两边，例如 。
  • 一条边如果一端在 ，另一端在 ，就 crossing this cut。
  • cut 的大小是 crossing edges 的数量；加权图中是 crossing edges 的权重和。
  • Min-cut 是大小最小的 cut，记它的值为 。

Karger contraction 的核心直觉

Karger 算法反复做 edge contraction：

  1. 均匀随机选一条边 。
  2. 把 和 合并成一个 supervertex。
  3. 删除 self-loops，但保留 parallel edges。
  4. 重复到只剩两个 supervertices。

最后两个 supervertices 对应原图顶点的一种划分，因此输出一个 cut。

分析时固定一个真正的 min-cut 。如果算法从头到尾都没有 contract 里的边，那么 的两边永远不会被合并，最后算法就会输出这个 cut。所以成功条件可以写成：

每一步都没有选到目标 min-cut 的 crossing edge。

这就是这周最重要的证明角度：不直接证明“算法聪明地找到了答案”，而是证明“随机过程有一定概率没有毁掉某个固定最优解”。

Karger 成功概率为什么是 ?

假设当前还有 个 supervertices，并且目标 min-cut 还没被破坏。由于 仍然是大小 的 cut，当前图的 min-cut 也至少是 。所以每个 supervertex 的 degree 至少为 ；否则把这个 supervertex 单独切出来，就得到小于 的 cut。

于是当前边数满足：

危险边只有 中的 条，所以这一轮选到危险边的概率最多是：

安全概率至少是：

从 个点一路缩到 个点，安全概率相乘：

这个概率不大，但它是多项式小，不是指数小。于是重复 次可以把失败概率降到很低。

Karger-Stein 为什么要分支递归?

Basic Karger 最危险的是后半段：点越少，每一步选中 min-cut 边的概率越高。Karger-Stein 的想法是先只 contract 到约 个点。做到这里时，保留某个固定 min-cut 的概率仍然是一个常数级别。然后算法复制成两个独立分支递归。

你可以把它理解成：

  • 前半段 contraction 很便宜，而且成功概率还不错。
  • 后半段风险大，所以不只赌一次，而是分成两个分支。
  • 两个分支只要有一个成功，整体就成功。

因此成功概率递推形如：

其中 是前半段没有破坏目标 min-cut 的概率。tutorial 中关于 1 次递归、2 次递归、3 次递归的题，就是在训练你看懂这个 trade-off：分支少则成功概率低，分支多则运行时间高。

MST 部分要先掌握两个 property

MST 是 Minimum Spanning Tree，目标是在连通加权图中选 条边连接所有顶点，并让总权重最小。

两个基本性质必须会用：

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

Cycle property：对任意 cycle，cycle 上最重的边一定不需要出现在 MST 中。

Kruskal、Prim、Boruvka 和 Karger-Klein-Tarjan 都是在不同方式下利用这两个性质。

-heavy edge 的直觉

假设 是一个 forest。对一条边 ，如果 到 在 中已经有路径，并且 的权重大于这条路径上每条边，或者至少大于路径上的最大边，那么加上 会形成一个 cycle，而 是这个 cycle 上最重的边。

根据 cycle property， 不可能属于 MST。这样的边就是 -heavy edge，可以安全删除。

KKT MST 算法的核心可以粗略理解成：

  1. 随机抽样一部分边。
  2. 在抽样图上递归求一个 MST/forest。
  3. 用这个 forest 判断原图中哪些边是 heavy。
  4. 批量删除这些不可能属于 MST 的边。

所以这部分不是要你死记复杂递归，而是要看懂：随机采样给出一个参照 forest，cycle property 让我们安全删边。

做题时怎么判断用哪个工具?

  • 题目问 contraction 成功概率：固定一个 min-cut，计算每轮不选 cut edge 的概率。
  • 题目问重复次数：用 。
  • 题目问 min-cuts 数量上界：用“每个 min-cut 被输出的概率至少某个值，总概率不超过 1”。
  • 题目问加权图：把“边数”换成“权重和”，危险概率用 cut weight / total weighted degree。
  • 题目问 MST 边能否删除：优先想 cycle property。
  • 题目问某条边是否必须能加入 MST：优先想 cut property。

1. Min-Cut 与 contraction

Min-Cut 问题：给定连通无向图 ，输出 cut 使跨边数：

最小。

Edge contraction 是把一条边 的两个端点合成一个 supervertex，并删除 self-loop，但保留 parallel edges。因此算法自然工作在 multigraph 上。

如果 contraction 最后剩下两个 supervertices，它们对应原图顶点集的一个 partition，也就是一个 cut。

2. Basic Karger 算法

算法：

  1. 当 时：
    • 均匀随机选择一条边；
    • contract 这条边；
  2. 返回最后两个 supervertices 定义的 cut。

单次运行时间：

因为每次 contraction 可 ，一共 次。

3. Karger 的成功概率

固定一个 minimum cut ，大小为 。它被返回的充分必要条件是：整个过程中没有 contract 中的任何边。

若当前还剩 个顶点，且 存活，则当前图的 minimum degree 至少 。否则某个单点 cut 小于 ，与 minimum cut 矛盾。

所以：

当前 contract 到 中边的概率：

存活概率：

因此：

重复 次，失败概率：

总时间：

4. Karger-Stein

Karger basic 的问题在最后几步：当只剩 3 个点时，最后一步杀掉 min-cut 的概率上界达到 。

Karger-Stein 的修正：

  1. 只 contract 到约 个点；
  2. 独立做两次；
  3. 对两个子图递归；
  4. 返回更小的 cut。

核心结果：

单次成功率：

重复放大后：

时间可获得 成功概率。

5. Minimum cuts 数量上界

Karger analysis 不只证明算法成功，也给出结构性定理。

若图中有 个不同 minimum cuts，每个被 Karger 输出概率至少：

这些输出事件互斥，所以：

即：

这个界是 tight 的：cycle graph 有 个 minimum cuts，因为任意选两条边断开 cycle 都得到一个 min-cut。

6. MST 与 Karger-Klein-Tarjan

Week 5 后半介绍 randomized expected linear time MST。

经典 deterministic MST：

  • Kruskal: ；
  • Prim: ；
  • Boruvka: ；
  • 更高级算法接近线性，但很复杂。

Karger-Klein-Tarjan 给出 expected：

7. MST 的 cut property 与 cycle property

Cut property: 对任意 ，跨越 cut 的最轻边一定在 MST 中。

Cycle property: 任意 cycle 中最重边一定不在 MST 中。

这两个性质是 Kruskal、Prim、Boruvka 和 KKT 的基础。

8. -heavy edges

给定 forest ，若边 加入 后形成 cycle，并且 是该 cycle 中最重边，则称 是 -heavy。

由 cycle property：

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

9. KKT MST 的三个 building blocks

  1. MSTVerification: 给定 和 forest ，线性时间找出所有 -heavy edges。

  1. Random Subsampling Lemma: 每条边以概率 保留得到 ，令 为 的 MSF，则原图中非 -heavy 的边期望至多：

  1. Boruvka steps: 每轮每个 component 选择 incident 最轻边并 contract。 轮后顶点数至少缩小 倍：

10. KKT 算法流程

  1. 运行若干轮 Boruvka，缩小顶点数；
  2. 随机 subsample 边；
  3. 递归求 sampled graph 的 MSF ；
  4. 用 找原图中的 heavy edges 并删除；
  5. 对剩余图递归求 MSF；
  6. 加上 Boruvka 阶段收缩的边，得到 MST。

设置 ， 时可证明：

随机性只影响运行时间，不影响正确性；因此这是 Las Vegas 风格算法。

本周核心记忆

主题 关键结论
cut 数量 所有 cut 有 个
Basic Karger 时间，成功率
放大 Karger 时间，高概率成功
Karger-Stein 时间，成功率
min-cuts 数量 最多 个
weighted Karger 按边权比例采样
MST cut property cut 上最轻边在 MST 中
MST cycle property cycle 上最重边不在 MST 中
KKT MST expected