algorithm - 证明最小生成树的性质

Question

我需要您的帮助来证明以下内容:G=(V,E) 是一个边上有非负权重的无向连通图。设 T 是 G 的 MST，T' 是 G 的生成树(不是最小生成树)所以它认为 Weight(T') > Weight(T)。证明T'中最重边的权值不小于T中最重边的权值。

我不确定如何处理这个问题，如果我们让 e(u,v) - T 上最重的边 和 e'(u',v') - 最重的边T' 上的边缘，然后如果我们查看由 (u,u') 定义的切割，我们可以使用 Kruskal 算法并证明 e' 不是' t 选择在 T 或这个方向的某个地方...

谢谢，

Answer 1

假设相反——存在一个带最小生成树 T 和生成树 T' 的加权无向图，使得 T 的最重边比 T' 的最重边重，即 T 的最重边比 T' 中的所有 边都重。考虑通过删除 T 的最重边 h 引起的切割。由于 T' 是连通的，因此 T' 中的某些边穿过该切割。如果我们将这条边添加到 T - h 中，我们会得到一棵比 T 更轻的生成树，这是一棵最小生成树。自相矛盾。