algorithm - 具有度约束的最小生成树

Question

我必须解决这个问题:

Given a weighted connected undirected graph G=(V,E) and vertex u in V. Describe an algorithm that finds MST for G such that the degree of u is minimal; the output T of the algorithm is MST and for each another minimal spanning tree T' being the degree of u in T less than or equal to the degree of u in T'.

我想到了这个算法(经过一些谷歌搜索，我找到了类似问题的解决方案 here):

• 暂时删除顶点u。
• 对于每个生成的连接组件 C1,...,Cm 找到一个 MST，例如使用Kruskal 或 Prim 算法。
• 重新添加顶点 u 并为每个 Ci 添加 1 和 Ci 之间最便宜的边。

编辑:

我知道这个算法可能会得到一个错误的 MST(见@AndyG 评论)所以我想到了另一个:

• 让 k 为 G 中每两个权重之间的最小增量，并将 0 < x < k 添加到 u 的每个相邻边。 (例如，如果所有权重都是自然数，那么 k=1 并且 x 是分数)。
• 使用 Kruskal 算法找到 MST。

此解决方案基于 Kruskal 算法迭代边这一事实按权重排序，因此 G 的所有 MST 之间的差异是每条边是从具有相同权重的所有边中选择的。因此，如果我们增加 u 的相邻边的度数，算法将选择其他度数相同的边而不是 u 的相邻边，除非这条边对于 MST 是必需的并且 u 的度数将是所有边中最小的G 的 MST。

我仍然不知道它是否有效以及如何证明这个算法的正确性。

我将不胜感激。

Answer 1

总结建议的算法[对 epsilon(你称为 x)有更严格的要求]:

• 选择一个很小的 ​​epsilon(使得 epsilon * deg(u) 小于 d，d 是任何一对子图之间的最小非零权重差)。在所有原始权重都是自然数的情况下，epsilon = 1/(deg(u)+1) 就足够了。
• 将 epsilon 添加到入射到 u 的所有边的权重
• 找到一棵最小生成树。

我们将证明这个过程找到了原始图的 MST，它最小化了 u 的边缘数。

令 W 为原始图中任何最小生成树的权重。

首先，我们将证明新图的每个 MST 都是原始图的 MST。原始图中的任何非 MST 的权重必须至少为 W + d。新图中的任何 MST 的权重最多必须为 W + deg(u)*epsilon(因为原始图中的任何 MST 在新图中的权重最多)。由于我们选择的 epsilon 使得 deg(u)*epsilon < d，因此我们得出结论，新图中的任何 MST 也是原始图中的 MST。

其次，我们将证明新图的 MST 是原始图的 MST，它最小化了与 u 关联的边数。原始图的 MST T 在新图中的权重为 W + k * epsilon，其中 k 是 T 中与 u 关联的边数。我们已经表明，新图的每个 MST 也是原始图的 MST。因此，新图的MST是使k(入射到u的边数)最小的原始图的MST。