查找跨越给定最小生成树的最小权重完整图 [英] Find minimum-weight complete graph that spans a given minimum spanning tree

问题描述

让 T =（V，E）是 | V | 顶点和 | E |的树。 = | V-1 | 边，成本已知。我们想要构建一个跨过 T 的最小权重完全图 G =（V，E'）作为其唯一的最小生成树。 / p>

示例：考虑以下树 T 。 红色中的边具有给定的成本。

由于其唯一的MST而跨越 T 的最小权重完整图 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）对MST的所有其他边 e_i 重复，重量 w_i ，按重量降序排列。采取仅包含 e_i 且不包含其他MST边的削减。此削减的任何未知的非MST边的权重应为 w_i + 1 。

---

问题：

1）上述算法正确吗？

2）我可以更有效地做到这一点吗？我没有一种算法可以在我的头顶上找到切口，但我不认为这种方法可能有效。

---

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

1）使用联合-查找，我通过提高成本来迭代所有MST边缘，并统一同一组件下的相应顶点。

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

解决方案

回答我自己的问题

这是我想出的一个有效答案，下面还介绍了@sasha的反馈。
假设我们要计算完整图形G的总权重，即；

让T =（V，E ）是| V |的树顶点和| E | = | V | -1边，且权重已知。计算最小重量完整图G =（V，E’）的总重量 w_total ，该图跨越T作为唯一的最小生成树。
注意：边缘权重是自然数。

算法：

1. 使用 | V | 单例组件初始化联合查找。


2. 对 T 递增重量。运行时间：O（| V | * log | V |）。


3. 迭代下一条边 e =（v1，v2） T 。将其重量 w_e 加到 w_total 。


4. 查找 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 ：

 对于set1中所有顶点v1 
 set2 
中的顶点v2创建边e =（v1，v2）;忽略edge是否是MST edge 
 w_e = w_mst_edge + 1 
  

因此运行时间变为O（| E | + | V | * log | V |）= O（| V | ^ 2），因为我们有| E | = | V | *（| V | -1）/ 2完整图形 G 中的边。

Let T = (V, E) be a tree of |V| vertices and |E| = |V-1| edges, with known costs. We want to construct a minimum-weight complete Graph G = (V, E') that spans T as its unique minimum spanning tree.

Example: consider the following tree T. Edges in red have a given cost. Dotted edges will be added to construct a complete graph from this tree.

The minimum-weight complete graph G that spans T as its unique MST is the following:

---

I am trying to find a (polynomial-time) algorithm that generates this graph. I am looking mostly for a tip, not the complete solution. So far, I have devised the following algorithm:

1) Find a cut of the graph that includes the heaviest MST edge of weight w_max and no other MST edges. All other edges have to be w_max + 1. The following pictures illustrates my idea:

Edges (1--2), (1--4), (4--5), (2--3) and (2--5) are included in this cut C. The only edge that is included in the MST is edge (2--3) and it's the heaviest edge in the MST, with w=56. Thus, all other edges should have w=57. Proof: assume the contrary; we can replace (2--3) with another edge and still keep the tree connected. Now the tree's weight is lighter, thus (2--3) doesn't belong to the MST. Contradiction.

2) Repeat for all other edges e_i of the MST, of weight w_i, in decreasing weight order. Take a cut that includes only e_i and no other MST edges. Any unknown non-MST edge of this cut, should have a weight of w_i + 1.

---

Questions:

1) Is the above algorithm correct? According to the Cut property, it should be.

2) Could I do it more efficiently? I don't have an algorithm to find cuts on the top of my head, but I don't feel this approach could be efficient.

---

edit: Another approach that I had in my mind was an approach based on Kruskal's algorithm:

1) Using a Union-Find, I iterate all MST edges, by ascending cost, and unify the corresponding vertices under the same component.

2) In each step, two different components are unified through an edge of cost w. Any other edges that form a cycle within the same (new) component should have a cost of w+1.

解决方案

Answering my own question

Here's an efficient answer I've come up with, following also the feedback from @sasha . Suppose we would like to calculate the total weight of the complete graph G, i.e;

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.

Algorithm:

1. Initialize a Union-Find with |V| singleton components.
2. Sort all edges of T by ascending weight. Running time: O(|V| * log|V|).
3. Iterate next edge e = (v1,v2) of T. Add its weight w_e to w_total.
4. Find v1's andv2's components in the Union-Find: set1,set2, containing size1 and size2 vertices, respectively.
5. These components will be unified. Since G is a complete graph, size1 × size2 edges will be added: one edge is the MST e edge, all others have to be heavier than e, so that Kruskal's algorithm will ignore them. Thus, their minimum weight should be at least w_e + 1.
6. w_total += (size1 × size2 - 1) × (w_e + 1).
7. Unify the two components set1 and set2.
8. Repeat from step 2 for the next MST edge e.

Running time: O(|V| * log|V|).

---

If the problem becomes: list in detail all edges e = (v1, v2) of the complete graph and their weight w, we just have to do, between steps 6 and 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

So the running time becomes O(|E| + |V| * log|V|) = O(|V|^2), since we have |E| = |V|*(|V|-1)/2 edges in the complete graph G.

这篇关于查找跨越给定最小生成树的最小权重完整图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！