使特定节点的程度最小化的最小生成树

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的程度被最小化的一个。但是，该方法不会产生多项式时间算法。