找到 minimum-weight 个跨越给定最小生成树的完整图

Question

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

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

跨越T的minimum-weight完整图G如下：

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

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 边的切割。此切割的任何未知 non-MST 边缘的权重应为 w_i + 1。

问题：

1）以上算法是否正确？根据Cut属性，应该是。

2) 我可以做得更有效率吗？我没有算法可以在我的头顶找到切口，但我觉得这种方法效率不高。

edit：我想到的另一种方法是基于 Kruskal 算法的方法：

1）使用一个Union-Find，我遍历了所有的MST边，通过递增的cost，将相应的顶点统一在同一个组件下。

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.

算法：

使用 |V| 个单例组件初始化联合查找。
按权重升序对 T 的所有边进行排序。运行时间：O(|V| * log|V|).
迭代 T 的下一条边 e = (v1,v2)。将其权重 w_e 添加到 w_total.
在 Union-Find 中查找 v1 和 v2 的组件：set1、set2，包含 size1 和 size2 个顶点，分别为
这些组件将被统一。由于 G 是一个完全图，因此将添加 size1 × size2 条边：一条边是 MST e 条边，所有其他边都必须比 e 重，因此 Kruskal 算法会忽略它们。因此，它们的最小重量应至少为 w_e + 1.
w_total += (size1 × size2 - 1) × (w_e + 1).
统一两个组件set1和set2。
从步骤 2 开始重复下一个 MST 边缘 e。

运行时间：O(|V| * log|V|).

如果问题变成：详细列出完整图的所有边e = (v1, v2)及其权重w，我们只需要做，在步骤6和[=37之间=]:

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.

找到 minimum-weight 个跨越给定最小生成树的完整图

Find minimum-weight complete graph that spans a given minimum spanning tree

algorithm

graph

minimum-spanning-tree