最小生成树。唯一最小边与非唯一证明

Question

所以我有一个练习，我应该证明或反驳：

1）如果e是连通图G中的一个最小权边，使得不一定所有边都是不同的，则G的每一个最小生成树都包含e

关于如何证明这两个问题，有什么建议吗？归纳法？不知道怎么接近。

Answer 1

实际上，在第一个证明中，如果e和E1都在G中，那么有一个循环，那不是真的，因为它们是最小边，所以不一定有循环，你需要把它们都包括在MST中，因为如果e>1和V>2，那么它们都必须在那里。

不管怎样，第一个例子的反例是一个完整的图，所有边的权重都和e一样，MST只包含V-1个边，但你没有包含所有其他的权重相同的边，所以你有一个矛盾。

至于第二个，如果所有的边都是不同的，那么如果你删除最小边并想重建MST，唯一的方法是添加一个边，连接被最小权边分割的两个不相交集。

现在假设您没有删除那个最小权重的边，而是添加了另一个边，现在您已经创建了一个循环，由于所有的边都是不同的，创建循环的边将大于所有的边，因此如果您从那个循环中删除任何以前的MST边，它只会增加MST的大小。这意味着当所有边都有不同的权重时，几乎所有以前的MST边都是关键的。