有關最小生成樹的基本問題

Question

這不是一項家庭作業。我正在嘗試從教科書中練習以瞭解MST (minimum spanning tree)。

假設我在一個帶權無向圖G中有一個循環C。據我瞭解，以下是正確的：

• 在C的重邊緣屬於沒有 MST的G。也就是說，有沒有 MST G，其中包含該邊緣。
• 在C的最輕邊緣屬於的G一些 MST。也就是說，存在G的MST，其包含該邊緣。

現在我想知道下面的說法是否正確。

• 的最輕C邊緣屬於所有 MST的G。即否G的MST，其不包含該邊緣。
• C任何邊緣除最重一個屬於一些 MST。也就是說，對於C中除最重的之外的每條邊都有一個包含該邊的MST。

你能證明最後的說法嗎？

Answer 1

即使對於第一個索賠，如果有多個最輕的邊緣，都不需要包含在MST中。

Answer 2

你的第一個要求永遠是對的。最輕的邊緣在任何圖形的MST上。

第二個不總是如此。如果整個圖形是一個 週期，並且每個節點都有2個邊緣出現，則總是如此。然而，在一般情況下，重量k的 邊緣(u,v)是從未上MST每當有節點u和v 它們在總重量小於k連接之間的路徑。

Answer 3

我不認爲你的聲明是有效的。問題在於你只考慮更大圖中的一個循環。

例如考慮一個圖G，其由一個週期中的6個節點組成（其中隨機權重> 1）。您的要求可能適用於該圖，但現在在圖的中心添加1個節點，並將其與6個成本爲1的鏈接連接。現在，整個圖的MST將僅包含這6個邊（它們組成一顆星）。

如果你現在看看你的權利，你會看到：

• 在你的週期最輕的邊緣不屬於MST（=星）在週期
• 無邊緣的位置是在MST中