是否存在不包含最小/最大加權邊緣的最小生成樹？

Question

如果我們有一個（任意的）連接的無向圖G，其邊緣具有不同的權重，

1. 確實的G每MST包含最小加權邊緣？
2. 是否有G的MST不包含最大加權邊緣？

此外，如果有人能夠提供關於在處理此類MST問題時必須記住的關鍵事項，我更感激。

這是一個家庭作業問題。謝謝。

Answer 1

是否有G的MST不包含最大加權邊？

可能有，但並不一定如此。考慮如下的4頂點圖：

[A]--{2}--[B] 
|   | 
|   | 
{1}  {3} 
|   | 
|   | 
[C]-{50}--[D] 

最小生成樹由邊集{CA，AB，BD}組成。沿{CD}的最大邊權重爲50，但它不是MST的一部分。但是如果G已經等於它自己的MST，那麼顯然它將會包含它自己的最大邊緣。

確實的G每MST包含最小加權邊緣？

是的。 MST有切割屬性。 A cut只是將圖的頂點劃分成兩個不相交的集合。對於任何可以進行的切割，如果該切割中邊緣的重量小於切割中其他邊緣的重量，則該邊緣屬於圖形中的所有MST。因爲你保證邊權重是不同的，所以你也保證有一個比所有其他邊更小的邊。

此外，如果有人能夠提供關於在處理這些MST問題時必須記住的關鍵事項，我更感激。

最好的辦法是推理一般情況下使用MST的屬性，並嘗試構建您認爲將證明您的情況的特定反例。我給出了上面每條推理的一個實例。由於切割和循環屬性，您始終可以確定MST中的哪些邊緣，因此您可以系統地測試每個邊緣以確定它是否在MST中。

Answer 2

對於第一個問題，答案是否定的，kruskal's algorithm證明了這一點。它將始終選擇最低的成本優勢。

對於第二個問題的答案是肯定的，並且是微不足道的發現的示例曲線圖：因爲它引入了一個週期

1 - 2 (cost 10) 
2 - 3 (cost 100) 
3 - 1 (cost 1000) 

第三邊緣絕不會被選中。因此，基本上，如果插入MST的成本最高的邊將創建一個循環，它將不會被插入。

Answer 3

G的每個MST是否包含最小加權邊？

是的。讓我們假設我們有一個MST它不包含最小權重邊緣。現在將此邊緣加入MST將產生cycle。現在在cycle中總是會有另一個邊緣，它可以被移除以去除週期並仍然保持連接的圖形（MST）。

G是否存在不包含最大加權邊的MST？

取決於圖表。如果本身是一棵樹，那麼我們需要在MST中包含其所有n-1邊緣，因此不能排除最大加權邊緣。同樣，如果最大加權邊沿是cut-edge，以便其排除不會導致連通性，那麼不能排除最大加權邊沿。但是，如果最大重量邊緣是cycle的一部分，那麼可以從MST中排除。

Answer 4

我看到你也正在爲CSC263通過2009考試學習嗎？ （！我也一樣）

另一種方式看，最低總是在MST是在這個最小邊簡單地看（稱之爲E）：

  e 
v1 ---------------- v2 

（假設這有連接到其他verticies）。現在，對於不包含在最後的MST平均值中的我們而言，在不失一般性的情況下，我們在MST中具有v1，但不是v2。但是，添加v2而不添加e的唯一方法就是說v1的添加不會將e添加到隊列中（因爲根據定義，e會位於隊列的頂部，因爲它具有最低的優先級），但是此與MST構造定理相矛盾。

所以基本上，不可能有最小權重的邊不能進入隊列，這意味着任何構建的MST都會擁有它。