尋找具有不同權重的連通圖的MST

Question

我們都知道存在諸如kruskal's和prim的MST算法的算法來查找連通圖的MST（最小生成樹）。

我知道的另一種方法是從圖中的每個循環中刪除具有最大值的邊緣，直到沒有更多循環。結果圖將是MST。我不確定的問題是，如果連接圖具有不同的權重，那麼圖中每個週期的最小邊將包含在圖的每個MST中？我們能夠證明/反駁這個嗎？

Answer 1

我設法找到了MST回答這個維基百科頁面上：

最低成本邊緣

如果圖的最小代價邊e是 唯一的，那麼此邊緣包含在任何MST中。證明：如果e未包含在MST中，則刪除在向MST添加e之後形成的週期中的任何（更大的 成本）邊緣將產生具有較小權重的生成樹。