最小生成树。独特的最小边缘与非独特的证明
Minimum spanning tree. unique min edge vs non unique proof
所以我有一个练习，我应该证明或反驳：
1) 如果e是连通图G中的一条最小权重边使得不是所有的边都必然不同，那么G的每一个最小生成树都包含e
2) 与 1) 相同，但现在所有的边权重都不同。
好吧，凭直觉，我理解 1) 因为并非所有的边权重都是不同的，所以一个顶点可能有边 e 的路径，但也有另一条边 e_1 这样如果权重（e ) = weight (e_1) 则存在一棵不包含边 e 的生成树，因为该图是连通的。否则如果e_1和e都在最小生成树中，则有环
对于 2)，由于所有边的权重都是不同的，因此最小生成树当然会包含边 e，因为任何算法都会始终选择较小的路径。
有什么关于如何证明这两个的建议吗？就职？不确定如何处理。
实际上在你的第一个证明中，当你说如果 e 和 e_1 都在 G 中，那么就有一个循环，那是不正确的，因为它们是最小边，所以不必是一个循环，你确实需要将它们都包含在 MST 中，因为如果 |E| > 1 和 |V| > 2 那么他们都必须在那里。
无论如何，第一个的反例是一个完整图，所有边的权重都与 e 相同，MST 将仅包含 |V|-1 条边，但您没有包括所有其他边同样的重量，所以你有一个矛盾。
至于第二个，如果所有边都是不同的，那么如果你删除最小边并想要重建 MST，唯一的方法是添加一条连接 2 个不相交集的边被那个最小重量的边缘打碎了。
现在假设您没有删除最小权重边，而是添加了另一条边，现在您已经创建了一个循环，并且由于所有边都是不同的，因此创建循环的边将大于所有它们，因此，如果您从该循环中删除任何以前的 MST 边缘，它只会增加 MST 的大小。这意味着当所有边都具有不同的权重时，几乎所有以前的 MST 边都是关键的。
所以我有一个练习，我应该证明或反驳：
1) 如果e是连通图G中的一条最小权重边使得不是所有的边都必然不同，那么G的每一个最小生成树都包含e
2) 与 1) 相同，但现在所有的边权重都不同。
好吧，凭直觉，我理解 1) 因为并非所有的边权重都是不同的，所以一个顶点可能有边 e 的路径，但也有另一条边 e_1 这样如果权重（e ) = weight (e_1) 则存在一棵不包含边 e 的生成树，因为该图是连通的。否则如果e_1和e都在最小生成树中，则有环
对于 2)，由于所有边的权重都是不同的，因此最小生成树当然会包含边 e，因为任何算法都会始终选择较小的路径。
有什么关于如何证明这两个的建议吗？就职？不确定如何处理。
实际上在你的第一个证明中，当你说如果 e 和 e_1 都在 G 中，那么就有一个循环，那是不正确的，因为它们是最小边，所以不必是一个循环，你确实需要将它们都包含在 MST 中，因为如果 |E| > 1 和 |V| > 2 那么他们都必须在那里。
无论如何，第一个的反例是一个完整图，所有边的权重都与 e 相同，MST 将仅包含 |V|-1 条边，但您没有包括所有其他边同样的重量，所以你有一个矛盾。
至于第二个，如果所有边都是不同的，那么如果你删除最小边并想要重建 MST，唯一的方法是添加一条连接 2 个不相交集的边被那个最小重量的边缘打碎了。
现在假设您没有删除最小权重边，而是添加了另一条边，现在您已经创建了一个循环，并且由于所有边都是不同的，因此创建循环的边将大于所有它们，因此，如果您从该循环中删除任何以前的 MST 边缘，它只会增加 MST 的大小。这意味着当所有边都具有不同的权重时，几乎所有以前的 MST 边都是关键的。