找到 minimum-weight 个跨越给定最小生成树的完整图
Find minimum-weight complete graph that spans a given minimum spanning tree
设 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
.
回答我自己的问题
这是我根据@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
.
设 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
.
回答我自己的问题
这是我根据@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
条边:一条边是 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
和[=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
.