知识焦点
先建立概念地图
- minimum spanning tree
- Boruvka's algorithm
- cut property
- maximum spanning tree
- infinity-norm cut
- k-center
- approximation algorithm
- greedy algorithm
CS170 · 作业 6
CS 170 2023 年秋季作业 6，截止时间为 2023 年 10 月 11 日 22:00（宽限至 23:59）。本次作业共四题：分析 Borůvka 最小生成树算法的正确性与复杂度；利用最大生成树求解最小 ∞-范数割；以及为消防站选址问题（k-中心问题）设计 2-近似贪心算法。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：hw06.pdf、hw06-sol.pdf
本地一手资料完整提取 · 作业
本节按本地一手资料完整整理，共 4 道大题。本地官方解答已收录 3/4 道并默认折叠；其余题目会明确标注无本地官方解答。
hw06.pdf、hw06-sol.pdf列出你的学习小组中所有成员的姓名和 SID（学生编号）。如果你没有合作者，必须明确写出 "none"。
请依据自己的实际协作或提交情况填写；本题没有唯一的标准答案。
本地资料未提供这道题的官方解答；页面只保留题面与非答案式提示。
题面来源：hw06.pdf · 1 · confidence: high
在无向带权图 \(G(V, E)\) 中，考虑以下求最小生成树（Minimum Spanning Tree, MST）的算法。该算法与 Prim 算法类似，但它不是从单个顶点出发生长生成树，而是尝试同时从每个顶点出发生长生成树。
procedure FindMST(G(V, E))
T ← ∅
while T is not a spanning tree do
Let S1, S2 ... Sk be the connected components of the graph with vertices V and edges T
For each i ∈ {1, ..., k}, let ei be the minimum-weight edge with exactly one endpoint in Si
T ← T ∪ {e1, e2, ... ek}
return T
例如，在第一次迭代开始时，每个顶点各自构成一个 \(S_i\)。
为简化起见，在以下各部分中你可以假设 \(G\) 中没有两条边的权值相同。
(a) 证明该算法能找到一棵最小生成树。
(b) 给出该算法运行时 while 循环在最坏情况下迭代次数的紧上界（tight upper bound）。证明你的答案。
(c) 利用上一部分的结论，给出该算法运行时间的上界。
切入点：对每个连通分量 \(S_i\)，考虑割 \((S_i, V - S_i)\) 并应用割性质（cut property）——恰好有一个端点在 \(S_i\) 中的最小权边必在 MST 中。关于迭代次数，注意每条新加入的边最多只能被两个分量「贡献」，因此每轮迭代后分量数至少减半。
自检：若某轮有 \(k\) 个分量但只加入少于 \(k/2\) 条边，是否意味着某条边被超过两个分量贡献？这与边的什么性质矛盾？
该算法被称为 Borůvka 算法（Boruvka's algorithm）。尽管作为 MST 算法看起来可能有些复杂，它早在 1926 年就被发现，早于 Prim 算法和 Kruskal 算法。该算法至今仍受关注，因为它易于并行化，并且是一个期望时间 \(O(|E|)\) 的随机化 MST 算法的基础。
(a) 当我们把边 \(e_i\) 加入 \(T\) 时，是因为它是恰好有一个端点在 \(S_i\) 中的最小权边。因此，对割 \((S_i, V - S_i)\) 应用割性质可知，\(e_i\) 必须属于（唯一的）最小生成树。所以我们加入的每条边都必须是最小生成树中的边，即该算法恰好找到最小生成树。
(b) 在具有顶点 \(V\) 和边 \(T\) 的图中，分量数初始为 \(|V|\)，每个顶点自成一个分量。若某轮迭代开始时有 \(k\) 个分量，则该轮必须加入至少 \(k/2\) 条边：每个分量 \(S_i\) 对我们加入的边集贡献某条 \(e_i\)，而每条被加入的边最多只能被两个分量贡献。这意味着每轮迭代分量数至少减少为原来的一半。因此，while 循环最多运行 \(\log |V|\) 轮。
(c) 由 (b) 可知最多需要 \(\log |V|\) 轮迭代。每轮迭代可在 \(O(|E|)\) 时间内完成（例如，可在 \(O(|E|)\) 时间内计算各分量，然后初始化一个表格记录每个分量恰好有一个端点在其中的最便宜边，再通过一次对所有边的线性扫描填充该表格），因此运行时间上界为 \(O(|E| \log |V|)\)。
解答来源：hw06-sol.pdf · 1-2 · confidence: high
题面来源：hw06.pdf · 1 · confidence: high
在最小 ∞-范数割（Minimum Infinity-Norm Cut）问题中，给定一个连通无向图 \(G = (V, E)\)，边权 \(w_e\) 为正，要求找出图中的一个割，使得该割中最大的边权尽可能小（注意：此问题中没有源点或目标点的概念；任何两边都至少有一个节点的割都是合法割）。
在 \(O(|E| \log |V| + |V| + |E|)\) 时间内解决该问题。给出包含三个部分的解答（算法、正确性证明、运行时间分析）。
提示：最小生成树并不要求边权必须为正。
考虑将所有边权取负后运行 Kruskal 算法，得到原图的最大生成树（maximum spanning tree）。最大生成树中的最小权边被移除后形成的割与原问题的答案有何关系？注意割性质对最大生成树同样成立：任意割的最大权边必在最大生成树中。
自检：验证树中的割的 ∞-范数是否等于原图中同一割的 ∞-范数。为什么最大生成树保留了每个割的 ∞-范数？
算法：首先将 \(G\) 中所有边权取负，将得到的新图送入 Kruskal 最小生成树算法；这将给出原图的一棵最大生成树。移除这棵最大生成树中权值最小的边，返回由该边移除所诱导的割。
正确性证明：首先注意到我们正确地找到了图的最大生成树，因为最大生成树 \(T\) 满足 \(\sum_{e \in T} w_e = -\sum_{e \in T} (-w_e)\)，即最大化原图边权之和等价于在取负后的图上最小化边权之和。同样容易看出，我们在图的最大生成树中找到了一个最小 ∞-范数割（使用生成树中其他任何边都不可能使割的 ∞-范数更小，因为我们只使用了可能的最小边）。
接下来只需证明：图中任意节点割在整棵树中的 ∞-范数与在整个图中的 ∞-范数完全相同；这将证明算法的正确性（因为我们已经证明了算法在树上的正确性）。为此，我们将使用最大生成树的割性质（它由最小生成树的割性质在取负后的图上直接推出）。该性质是：对于图中的任意割，其最大权的那条边（若最大边不唯一，则为其中之一）必须包含在最大生成树中。由于割的 ∞-范数等于其最大边的权值，这意味着割在树中的 ∞-范数至少等于其在图中的 ∞-范数；同时它也不会超过在图中的 ∞-范数，因为树中不存在图中所没有的边。
运行时间分析：创建将所有边权取负的新图需要 \(O(|V| + |E|)\) 时间。得到最大生成树后，可通过一次简单的 \(O(|E|)\) 时间搜索找到最小权边；移除该边后，可通过 \(O(|V| + |E|)\) 时间的遍历枚举出两个连通分量中的节点。因此，总体我们将该问题转化为 MST 问题花费了线性时间。
然后我们可以在 \(O(|E| \log |V|)\) 时间内运行 Kruskal 算法找到 MST。找到最小 ∞-范数割需要遍历所有边。因此，最终运行时间为 \(O(|E| \log |V| + |V| + |E|)\)。
替代解法：对边权数组排序，二分查找割中的最大边。对于权值为 \(w_m\) 的边，考虑图 \(G'\)，仅保留 \(E\) 中权值 \(\leq w_m\) 的边。若 \(G'\) 连通，则答案 \(\geq w_e\)；否则答案 \(< w_m\)。找到割的 ∞-范数 \(w_e\) 后，移除所有权值 \(\geq w_e\) 的边，任取一个连通分量及其补集即可恢复割。总体运行时间为 \(O(|E| \log |V|)\)。
解答来源：hw06-sol.pdf · 2-3 · confidence: high
题面来源：hw06.pdf · 2 · confidence: high
PNPLand 由 \(N\) 个城市组成，编号为 \(0, 1, \ldots, N-1\)，城市之间由双向道路连接。给定矩阵 \(D\)，使得对每对城市 \((a, b)\)，\(D[a][b]\) 为 \(a\) 与 \(b\) 之间最短路径的距离。
我们要选出 \(K\) 个不同的城市并在那里建造消防站。对于没有消防站的城市，其响应时间（response time）定义为到最近消防站的距离。我们定义有消防站的城市的响应时间为 \(0\)。令 \(R\) 为所有城市中的最大响应时间。我们希望创建一种消防站到城市的分配方案，使得 \(R\) 尽可能小。
假设最优的消防站分配方案产生的响应时间为 \(R_{\text{opt}}\)。给定正整数 \(N\)、\(K\) 和二维矩阵 \(D\) 作为输入，描述一个 \(O(N^2 \cdot K)\)（或更快）的贪心算法，输出一个达到响应时间 \(R_g \leq 2 \cdot R_{\text{opt}}\) 的分配方案。给出包含三个部分的解答（算法、正确性证明、运行时间分析）。在你的正确性证明中，证明算法达到了 2 的期望近似比。
提示：\(D[a][b]\) 表示最短（度量）距离。因此你可以使用三角不等式：对所有 \(a, b, c\)，有 \(0 \leq D[a][b] \leq D[a][c] + D[c][b]\)。
这是 k-中心（k-center）问题的一个实例。贪心策略：每次选择当前响应时间最大的城市建消防站。证明近似比时，考虑算法结束后响应时间最大的城市 \(v\)，以及 \(K\) 个消防站，共 \(K+1\) 个城市；在最优解中必有两个城市被同一个消防站覆盖，利用三角不等式导出矛盾。
自检：确认 \(R_K > 2R_{\text{opt}}\) 的假设如何导致矛盾。具体地，在最优解中距离某消防站最近的两个城市 \(a, b\) 都在集合 \(S\) 中，它们的距离如何被三角不等式限制？
算法描述：首先在任一城市（例如城市 1）建造消防站。对于剩下的 \(K-1\) 个消防站，反复找到当前响应时间最大的城市并在那里建造消防站。
正确性证明：设 \(R_i\) 为算法建造第 \(i\) 个消防站时的最大响应时间（\(i > 1\)）。观察到，在算法的第 \(i\) 步，任意两个消防站之间的行程时间 \(\geq R_i\)。我们要证明 \(R_K = R_g \leq 2R_{\text{opt}}\)。
假设算法导致某个城市 \(v\) 的响应时间为 \(R_K > 2R_{\text{opt}}\)。那么每对消防站之间的行程时间都 \(> 2R_{\text{opt}}\)。
现在考虑这 \(K+1\) 个城市的集合 \(S\)：\(K\) 个消防站和 \(v\)。在最优解中，必须存在一个消防站 \(w\)，使得 \(w\) 是集合 \(S\) 中两个城市 \(a, b\) 最近的消防站。因此 \(D[a][b] \leq D[a][w] + D[w][b] \leq 2R_{\text{opt}}\)。然而，由于 \(a, b\) 都在 \(S\) 中，\(D[a][b] > 2R_{\text{opt}}\)。这是矛盾的。
运行时间分析：共有 \(K\) 轮迭代，每轮迭代需要 \(O(N^2)\) 时间，因为我们要查看每对消防站之间的距离。因此，总体运行时间为 \(O(N^2 K)\)。
解答来源：hw06-sol.pdf · 3-4 · confidence: high
题面来源：hw06.pdf · 2 · confidence: high
hw06.pdfhw06-sol.pdf