查找最小生成樹是否包含線性時間的邊沿？

Question

我有我的功課以下問題：

舉一個O（N + M）算法來找到一個邊e是否會是一個圖

的MST的一部分（我們被允許在這項任務上得到別人的幫助，所以這不是作弊。）

我認爲我可以做一個BFS並且發現這個邊緣是否是兩層之間的邊緣，如果是這樣的話，這些層次中最小。但是，當這條邊不是BFS樹的樹邊時，我該說些什麼呢？

Answer 1

作爲一個提示，如果一個邊不是包含它的任何循環中最重的邊，那麼就有一些包含該邊的MST。要看到這個，考慮任何MST。如果MST已經包含邊緣，太棒了！我們完成了。如果不是，則將該邊添加到MST中。這會在圖形中創建一個循環。現在，找到那個週期中最重的邊緣，並將其從圖中移除。所有東西現在仍然連接在一起（因爲如果兩個節點曾經通過穿過邊緣的路徑連接，現在它們可以通過以其他方式繞過週期來連接）。此外，由於邊緣的成本被刪除並不小於邊緣的成本（因爲邊緣不是週期中最重的邊緣），所以該樹的成本不能大於之前。由於我們從MST開始，因此我們必須以MST結束。

使用此屬性，查看您是否可以找到邊緣是否是線性時間內任何週期上最重的邊緣。

Answer 2

查找是否有任何路徑比當前創建一個循環到u和v的當前（u，v）更便宜。如果是，則（u，v）不在mst上。否則是。這可以通過切割屬性和循環屬性來證明。

Answer 3

我們將使用MST cycle property來解決這個問題，它說：「對於圖中的任何循環C，如果C的邊e的權重大於C的所有其他邊的權重，則該邊不能屬於到MST「。

現在，運行以下O(E+V)算法以測試連接頂點u和v的邊E是否是某個MST的一部分。

步驟1

運行從端點中的一個的DFS（U或V）的緣部E僅考慮具有重量小於E.

的

步驟那些邊緣的2

案例1 如果在這個DFS，頂點u的結束和v得到連接，然後邊e不能是一些MST的一部分。這是因爲在這種情況下，圖E中肯定存在一個循環，其中邊E具有最大權重，並且它不能成爲MST的一部分（來自循環屬性）。

案例2 但是，如果在DFS結束u和v留斷開連接，然後邊e一定是有MST的一部分，在這種情況下，E不是總是所有周期的最大重量邊緣它是一部分。