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，任何一对子图之间的最小非零权重差)。在所有原始权重都是自然数的情况下，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。