通过Prim算法获得的图的最小生成树

Question

我需要一些关于Prim算法问题的帮助：

令T为由Prim算法获得的图G的最小生成树。设Gnew是通过向G添加新顶点和一些带有权重的边来获得的图，将新顶点连接到G中的某些顶点。我们可以通过向T添加一个新边来构造Gnew的最小生成树吗？如果你回答是，请解释如何;如果没有，请解释原因。

先感谢您！！

Answer 1

我们可以通过向T添加一个新边来构造Gnew的最小生成树吗？

不，不是一般的。假设T是通过考虑v1,v2,...,vn-1的脊椎生成的

设vn为新顶点，(v1,vn)为加权边（v1为T的根），如果(v1,vn)的权重小于T中(v1,v2)的权重，则不再是MST。

Answer 2

并非在所有情况下我们都可以在T中添加新边，它取决于新边的权重，因为如果新边重量小于图中的其他权重，旧MST（T）会发生变化

Answer 3

不，这可能更容易用反例来形象化：

从上面可以看出，与原始MST相比，新MST不仅缺少边缘。它也使用两个顶点而不是一个顶点。