證明，沒有最小生成樹包含最大加權邊緣

比方說，有圖G，使得它的所有邊緣都對應於不同的整數權重。所以沒有兩個邊緣具有相同的重量。設E是G的所有邊。令emax爲E中具有最大權重的邊。 Graph G的另一個性質是每條邊e屬於G中的某個循環。我必須證明沒有G的最小生成樹包含邊emax。我不得不證明G的最小生成樹不包含邊emax。證明，沒有最小生成樹包含最大加權邊緣

我明白爲什麼這是真的，因爲所有的邊是不同的，每邊屬於一個週期，最小生成樹算法可以簡單地選擇邊緣與包含EMAX週期較低的權重。但我不確定如何具體證明它。

來源

2013-11-27 user65663

http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cycle_property – Geobits

這種類型的參數在證明一般結構的最優性屬性中非常有用，稱爲剪切和粘貼參數。您可以在CLRS中閱讀更多信息。 – sukunrt

謝謝大家，現在很簡單，我知道這一點 – user65663

這與the Cycle Property of the Minimum Spanning Tree有關，這基本上是說，給定圖中的一個循環，權重最大的邊不屬於MST（通過上面鏈接中的矛盾很容易證明）。因此由於邊緣emax屬於週期它不能處於MST。

來源

2013-11-27 17:36:09 Dimitris

反證法在這裏工作。假設你有一個包含最大邊緣的最小生成樹。如果刪除該邊緣，則有兩個組件不再彼此連接。每個頂點都在一個組件或另一個組件中。有一個循環包括最大邊緣。從最大邊的一側開始，沿着循環移動。因爲您最終將循環到另一個組件的最大邊的另一邊，您會發現 - 在此之前 - 在其中一個斷開組件中有一個頂點，另一個斷開組件中有一個頂點的邊。由於組件斷開連接，因此邊緣不在最小生成樹中。通過將它添加到樹中，重新連接這些組件，並創建一個最小生成樹，其重量比您開始時的重量要小 - 因此您原始的最小生成樹不是最小值。

來源

2013-11-27 17:40:38 mcdowella

難道一個MST包含的最大重量的優勢？

有時候是。這取決於圖的類型。如果具有最大權重的邊是連接圖的組件的唯一橋，那麼該邊也必須存在於MST中。

來源

2015-01-07 13:08:54 Prabhakar

證明，沒有最小生成樹包含最大加權邊緣

回答

相關問題