graph - 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)小于(v1,v2)T 中的权重，则不再是 MST。

Answer 2

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

Answer 3

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

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