寻找跨越给定最小生成树的最小权重完全图。

Question

让T = (V, E)成为一个具有|V|个顶点和|E| = |V-1|条边的树，其中边缘成本已知。我们想要构建一个最小权重的完全图G = (V, E')，它以其唯一的最小生成树为跨度。
例如：考虑以下树T。红色边缘具有给定成本。将添加虚线边缘以从此树构建完整图形。
要找到生成此图的（多项式时间）算法。我主要是在寻找提示，而不是完整的解决方案。到目前为止，我设计了以下算法：
1）找到包括权重为w_max的最重MST边缘且没有其他MST边缘的图形割。所有其他边缘都必须为w_max + 1。下面的图片说明了我的想法：
2）对于MST的所有其他边缘e_i，按降序处理其权重w_i。取一个仅包含e_i的切割，没有其他MST边缘。该切割中的任何未知非MST边缘都应具有w_i + 1的权重。
问题：
1）上述算法是否正确？根据割定理，应该是这样的。
2）我能否更有效地做到这一点？我没有一个在脑海中找到切割的算法，但我不认为这种方法会很有效。

1) 使用并查集，我按照成本递增的顺序迭代所有最小生成树边，并将相应的顶点统一到同一个组件中。

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

- Adama

---

我无法正式证明，但似乎Kruskal方法和你的切割方法间接相同，不确定你的切割算法是否具有糟糕的复杂度。 - advocateofnone

你关于Kruskal算法的观点是正确且高效的。 - advocateofnone

Answer 1

回答自己的问题

这是我想出的一个高效答案，也考虑了@sasha的反馈意见。

假设我们想计算完全图G的总重量，即;

令T = (V, E)为一棵具有|V|个顶点和|E|=|V|-1条边的树，其权重已知。 计算唯一最小生成树作为跨越T的完全图G =（V，E'）的总权重w_total。 NB：边缘权重是自然数。

算法：

1. 使用具有|V|个单例组件的Union-Find进行初始化。
2. 按升序对T的所有边进行排序。 运行时间：O（| V | * log | V |）。
3. 迭代下一个边缘e =（v1，v2）的T。 将其权重w_e添加到w_total中。
4. 在Union-Find中找到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

因为完全图 G 中有 |V|*(|V|-1)/2 条边，所以运行时间变为 O(|E| + |V| * log|V|) = O(|V|^2)。

- Adama