最小生成树只有2等于边缘

Question

假设有一个无向加权图ģ，具有不同的边缘晕死但仅在两个边缘：w(e1)=w(e2)

我必须证明G具有至多一个最小生成树包含e1的树。 另外我必须证明G最多只有一个最小生成树，它不包含e1。

我只需要第一个解决方案，并将解决第二个单独。

感谢

Answer 1

为了解决第1部分：

考虑通过删除给G e1得到图（也可能是它的一个顶点，如果它现在没有连接到图形的其余部分），让我们称之为G'。

在此图（G'）中，全部边缘权重不同。

现在假设G有超过1个MST，其中包括e1 - 它们都是G'的不同MST。

现在的技巧是有一个定理，在这种图（所有边是不同的），MST是唯一的。请参阅证明here。

编辑：您可能只需从链接中获取证明并对您的案例稍作编辑即可。