Show that if an edge (u, v) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph.
(u, v) 属于最小生成树 A, 假设 cut 不影响 A 中除 (u, v) 外的其他边, 既 A 中只有 (u, v) 穿过该 cut,
所以 (u, v) 对该 cut 是最轻边, 否则 (u, v) 不属于 A.
Exercises 23.1-4
Give a simple example of a connected graph such that the set of edges { (u, v) : there exists a cut (S, V - S) such that (u, v) is a light edge crossing (S, V - S) } does not form a minimum spanning tree.
三角形三条边权重相同的情况, 每条边在某种 cut 中均是最轻, 既结果中存在环, 所以不是最小生成树.
Exercises 23.1-5
Let e be a maximum-weight edge on some cycle of connected graph G = (V, E). Prove that there is a minimum spanning tree of G‘ = (V, E - {e}) that is also a minimum spanning tree of G. That is, there is a minimum spanning tree of G that does not include e.
因为在某些圈中 e 是权重最大的边, 去掉 e 后圈中的顶点仍然可连通. 假设最小生成树 A 中不包含 e, 边集合 是 T, 同样假设包含 e 的情况, 边集合为 T‘, 既 T‘ 是 T 去除某条边 x, 并加入 e. (最小生成树边数是常量 V-1)
w(T‘) = w(T) - w(x) + w(e),
>= w(T)
所以可知最小生成树 A 不包含 e.
Exercises 23.1-6
Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. Show that the converse is not true by giving a counterexample.
假设存在两个最小生成树 T 和 T‘. 任何边 e 属于 T, 如果从 T 中移除 e, 则 T 变得不连通, 形成 cut (S, V - S), 根据练习 23.1-3 可知, e 是穿过 cut(S, V - S) 最轻边. 假设边 x 属于 T‘, 并穿过 cut (S, V - S), 则 x 同样是最轻边. 由于穿过 cut(S, V - S) 的最轻边唯一. 既 e 和 x 是同一条边. 所以 e 也属于 T‘, 由于我们选择 e 是任意的, 所有在 T 中的边, 同样在 T‘ 中. 既最小生成树唯一.
将条件和结论调换则不成立, 如下.
