查找跨越給定的最小生成樹的最小權重完整圖形

Question

讓T =（V，E）是|V|頂點樹和|E| = |V-1|邊，具有已知成本。我們要構建一個最小權重完整圖G =（V，E'）跨越牛逼其獨特的最小生成樹。

示例：考慮以下樹T。 紅色的邊緣有給定的成本。虛線邊將被添加以構造來自該樹的完整圖。

最小重量完全圖摹跨越牛逼其獨特的MST如下：

---

我試圖找到一個（多項式時間）算法來生成該圖。我期待的主要是小費，而不是完整的解決方案。到目前爲止，我已經設計了以下算法：

1）查找包含重量爲w_max的最重MST邊緣並且沒有其他MST邊緣的圖的切口。所有其他邊緣必須是w_max + 1。下面的圖片說明了我的想法：

邊緣（1--2）（1--4），（4-5），（2-3）和（2--5 ）包含在此切割C中。包含在MST中的唯一邊緣是邊緣（2--3），它​​是MST中最重的邊緣，其中w=56。因此，所有其他邊緣應該有w=57。證明：假設相反;我們可以用另一條邊代替（2-3），並保持樹連接。現在樹的重量更輕，因此（2-3）不屬於MST。矛盾。

2）對重量遞減順序的重量爲w_i的MST的所有其他邊緣e_i重複。採取只包括e_i，並沒有其他MST邊緣的剪輯。此切割的任何未知非MST邊緣應具有w_i + 1的權重。

---

問題：

1）是上述算法是否正確？根據Cut屬性，它應該是。

2）我能更有效地做到這一點？我沒有一個算法來尋找我的頭頂上的切割，但我不覺得這種方法可能是有效的。

---

編輯：另一種方法，我曾在我的腦海裏是一個基於Kruskal算法的方法：

1）使用聯盟查找，我遍歷所有MST邊緣，按升序成本，統一相同組件下的相應頂點。

2）在每個步驟中，通過成本邊緣w來統一兩個不同的組件。在相同（新）組件中形成循環的任何其他邊緣的成本應爲w+1。

Answer 1

回答我的問題

下面是一個有效的答案，我想出來的，也是繼從@sasha反饋。 假設我們想計算完整圖G的總權重，

設T =（V，E）爲| V |頂點和| E | = | V | -1邊，已知權重。計算跨越T作爲其唯一最小生成樹的最小權重完整圖G =（V，E'）的總權重w_total。 NB：邊權重是自然數。

算法：

1. 初始化與|V|單組分聯盟查找。
2. 按照遞增的權重對T的所有邊進行排序。運行時間：O（| V | * log | V |）。
3. 遍歷T的下一個邊緣e = (v1,v2)。將其重量w_e增加到w_total。分別set2set1，含size1和size2頂點：
4. 查找v1的和v2的在聯盟中找到的成分。
5. 這些組件將被統一。由於G是一個完整的圖形，因此將增加size1 × size2邊：一條邊是MST e邊，所有其他邊必須比e更重，以便Kruskal的算法將忽略它們。因此，他們的最小重量應至少爲w_e + 1。
6. w_total += (size1 × size2 - 1) × (w_e + 1)。
7. 統一兩個組件set1和set2。
8. 從步驟2重複下一個MST邊緣e。

運行時間：O（| V | * log | V |）。

---

如果問題變成了：詳細列出所有邊緣完全圖的e = (v1, v2)及其權重w，我們只需要做，之間步驟6和7：

for all vertices v1 in set1 
    for all vertices v2 in set2 
    create edge e = (v1, v2); ignore if edge is the MST edge 
    w_e = w_mst_edge + 1 

所以運行時間變爲O（| E | + | V | * log | V |）= O（| V |^2），因爲我們有| E | = | V | *（| V | -1）/ 2邊的完整圖G。