最小生成樹只有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。

編輯：您可能只需從鏈接中獲取證明並對您的案例稍作編輯即可。