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

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

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

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

跨越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.

回答我自己的问题

这是我根据@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| 个单例组件初始化联合查找。
  2. 按权重升序对 T 的所有边进行排序。 运行 时间:O(|V| * log|V|).
  3. 迭代 T 的下一条边 e = (v1,v2)。将其权重 w_e 添加到 w_total.
  4. 在 Union-Find 中查找 v1v2 的组件:set1set2,包含 size1size2 个顶点,分别为
  5. 这些组件将被统一。由于 G 是一个完全图,因此将添加 size1 × size2 条边:一条边是 MST e 条边,所有其他边都必须比 e 重,因此 Kruskal 算法会忽略它们。因此,它们的最小重量应至少为 w_e + 1.
  6. w_total += (size1 × size2 - 1) × (w_e + 1).
  7. 统一两个组件set1set2
  8. 从步骤 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.