algorithm - 是不是: all edge weights are positive,那么任何连接所有顶点并且具有最小总重量的必须是最小生成树？

Question

这道题是从算法导论的习题23.1-7演化而来的。

原问题是:

23.1-7争论如果一个图的所有边权重都是正的，那么连接所有顶点并且具有最小总权重的边的任何子集必须是一棵树。举例说明，如果我们允许某些权重为非正数，则不会得出相同的结论。

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

我的推论正确吗？如果不是，请给我一个反例。

Answer 1

我认为你的推论等同于要求你证明的命题。生成树是边的子集，因此所有顶点都没有任何循环地连接(因此它是一棵树)。如果它是最小生成树，则边的总权重最小。

所以是的，你的推论是正确的，但你没有证明这个陈述。提示:树不包含任何循环，因此尝试通过假设您有一个子集连接所有具有循环的最小总权重的顶点来进行反证法证明。