具有N个顶点的完整图的最小生成树（MST）的最小数量是多少？
问问题
352 次
1 回答
2
我相信答案是1。
可以构造一个包含 n 个节点且恰好具有一个 MST 的完整图。为此，请构建一个带有 n 个节点的图，这些节点标记为 1、2、3、...、n。然后，添加一条成本为 0 的边，从 1 到 2，从 2 到 3，从 3 到 4，...，从 n - 1 到 n，并添加连接每对成本为 1 的节点的边。显然，选择所有零成本边给出了该图的一个可能的生成树，它是最小生成树，因为如果选择任何其他边选择，成本将至少为 1。此外，这是图中唯一的 MST它的成本为 0，因为如果选择了另一组边，则该组必须包括至少一个成本至少为 1 的边，因此总 MST 的成本至少为 1。
希望这可以帮助！
于 2012-12-21T21:47:20.163 回答