Joey

COMP5270 Assignment 1 marked solutions 中文题解，覆盖随机集合、离散随机比特、balls into bins 和星形图采样。

Microsoft Build 2026 前夕 Agent 密集预告，比特币 ETF 创纪录流出 29.7 亿美元，Aave 因 2.3 亿美元漏洞重塑上币标准。

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

---

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

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

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

这周有两条主线：

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

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

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

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