寻找最小度数特定顶点的最小生成树

Question

给定无向连通图G={V,E}，其中v是V(G)中的一个顶点，f:E->R+（正实数）是一个权重函数，我需要找到一个最小生成树，使得v的度数最小。我已经注意到，如果所有边的权重都是唯一的，则MST是唯一的，因此我相信它与边上的重复权重有关。我考虑运行Kruskal算法，但在对边进行排序时，我将始终考虑出现在v上的边。例如，如果(a,b),(c,d),(v,e)是唯一权重为k的边，则排序后的边数组的可能排列方式为：{(a,b),(c,d),(v,e)}或{(c,d),(a,b),(v,e)}。我已经在几个图上运行了这个变种，似乎可以工作，但我无法证明它。有人知道如何证明算法是正确的（即证明v的度数最小），或者给出算法失败的反例吗？

- sel

---

1. 我会首先证明Kruskal算法可以生成所有可能的最小生成树（算法的执行完全由相同权重的边的顺序决定）。
2. 然后，我会将Kruskal算法的任何执行与您建议的执行进行比较，并尝试得出结论，即您的执行会产生更少的与“v”相邻的边。

- piotrekg2

Answer 1

请注意，Kruskal算法可应用于任何加权图，无论它是否连通。一般情况下，它会生成一个最小权重生成森林（MSF），每个连通分量都有一个MST。为了证明你修改后的Kruskal算法成功找到了度数最小的MST，需要证明稍微更强的结果：如果你将算法应用于可能不连通的图，则它可以成功地找到度数最小的MSF。

证明通过对不同权重数量k的归纳进行。

基本情况（k = 1）。在这种情况下，权重可以忽略不计，我们试图找到一个度数最小的生成森林。在这种情况下，你的算法可以描述如下：根据以下两个规则尽可能选择边缘：

1）没有选定的边与先前选定的边形成环路

2）涉及v的边不被选择，除非任何不涉及v的边违反规则1。

让G'表示从G中删除v和所有关联边后的图形。很容易看出，在这种特殊情况下，算法的工作方式如下。它首先为G'创建一个生成森林。然后，它取出那些在原始图G中与v的连通分量相交的森林中的树，并通过一条单独的边将每个组件连接到v。由于第二阶段连接到v的组件不能以其他方式彼此连接（因为如果存在不涉及v的任何连接边，则会按规则2进行选择），因此很容易看出v的度是最小的。

归纳假设：假设对于 k 结果是正确的，G 是具有 k+1 个不同权重的加权图形，v 是 G 中指定的顶点。按升序排序不同的权重（使得权重 k+1 是不同权重中最长的 - 即 w_{k+1}）。让 G' 成为具有相同顶点集但所有权重为 w_{k+1} 的边被删除的子图 G。由于边按权重递增的顺序排序，请注意修改后的 Kruskal 算法实际上是通过应用自己到 G' 来 开始。因此 - 在考虑权重为 w_{k+1} 的边之前的归纳假设下，算法已成功地构造了 G' 的 MSF F'，其中度数 d' 是在 G' 中最小化的 v。

作为最后一步，将修改过的Kruskal算法应用于整个图G，通过添加权重为w_{k+1}的边将F'中的某些树合并在一起。一个概念化最后一步的方法是将F'视为一个图，当第一棵树中有一条边的权重w_{k+1}指向第二棵树中的某个节点时，两棵树就会连接在一起。我们几乎已经有了基础情况的F'。修改后的Kruskal算法将添加权重为w_{k+1}的边，直到无法再添加为止——除非没有其他方法连接到需要连接以获取原始图G生成森林的F'中的树，否则不会添加连接到v的边。

在生成的最小生成森林中，v 的最终度数为d = d'+d"，其中d"是在最后一步添加的权重为w_{k+1}的边的数量。既不能使d'也不能使d"更小，因此可以得出结论，d不能再变小了（因为在任何生成树中，v的度数可以写成比w_{k+1}小的边的数量与权重为w_{k+1}的边的数量之和）。

证毕。

尽管最后一步有些牵强附会，但Stack Overflow不是同行评议的期刊。总体逻辑应该足够清晰。

最后一个备注——Prim算法似乎可以类似地修改解决这个问题。你研究过吗？

- John Coleman