证明一个 属性 的最小生成树
Prove a property of Minimum Spanning Tree
我需要你的帮助来证明以下几点：
G=(V,E)是一个无向连通图，边上有非负的权值。
设 T 是 G 的 MST，T' 是 G 的生成树（不是最小生成树），因此它认为 Weight(T') > Weight(T)。证明 T' 中最重边的权重不小于 T.
中最重边的权重
我不确定如何处理这个问题，如果我们让 e(u,v) - heaviest edge on T 和 e'(u',v') - heaviest edge on T'，然后如果我们查看 (u,u') 定义的切割，我们可以使用 Kruskal 算法并表明 e' 没有被选择在 T 或这个方向的东西...
谢谢，
我会选择另一个方向。为简单起见，让所有的边权重不同，这样 MST 是唯一的。考虑 MST 中最重的边 e，以及 Kruskal 算法构造此 MST 的方式。最后添加的边是生成的 MST 中最重的边。
现在看看添加最后一条边之前的情况。我们有一个由两棵树组成的森林。当我们使用 Kruskal 算法时，目前没有比 e 更便宜的方法来连接这两棵树。因此，在任何其他生成树中它们之间的任何边的权重至少与 e 一样大。
重量相等的边需要一些小心，或者可能是一个聪明的想法，才能妥善处理。
假设相反——存在一个带最小生成树T和生成树T'的加权无向图，使得T的最重边比T'的最重边重，即最重边T 的重于 T' 中的 every 边。考虑通过删除 T 的最重边 h 引起的切割。由于 T' 是连通的，因此 T' 中的某些边穿过该切割。如果我们将这条边添加到 T - h 中，我们会得到一棵比 T 更轻的生成树，这是一棵最小生成树。矛盾。
我需要你的帮助来证明以下几点：
G=(V,E)是一个无向连通图，边上有非负的权值。
设 T 是 G 的 MST，T' 是 G 的生成树（不是最小生成树），因此它认为 Weight(T') > Weight(T)。证明 T' 中最重边的权重不小于 T.
我不确定如何处理这个问题，如果我们让 e(u,v) - heaviest edge on T 和 e'(u',v') - heaviest edge on T'，然后如果我们查看 (u,u') 定义的切割，我们可以使用 Kruskal 算法并表明 e' 没有被选择在 T 或这个方向的东西...
谢谢，
我会选择另一个方向。为简单起见，让所有的边权重不同，这样 MST 是唯一的。考虑 MST 中最重的边 e，以及 Kruskal 算法构造此 MST 的方式。最后添加的边是生成的 MST 中最重的边。
现在看看添加最后一条边之前的情况。我们有一个由两棵树组成的森林。当我们使用 Kruskal 算法时，目前没有比 e 更便宜的方法来连接这两棵树。因此，在任何其他生成树中它们之间的任何边的权重至少与 e 一样大。
重量相等的边需要一些小心，或者可能是一个聪明的想法，才能妥善处理。
假设相反——存在一个带最小生成树T和生成树T'的加权无向图，使得T的最重边比T'的最重边重，即最重边T 的重于 T' 中的 every 边。考虑通过删除 T 的最重边 h 引起的切割。由于 T' 是连通的，因此 T' 中的某些边穿过该切割。如果我们将这条边添加到 T - h 中，我们会得到一棵比 T 更轻的生成树，这是一棵最小生成树。矛盾。