是对的：所有边权重都是正数，那么连接所有顶点并且总重量最小的任何边权都必须是最小生成树？

Question

这个问题是从演练23.1-7演变而来的算法介绍。

原来的问题是：

23.1-7 认为，如果一个图的所有边缘权重是肯定的，那么边缘的任意子集，连接所有的顶点和具有最小的总重量必须为树。举一个例子来说明，如果我们允许一些权重是非正的，那么同样的结论就不会遵循。

但我认为如果图的所有边权重都是正数，那么连接所有顶点并且具有最小总权重的边的任何子集都必须是最小生成树。

是我的必然吗？如果没有，请给我一个反例。

Answer 1

我认为你的推论等同于你被要求证明的陈述。生成树是边的一个子集，所有顶点都没有任何周期连接（所以它是一棵树）。如果它是最小生成树，那么边的总权重最小。

所以，你的推论是正确的，但你没有证明这一说法。提示：一棵树不包含任何循环，所以尝试通过假设你有一个子集连接所有具有最小总重量并具有一个循环的顶点来反证。