知识焦点
先建立概念地图
- Bellman-Ford
- Dijkstra
- shortest path
- MST
- Kruskal
- Prim
- cut property
- cycle property
CS170 · 讨论课 5
本讨论课涵盖：Bellman-Ford 算法性质与正确性证明、Dijkstra 算法与负权边、拓扑排序、最小生成树（MST）的 Prim 与 Kruskal 算法及切割/环性质、贪心算法反例（旅行商问题、最大匹配、区间调度）、Horn 公式、霍夫曼编码最长码字、最小化平均等待时间的调度问题，以及 MST 练习。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：dis05.pdf、dis05-sol.pdf
本地一手资料完整提取 · 讨论课
本节按本地一手资料完整整理，共 25 道大题。本地官方解答已完整收录并默认折叠；建议先独立完成，再逐题核对推导。
dis05.pdf、dis05-sol.pdf判断对错：Kruskal 算法（Kruskal's algorithm）在存在负权边（negative edges）的图上仍然有效。若答案为真，请证明；若为假，请给出反例。
Kruskal 算法的正确性基于割性质（cut property）：跨越任意割的最轻边属于某棵 MST。思考这一性质是否依赖于边权为非负。
真。割性质在存在负权边时仍然成立。如果希望所有边权为正，我们可以给每条边加上一个常数使其全部变为正数，再运行 Kruskal 算法。
解答来源：dis05-sol.pdf · 3 · confidence: high
题面来源：dis05.pdf · 3 · confidence: high
我们修改一个含负权边（negative edges）的图 \(G\)，给每条边加上一个足够大的正常数，使得所有边权变为正数，记此修改后的图为 \(G'\)。判断对错：如果在 \(G'\) 上运行 Dijkstra 算法（Dijkstra's algorithm），则在 \(G'\) 上得到的最短路径也是 \(G\) 上的最短路径。若答案为真，请证明；若为假，请给出反例。
考虑路径中边数的影响。在 \(G'\) 中每条边都增加了相同的常数，那么边数不同的路径受到的影响有何不同？边数多的路径在 \(G'\) 中会累积更多的额外常数。
假。在 \(G'\) 中，边数更多的路径会被更多地惩罚（每条边都多了一个常数）。这意味着在 \(G\) 中一条含很多条边的最短路径在 \(G'\) 中不再是最短路径。
解答来源：dis05-sol.pdf · 3 · confidence: high
题面来源：dis05.pdf · 3 · confidence: high
设 \(G = (V, E)\) 是一个边权为正的有向无环图（DAG, Directed Acyclic Graph）。我们先运行 Dijkstra 算法计算源点 \(s\) 到每个其他顶点 \(v\) 的距离，然后将顶点按照距 \(s\) 的距离递增顺序存储。判断对错：这一顶点序列是 \(G\) 的一个有效的拓扑排序（topological sort）。若答案为真，请证明；若为假，请给出反例。
顶点: A, B, C；边: 需满足拓扑序 A→B→C 且 Dijkstra 距离满足 dist(A) < dist(C) < dist(B)
来源：dis05.pdf · 3
拓扑排序要求所有边从前指向后。思考 Dijkstra 距离的顺序是否一定满足这一条件。尝试构造一个含三个顶点的小反例，使得某条边的起点距离大于终点距离。
假。考虑以下图：一个拓扑排序应为 \(A, B, C\)，但按本题方法得到的是 \(A, C, B\)。
解答来源：dis05-sol.pdf · 3 · confidence: high
题面来源：dis05.pdf · 3 · confidence: high
设 \(G = (V, E)\) 是一个无向图。设 \(G' = (V', E')\) 其中 \(V' = V \cup \{u\}\)，\(E' = E \cup E_u\)，其中 \(E_u\) 是某组包含 \(u\) 的边的集合。判断对错：\(G\) 的任意一棵最小生成树（MST, Minimum Spanning Tree）都是 \(G'\) 的某棵 MST 的子集。若答案为真，请证明；若为假，请给出反例。
图 G 与 G' = (V∪{u}, E∪E_u)，其中 E_u 中的边权均小于 E 中的边权
来源：dis05.pdf · 4
考虑新顶点 \(u\) 的连接方式。如果 \(u\) 到 \(G\) 中各顶点的边都非常轻（比 \(G\) 中任何边都轻），会对 \(G'\) 的 MST 产生什么影响？此时 \(G'\) 的 MST 会包含哪些边？
假。考虑 \(G'\) 中新顶点 \(u\) 到所有其他顶点都有边的情况。如果从 \(u\) 出发的每条边都比 \(G\) 中的任何边都轻，则 \(G'\) 的 MST 由所有从 \(u\) 出发的边构成，不包含 \(G\) 的任何边。
解答来源：dis05-sol.pdf · 4 · confidence: high
题面来源：dis05.pdf · 3–4 · confidence: high
回顾 Dijkstra 算法依赖于按距离递增顺序访问顶点这一事实。因此，如果到顶点 \(u\) 的最短路径经过 \(v\)，由于 \(\text{dist}[v] < \text{dist}[u]\)，我们会先访问 \(v\) 再访问 \(u\)。当存在负权边时这不再成立，因为可能出现 \(\text{dist}[v] > \text{dist}[u]\) 的情况。本题研究 Bellman-Ford 算法如何避免这一问题。
设 \(G = (V, E)\) 为带负权可能的加权有向图，其中 \(|V| = n\)，\(|E| = m\)。我们希望找到从固定源点 \(s\) 到 \(V\) 中每个顶点的最短路径。
(a) 假设 \(G\) 没有总权值为负的环。证明：对任意顶点对 \(u, v\)，存在一条最多含 \(n - 1\) 条边的最短路径。
如果最短路径含有多于 \(n - 1\) 条边，根据鸽巢原理，路径上必有顶点被重复。这意味着什么？重复顶点之间的部分构成一个环，而该环的权值非负。
这是因为，如果路径含有多于 \(n - 1\) 条边，则路径上必有某个顶点被重复访问，即路径包含一个环。然而，由于该环不可能具有负权（题目假设无负权环），我们可以在不增加路径长度的情况下将其移除。
解答来源：dis05-sol.pdf · 5 · confidence: high
题面来源：dis05.pdf · 4 · confidence: high
考虑与 2(a) 相同的设定（\(G = (V, E)\) 为带负权可能的加权有向图，\(|V| = n\)，\(|E| = m\)，源点为 \(s\)）。设 \(d_k[v]\) 表示从 \(s\) 到 \(v\) 最多使用 \(k\) 条边的最短距离。
(b) 证明：如果 \(d_n[v] < d_{n-1}[v]\)，则 \(G\) 中必存在负权环。
利用 2(a) 的结论：如果没有负权环，最短路径最多含 \(n-1\) 条边。如果使用 \(n\) 条边能得到更短的距离，说明什么？
由 (a) 推出。因为如果没有负权环，任意两个顶点对之间不可能存在使用多于 \(n - 1\) 条边的更短路径。因此，若 \(d_n[v] < d_{n-1}[v]\)，说明存在一条使用 \(n\) 条边的更短路径，这意味着路径上有重复顶点，即包含一个环，且该环必为负权环。
解答来源：dis05-sol.pdf · 5 · confidence: high
题面来源：dis05.pdf · 4–5 · confidence: high
考虑与 2(a) 相同的设定，假设 \(G\) 没有负权环。
(c) 对任意 \(k \geq 0\)，\(d_k[s]\) 是多少？如果 \(v\) 是 \(s\) 的邻居，\(d_1[v]\) 的值是多少？
从 \(s\) 到 \(s\) 的最短路径是什么？使用恰好一条边从 \(s\) 到其邻居 \(v\) 的距离如何计算？注意没有负权环的假设保证了什么。
\(d_k[s] = 0\)，因为不存在负权环，从 \(s\) 到 \(s\) 的最短路径始终为空路径。如果 \((s, v)\) 是一条边，则 \(d_1[v] = w(s, v)\)，否则为 \(\infty\)。
解答来源：dis05-sol.pdf · 5 · confidence: high
题面来源：dis05.pdf · 5 · confidence: high
考虑与 2(a) 相同的设定，假设 \(G\) 没有负权环。
(d) 对于固定的 \(k > 1\)，假设给定所有 \(v \in V\) 的 \(d_{k-1}[v]\) 值，给出一个在 \(O(n + m)\) 时间内计算所有 \(v\) 的 \(d_k[v]\) 的算法。
使用松弛（relaxation）操作。对于每条边 \((u, v)\)，如何由 \(d_{k-1}\) 更新 \(d_k[v]\)？注意要同时考虑「不使用第 \(k\) 条边」和「使用第 \(k\) 条边」两种情况。
初始化 \(d_k[v] = \infty\)。遍历所有边，对边 \((u, v)\) 做如下更新： \[d_k[v] = \min(d_{k-1}[v], d_{k-1}[u] + w(u, v))\]
该算法对每条边处理一次，时间复杂度为 \(O(m)\)，加上初始化 \(O(n)\)，总计 \(O(n + m)\)。
解答来源：dis05-sol.pdf · 5 · confidence: high
题面来源：dis05.pdf · 5 · confidence: high
考虑与 2(a) 相同的设定，假设 \(G\) 没有负权环。
(e) 给定 \(K < N\) 的值，描述一个 \(O(n + K \cdot m)\) 算法，找出从 \(s\) 到每个 \(v\) 最多使用 \(K\) 条边的最短路径长度。证明你的算法是正确的。
从 \(d_0\) 开始，迭代应用 2(d) 中的算法。尝试用归纳法证明正确性：假设 \(d_{k-1}[\cdot]\) 正确，证明 \(d_k[\cdot]\) 也正确。
从 \(d_0[s] = 0\) 和 \(d_0[v] = \infty\)（对所有其他 \(v\)）开始，对 \(k = 1, 2, \ldots, K\) 重复应用 (d) 中的算法。
正确性可用归纳法证明。假设 \(d_{k-1}[\cdot]\) 正确，则 \[d_k[v] = \min\left(d_{k-1}[v], \min_{(u,v) \in E} \left(d_{k-1}[u] + w(u, v)\right)\right)\] 这就是 (d) 中算法所做的。唯一的区别是这里不需要显式遍历每个 \(v\) 的所有邻居，而是通过遍历 \(E\) 中的所有边来同时计算所有 \(d_k[v]\)。
时间复杂度：每次迭代 \(O(n + m)\)，共 \(K\) 次，总计 \(O(n + K \cdot m)\)。
解答来源：dis05-sol.pdf · 5 · confidence: high
题面来源：dis05.pdf · 5 · confidence: high
旅行商问题（Travelling Salesman Problem, TSP）：我们有一个带权无向图 \(G(V, E)\)，包含所有可能的边（即 \(G\) 是完全图）。目标是找到一条访问所有顶点恰好一次且长度最短的环。
一种贪心算法是：从任意起点 \(s\) 开始构建环，已访问顶点集合初始化为 \(\{s\}\)。在每一步，如果当前位于顶点 \(u\) 且环尚未访问所有顶点，则添加从 \(u\) 到某个未访问顶点 \(v\) 的最短边，然后移动到 \(v\) 并标记 \(v\) 为已访问。否则，添加一条从当前顶点到 \(s\) 的边，返回完成的环。
请给出一个反例，说明该贪心算法不能找到最优解。
思考贪心算法在早期选择低权值边后，是否可能被迫在后期选择高权值边。尝试构造一个含四个顶点的图，使得贪心算法被迫在最后选择一条极贵的边。
一个反例是四个顶点的图，顶点为 \(a, b, c, d\)，其中边 \((a, b), (b, c), (c, d)\) 的权值为 1，边 \((a, d)\) 的权值为 100，其余所有边的权值为 2。如果贪心算法从顶点 \(a\) 出发，它会依次将 \((a, b), (b, c), (c, d)\) 加入环，最后被迫加入权值很高的边 \((a, d)\) 来完成环，总代价为 103。最优环为 \((a, b), (b, d), (d, c), (c, a)\)，代价为 6。
关键思想是，通过使用低权值边构成的路径，我们迫使算法陷入必须选择高权值边才能完成解的境地。
解答来源：dis05-sol.pdf · 7 · confidence: high
题面来源：dis05.pdf · 5 · confidence: high
最大匹配问题（Maximum Matching）：我们有一个无向图 \(G(V, E)\)，目标是找到最大的匹配 \(E' \subseteq E\)，即 \(E'\) 是 \(E\) 的一个最大子集，使得 \(E'\) 中没有两条边共享端点。
一种贪心算法是：当存在一条边 \(e = (u, v)\) 使得 \(u\) 和 \(v\) 都不是 \(E'\) 中已有边的端点时，将任意这样的一条边加入 \(E'\)。
请给出一个反例，说明该贪心算法不能找到最优解。（挑战题：能否证明该算法找到的解的大小至少是最优解大小的一半？）
考虑一条含三条边的路径图。贪心算法可能选中中间的边，而最优解是选两条外侧的边。对于挑战题，思考最优解中的每条边与算法解的关系。
最简单的例子是一条含三条边的路径图。贪心算法可能选中中间的边，而最优解是选两条外侧的边。
为了证明该算法总能找到至少是最优解大小一半的匹配，设算法找到的解大小为 \(m\)。最优解中的任意一条边都与算法解中的某条边共享端点（否则贪心算法本可以将其加入）。最优解中的边不能共享端点，而算法解中的 \(m\) 条边共有 \(2m\) 个端点，因此最优解至多包含 \(2m\) 条边。
解答来源：dis05-sol.pdf · 7 · confidence: high
题面来源：dis05.pdf · 5–6 · confidence: high
区间调度问题（Interval Scheduling）：在课堂讲过的区间调度问题中，我们的贪心算法改为反复选择冲突数（conflicts）最少的区间。
请给出一个反例，说明该贪心算法不能找到最优解。
一组区间，其中冲突数最少的区间（深灰色）位于中间，选择它导致最终只选 3 个区间，而最优解为最上面的 4 个区间
来源：dis05.pdf · 6
思考选择冲突数最少的区间是否可能过早地排除大量其他区间。尝试构造一组区间，其中冲突数最少的区间位于中间位置，选择它会阻塞上下两端的多个区间。
考虑以下反例：这里我们会先选择深灰色区间，因为它的冲突数最少。然而，这最终只选了 3 个区间，少于最优解的 4 个区间（即最上面的 4 个区间）。
解答来源：dis05-sol.pdf · 7 · confidence: high
题面来源：dis05.pdf · 6 · confidence: high
求解下列 Horn 公式的变量赋值： \[(x \land z) \Rightarrow y, \quad z \Rightarrow w, \quad (y \land z) \Rightarrow x, \quad \Rightarrow z, \quad (\bar{z} \lor \bar{x}), \quad (\bar{w} \lor \bar{y} \lor \bar{z})\]
从单位子句（unit clause）开始。哪些变量必须为真？然后利用蕴含关系传播。最后检查负子句是否满足。
• \(z\) 必须为真，因为有语句 \(\Rightarrow z\)。 • \(w\) 必须为真，因为 \(z \Rightarrow w\)。 • 由负子句 \((\bar{z} \lor \bar{x})\) 可知 \(\bar{x}\) 必须为真，即 \(x = \text{False}\)。 • 由负子句 \((\bar{w} \lor \bar{y} \lor \bar{z})\) 可知 \(\bar{y}\) 必须为真，即 \(y = \text{False}\)。 • 所有蕴含式均已满足，因此满足赋值为：\(z = \text{True}, w = \text{True}, x = \text{False}, y = \text{False}\)。
解答来源：dis05-sol.pdf · 8 · confidence: high
题面来源：dis05.pdf · 6 · confidence: high
证明形如 \((x_i \land x_j \land \cdots) \Rightarrow \text{True}\) 的任意蕴含子句总是可满足的。
将蕴含式转化为等价的析取形式。\(A \Rightarrow B\) 等价于 \(\bar{A} \lor B\)。这里的 \(B = \text{True}\)，所以整个子句等价于什么？
该子句无论变量如何赋值都满足，因为它等价于 \((\text{True} \lor \bar{x}_i \lor \bar{x}_j \lor \cdots)\)，而 \(\text{True}\) 与任何公式的析取恒为真。
解答来源：dis05-sol.pdf · 8 · confidence: high
题面来源：dis05.pdf · 6 · confidence: high
证明形如 \(\text{False} \Rightarrow x_k\) 的任意蕴含子句总是可满足的。
将蕴含式转化为等价的析取形式。\(\text{False} \Rightarrow x_k\) 等价于什么？
该子句等价于 \((\text{True} \lor x_k)\)，因此无论 \(x_k\) 取何值都满足。
解答来源：dis05-sol.pdf · 8 · confidence: high
题面来源：dis05.pdf · 6 · confidence: high
在 \(n\) 个符号的霍夫曼编码（Huffman encoding）中，其频率分别为 \(f_1, f_2, \ldots, f_n\)，一个码字最长可能有多长？给出一个能产生该情况的频率组，并论证这是最长可能的。
考虑前缀树（prefix tree）的结构。一棵有 \(n\) 个叶子的二叉树的最大高度是多少？什么样的频率分布会产生最不平衡的树？
最长码字长度可达 \(n - 1\)。一种达到该值的编码是：\(n - 2\) 个符号的概率分别为 \(1/2, 1/4, \ldots, 1/2^{n-2}\)，另外两个符号的概率均为 \(1/2^{n-1}\)。
没有任何码字能超过长度 \(n - 1\)。理由如下：考虑编码的前缀树（prefix tree）。如果某码字长度大于等于 \(n\)，则前缀树高度大于等于 \(n\)，从而至少有 \(n + 1\) 个叶子。而字母表大小为 \(n\)，前缀树恰好有 \(n\) 个叶子，矛盾。
解答来源：dis05-sol.pdf · 8–9 · confidence: high
题面来源：dis05.pdf · 6 · confidence: high
一家诊所有 \(n\) 位顾客，编号为 \(1, 2, \ldots, n\)，正在等待就诊。他们现在都在场，会一直等到医生可以接诊。医生一次只能看一位顾客，我们可以准确预测每位顾客需要的就诊时间：顾客 \(i\) 需要 \(t(i)\) 分钟。
(a) 我们希望最小化平均等待时间（每位顾客在被接诊前等待的时间的平均值，不计他们在医生处花费的时间）。应该使用什么顺序？本小题无需证明。
将顾客按 [某量] 排序。思考短任务优先是否有助于减少后续顾客的等待时间。
将顾客按 \(t(i)\) 排序，从最小的 \(t(i)\) 开始。
解答来源：dis05-sol.pdf · 10 · confidence: high
题面来源：dis05.pdf · 7 · confidence: high
考虑与 6(a) 相同的设定。设 \(x_1, x_2, \ldots, x_n\) 表示顾客的一个排序（即我们先接诊顾客 \(x_1\)，然后是 \(x_2\)，依此类推）。证明以下修改，若应用于任意排序，都不会增加平均等待时间： • 如果 \(i < j\) 且 \(t(x_i) \geq t(x_j)\)，则交换顾客 \(i\) 与顾客 \(j\)。
例如，如果顾客排序为 \(3, 1, 4, 2\) 且 \(t(3) \geq t(4)\)，则取 \(i = 1\) 和 \(j = 3\) 应用此规则后得到新排序 \(4, 1, 3, 2\)。
分析交换对哪些顾客的等待时间有影响。只有 \(i\) 和 \(j\) 之间的顾客（不含 \(i\)，含 \(j\) 之后的顾客？）的等待时间可能变化。计算交换前后这些顾客等待时间的变化量。
首先注意到交换 \(x_i\) 和 \(x_j\) 不影响顾客 \(x_1, x_2, \ldots, x_i\) 和顾客 \(x_{j+1}, x_{j+2}, \ldots, x_n\) 的等待时间（即对于 \(k \leq i\) 或 \(k > j\) 的顾客 \(x_k\)）。因此我们只需处理顾客 \(x_{i+1}, \ldots, x_j\)，即对于 \(i < k \leq j\) 的顾客 \(x_k\)。对于顾客 \(x_k\)，交换前的等待时间为 \[T_k = \sum_{1 \leq l < k} t(x_l),\] 交换后的等待时间为 \[T'_k = \sum_{1 \leq l < i} t(x_l) + t(x_j) + \sum_{i < l < k} t(x_l) = T_k - t(x_i) + t(x_j).\] 由于 \(t(x_i) \geq t(x_j)\)，有 \(T'_k \leq T_k\)，因此顾客 \(x_{i+1}, \ldots, x_j\) 的等待时间从不增加，所有顾客的平均等待时间在交换后也不会增加。
解答来源：dis05-sol.pdf · 10–11 · confidence: high
题面来源：dis05.pdf · 7 · confidence: high
考虑与 6(a) 相同的设定。设 \(u\) 为 (a) 中选出的排序，\(x\) 为任意其他排序。证明 \(u\) 的平均等待时间不大于 \(x\) 的平均等待时间——因此 (a) 中的答案是最优的。
令 \(i\) 为使得 \(u_i \neq x_i\) 的最小下标。利用 (b) 的结论，通过交换将 \(x\) 逐步转化为 \(u\) 而不增加平均等待时间。这本质上是一个交换论证（exchange argument）。
设 \(u\) 为 (a) 中的排序，\(x\) 为任意其他排序。令 \(i\) 为使得 \(u_i \neq x_i\) 的最小下标。令 \(j\) 为 \(x_i\) 在 \(u\) 中的下标，即 \(x_i = u_j\)，并令 \(k\) 为 \(u_i\) 在 \(x\) 中的下标。
易见 \(j > i\)。由 \(x\) 的构造可知 \(t(x_i) = t(u_j) \geq t(u_i) = t(x_k)\)，因此交换 \(x_i\) 和 \(x_k\) 不会增加平均等待时间。若持续这样做，最终可将 \(x\) 转化为 \(u\)。由于整个过程从不增加平均等待时间，\(u\) 是最优排序。
解答来源：dis05-sol.pdf · 11 · confidence: high
题面来源：dis05.pdf · 7 · confidence: high
考虑以下图（顶点 A–L 排列成网格，边权标注在原图各边上）：
A B C
D E F
G H I
J
K
L
[边权列表见原图]
3×3 网格 (A-I) 加下方 J-K-L 列，共 12 个顶点。Prim 算法前六条边: AB, BE, DE, EH, GH, HI。需重画完整网格图及所有边权。
来源：dis05.pdf · 8
从 \(A\) 开始，维护已访问集合。每次选择连接已访问集合与未访问集合的最轻边，若有多个则按字典序选择顶点。逐步追踪前六条边的选择过程。
AB, BE, DE, EH, GH, HI
解答来源：dis05-sol.pdf · 12 · confidence: high
题面来源：dis05.pdf · 8 · confidence: high
考虑与 7-1 相同的图。
3×3 网格 (A-I) 加下方 J-K-L 列，共 12 个顶点。Kruskal 前七条边: DE, GH, EH, CJ, JK, FK, HI。需重画完整网格图及所有边权。
来源：dis05.pdf · 8
将所有边按权值排序，依次选择不形成环的边。注意 Kruskal 算法选择的边可能远离起点，与 Prim 算法不同。
(DE, GH, EH, CJ, JK, FK, HI) 或 (DE, GH, EH, CJ, JK, HI, FK)
解答来源：dis05-sol.pdf · 12 · confidence: high
题面来源：dis05.pdf · 8 · confidence: high
对以下每个命题，证明或给出反例。始终假设 \(G = (V, E)\) 是无向连通图。除非特别说明，不要假设边权互不相同。
(a) 设 \(e\) 是 \(G\) 中任意一条最小权值边。则 \(e\) 必属于某棵 MST。
考虑 Kruskal 算法的行为。当 Kruskal 算法处理到最小权值边 \(e\) 时，\(e\) 的两个端点是否一定在不同的连通分量中？
真，\(e\) 会属于 Kruskal 算法产生的 MST。
解答来源：dis05-sol.pdf · 12 · confidence: high
题面来源：dis05.pdf · 8–9 · confidence: high
对以下每个命题，证明或给出反例。始终假设 \(G = (V, E)\) 是无向连通图。除非特别说明，不要假设边权互不相同。
(b) 如果 \(e\) 属于 \(G\) 的某棵 MST，则它必是 \(G\) 的某个割的最轻边。
设 \(e = (u, v)\)。考虑将 MST 去掉 \(e\) 后，从 \(u\) 出发可达的顶点集合作为割的一侧。这个割有什么性质？
真，设 \((u, v)\) 是该边。令割的一侧为 MST 中从 \(u\) 出发不使用边 \((u, v)\) 可达的所有顶点。如果该割有一条比 \((u, v)\) 更轻的边，我们就可以将该边加入 MST 并移除 \((u, v)\)。我们知道该边不在 MST 中，否则其两个端点都可以从 \(u\) 出发而不使用 \((u, v)\) 到达。
解答来源：dis05-sol.pdf · 12–13 · confidence: high
题面来源：dis05.pdf · 8–9 · confidence: high
对以下每个命题，证明或给出反例。始终假设 \(G = (V, E)\) 是无向连通图。除非特别说明，不要假设边权互不相同。
(c) 如果 \(G\) 有一个包含唯一最轻边 \(e\) 的环，则 \(e\) 必属于每棵 MST。
图含顶点 A, B, C, D, E, F，边 (B,E) 在某环中为唯一最轻边，在另一环中为最重边。边权: 部分边权为 1, 10, 5 等
来源：dis05.pdf · 9
考虑 \(e\) 是否可能在另一个环中是最重边。如果是，根据环性质（cycle property），\(e\) 不能属于任何 MST。尝试构造一个图使得 \(e\) 同时是两个环的公共边。
假。设 \(e\) 同时也是另一个环的最重边；那么我们知道 \(e\) 不可能属于 MST。具体地，在下图中，边 \((B, E)\) 满足此条件，但不会被加入图。
解答来源：dis05-sol.pdf · 13 · confidence: high
题面来源：dis05.pdf · 9 · confidence: high
对以下每个命题，证明或给出反例。始终假设 \(G = (V, E)\) 是无向连通图。除非特别说明，不要假设边权互不相同。
(d) 对任意 \(r > 0\)，定义 \(r\)-路径（\(r\)-path）为所有边权都小于 \(r\) 的路径。如果 \(G\) 包含一条从 \(s\) 到 \(t\) 的 \(r\)-路径，则 \(G\) 的每棵 MST 也必须包含一条从 \(s\) 到 \(t\) 的 \(r\)-路径。
使用反证法。假设 MST 不包含从 \(s\) 到 \(t\) 的 \(r\)-路径。考虑 \(G\) 中 \(r\)-路径上第一个 MST 无法通过 \(r\)-路径到达的顶点，分析加入下一条边后形成的环。
真。设 \(v_1, v_2, \ldots, v_n\) 表示 \(G\) 中从 \(s = v_1\) 到 \(t = v_n\) 的 \(r\)-路径。考虑最大的 \(i\) 使得 MST 包含一条从 \(s\) 到 \(v_i\) 的 \(r\)-路径，并假设对于矛盾有 \(i < n\)。则边 \((v_i, v_{i+1})\) 不在 MST 中。将该边加入 MST 会形成一个环，该环的所有边长必须小于 \(r\)，否则我们可以用 \((v_i, v_{i+1})\) 替换其中一条。因此存在一条从 \(v_i\) 到 \(v_{i+1}\) 从而从 \(s\) 到 \(v_{i+1}\) 的 \(r\)-路径，与初始假设矛盾。
解答来源：dis05-sol.pdf · 13–14 · confidence: high
题面来源：dis05.pdf · 9 · confidence: high
dis05.pdfdis05-sol.pdf