完整图的最小生成树数（MST）的最小值

Question

具有N个顶点的完整图的最小生成树数（MST）是多少？

Answer 1

我相信答案是。

可以构造一个完整的图，其中n个节点只有一个MST。要做到这一点，请构建一个包含n个节点，标记为1,2,3，...，n的图。然后，添加1到2，从2到3，从3到4，...，从n - 1到n的成本0的边，并添加连接成本为1的每一对节点的边。显然，选择所有零成本边缘给出了该图的一个可能的生成树，并且它是最小生成树，因为如果选择了任何其他边的选择，成本将至少为1.此外，这是图中唯一的MST因为如果选择了另一组边缘，那么该组必须至少包含一个边的成本至少为1，因此总MST的成本至少为1.

希望这有助于！