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

Question

设 T = (V, E) 是一棵 |V| 顶点和 |E| 的树= |V-1| 边，成本已知。我们想要构建一个最小权重的完整图G = (V, E')，它跨越T作为它唯一的最小生成树。

示例:考虑下面的树T。 红色 的边具有给定的成本。将添加虚线边以从这棵树构建完整的图。

跨越 T 作为其唯一 MST 的最小权重完整图 G 如下:

---

我正在尝试找到生成此图的(多项式时间)算法。我主要是在寻找提示，而不是完整的解决方案。到目前为止，我已经设计了以下算法:

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) 使用 Union-Find，我通过递增成本迭代所有 MST 边，并统一同一组件下的相应顶点。

2) 在每个步骤中，两个不同的组件通过成本边 w 统一。在同一(新)组件内形成循环的任何其他边的成本应为 w+1。

Answer 1

回答我自己的问题

这是我根据@sasha 的反馈得出的有效答案。假设我们要计算完整图G的总权重，即；

Let T = (V, E) be a tree of |V| vertices and |E| = |V|-1 edges, with known weights. Calculate the total weight w_total of the minimum-weight complete Graph G = (V, E') that spans T as its unique minimum spanning tree. NB: edge weights are natural numbers.

算法:

1. 使用 |V| 单例组件初始化 Union-Find。
2. 按权重升序对T 的所有边进行排序。运行时间:O(|V| * log|V|)。
3. 迭代 T 的下一条边 e = (v1,v2)。将其权重 w_e 添加到 w_total。
4. 在Union中查找v1和v2的组件-查找:set1,set2,分别包含 size1 和 size2 顶点。
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 中的边。