我需要证明，给定一个连通图，每个边都有不同的权重，每个生成树（最小生成树除外）都有一个相邻的权重较小的生成树。w(T') < w(T)，其中 T' 与生成树 T 相邻。
我坚持证明与 MST 相邻的每个 ST 都有相邻的生成树（实际上是 MST）。如何使用任何非 MST 相邻生成树来显示这一点？
user6338331
问问题
169 次
1 回答
1
Kruskals 算法的证明回答了你的问题。 http://people.qc.cuny.edu/faculty/christopher.hanusa/courses/634sp12/Documents/KruskalProof.pdf
让 T 成为您的 MST，N 成为您的非生成树。由于 N!=T，在 T 中找到一条不在 N 中的最小权重的边 e。
N+e 有一个循环，其中 e 是循环的一部分，并且循环上必须有一个 e'，使得 wt(e)
所以构造 N'=Ne'+e。显然 wt(N1)
于 2017-04-18T23:03:09.920 回答