设 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
。
最佳答案
回答我自己的问题
这是我根据@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|
单例组件初始化 Union-Find。 - 按权重升序对
T
的所有边进行排序。运行时间:O(|V| * log|V|)。 - 迭代
T
的下一条边e = (v1,v2)
。将其权重w_e
添加到w_total
。 - 在Union中查找
v1
和v2
的组件-查找:set1
,set2
,分别包含size1
和size2
顶点。 - 这些组件将被统一。由于
G
是一个完全图,因此将添加size1 × size2
边:一条边是 MSTe
边,所有其他边都必须更重而不是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
和 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
中的边。
关于algorithm - 查找跨越给定最小生成树的最小权重完整图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27772118/