是對的：所有邊權重都是正數，那麼連接所有頂點並且總重量最小的任何邊權都必須是最小生成樹？

Question

這個問題是從演練23.1-7演變而來的算法介紹。

原來的問題是：

23.1-7 認爲，如果一個圖的所有邊緣權重是肯定的，那麼邊緣的任意子集，連接所有的頂點和具有最小的總重量必須爲樹。舉一個例子來說明，如果我們允許一些權重是非正的，那麼同樣的結論就不會遵循。

但我認爲如果圖的所有邊權重都是正數，那麼連接所有頂點並且具有最小總權重的邊的任何子集都必須是最小生成樹。

是我的必然嗎？如果沒有，請給我一個反例。

Answer 1

我認爲你的推論等同於你被要求證明的陳述。生成樹是邊的一個子集，所有頂點都沒有任何週期連接（所以它是一棵樹）。如果它是最小生成樹，那麼邊的總權重最小。

所以，你的推論是正確的，但你沒有證明這一說法。提示：一棵樹不包含任何循環，所以嘗試通過假設你有一個子集連接所有具有最小總重量並具有一個循環的頂點來反證。