algorithm - 最小生成树。独特的最小边缘与非独特的证明

Question

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

1) 如果e是连通图G中的最小权边使得不是所有的边都必然不同，那么G的每一个最小生成树都包含e

2) 与 1) 相同，但现在所有的边权重都是不同的。

---

好吧，凭直觉，我理解对于 1) 因为并非所有的边权重都是不同的，所以一个顶点可能有边 e 的路径但也有另一条边 e_1 这样如果 weight(e) = weight (e_1)然后有一个生成树不包含边 e 因为图是连接的。否则如果e_1和e都在最小生成树中，则有环

对于 2)，由于所有边的权重都是不同的，因此最小生成树当然会包含边 e，因为任何算法都会始终选择较小的路径。

关于如何证明这两者有什么建议吗？就职？不确定如何处理。

Answer 1

实际上，在你的第一个证明中，当你说如果 e 和 e_1 都在 G 中，那么就有一个循环，那是不正确的，因为它们是最小边，所以不一定有一个循环，而且你确实需要将它们都包含在 MST 中，因为如果 |E| > 1 和 |V| > 2 那么他们都必须在那里。

无论如何，第一个的反例是一个完整的图，所有边的权重都与 e 相同，MST 将只包含 |V|-1 条边，但你没有包括它的所有其他边相同的重量，因此你有一个矛盾。

至于第二个，如果所有边都是不同的，那么如果你删除最小边并想要重建 MST，唯一的方法是添加一条边连接 2 个断开的不相交集由那个最小重量边上升。

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