具有度约束的最小生成树
Minimal spanning tree with degree constraint
我要解决这个问题：
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 使用例如Kruskal 或 Prim 算法。
- 重新添加顶点 u 并为每个 Ci 添加 1 和 Ci 之间最便宜的边。
编辑：
我知道这个算法可能会得到一个错误的 MST（见@AndyG 评论）所以我想到了另一个：
- 设k为G中每两个权重之间的最小增量，并在u的每条相邻边上加上0 < x < k。 （例如，如果所有权重都是自然数，那么 k=1 并且 x 是分数）。
- 使用 Kruskal 算法找到 MST。
此解决方案基于 Kruskal 算法对边进行迭代这一事实
按权重排序，因此 G 的所有 MST 之间的差异是每条边是从具有相同权重的所有边中选择的。因此，如果我们增加 u 的相邻边的度数，算法将选择其他度数相同的边而不是 u 的相邻边，除非这条边对于 MST 是必需的并且 u 的度数将是所有边中最小的G.
的 MST
我仍然不知道它是否有效以及如何证明这个算法的正确性。
如有任何帮助，我将不胜感激。
总结建议的算法[对 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。
我要解决这个问题：
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 使用例如Kruskal 或 Prim 算法。
- 重新添加顶点 u 并为每个 Ci 添加 1 和 Ci 之间最便宜的边。
编辑：
我知道这个算法可能会得到一个错误的 MST（见@AndyG 评论）所以我想到了另一个：
- 设k为G中每两个权重之间的最小增量，并在u的每条相邻边上加上0 < x < k。 （例如，如果所有权重都是自然数，那么 k=1 并且 x 是分数）。
- 使用 Kruskal 算法找到 MST。
此解决方案基于 Kruskal 算法对边进行迭代这一事实 按权重排序，因此 G 的所有 MST 之间的差异是每条边是从具有相同权重的所有边中选择的。因此，如果我们增加 u 的相邻边的度数，算法将选择其他度数相同的边而不是 u 的相邻边，除非这条边对于 MST 是必需的并且 u 的度数将是所有边中最小的G.
的 MST我仍然不知道它是否有效以及如何证明这个算法的正确性。
如有任何帮助，我将不胜感激。
总结建议的算法[对 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。