完整圖的最小生成樹數（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.

希望這有助於！