查找跨越给定的最小生成树的最小权重完整图形

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。