使特定節點的程度最小化的最小生成樹

Question

我們如何找到使節點度數最小的最小生成樹v（在所有最小生成樹中）？

會修改Kruskal算法，使得如果有幾個邊具有相同的重量，我們選擇不接觸的那個v解決問題？

Answer 1

要回答這個問題的一部分，修改克魯斯卡爾算法的草圖在問題中並不能解決問題。考慮圖G=(V,E,w)其中

V = {1,2,3}, 
E = {{1,2}, {2,3}, {3,1}}, 
w({1,2}) = 1, 
w({1,3}) = 1, 
w({2,3}) = 2 

和1是在最小生成樹程度要被最小化的節點。然後，邊緣設置

S1={{1,2},{1,3}} 

構成重量2的最小生成樹。然而，Kruskal算法的修改版本將不失一般性地選擇邊緣{1,2}，這將導致{1,3}被禁止，使得{2,3}被選擇。總之，在所選擇的邊緣設置

S2={{1,2},{2,3}} 

節點1具有更小的程度比在S2，但S2總重量爲3，這意味着它不構成最小生成樹。

此外，注意的是，節點v這是要被最小化的程度必須是至少3具有最小生成樹v多於一個鄰域的可能性。

在詳盡的搜索中，請選擇任何可能的v附近區域。由於v最多隻有n鄰居，所以最多有2^n這樣的鄰居。使用Prim算法，將其中的每一個擴展到生成樹，這對於包含所選擇的v的鄰域來說成本最小;在所有這些成本最小的解決方案中，選擇其中v的程度被最小化的一個。但是，該方法不會產生多項式時間算法。