1. 概述
本文将讨论最小生成树（Minimum Spanning Tree, MST）的定义，并介绍如何统计一个图中所有最小生成树的数量。
最小生成树是图论中的经典问题，常用于网络设计、路径规划等领域。而统计图中所有 MST 的数量，则是进一步理解图结构和生成树分布的重要方式。
2. 生成树与最小生成树定义
2.1 生成树（Spanning Tree）
给定一个无向连通图 $ G(V, E) $，其生成树是一个子图 $ T(V, E') $，满足：
- 包含图中所有顶点 $ V $
- 边集 $ E' \subseteq E $，且 $ |E'| = |V| - 1 $
- 无环且连通
2.2 最小生成树（Minimum Spanning Tree）
最小生成树是在所有生成树中，边权总和最小的那一个（或多个）。
3. 示例说明
我们来看一个无向带权图：
从该图中可以构造出多个生成树，例如：
每棵树都包含所有顶点，且无环。计算每棵树的边权和：
- ST₁: 15
- ST₂: 11
- ST₃: 12
- ST₄: 10 ✅
因此，ST₄ 是 MST。
4. 生成树性质总结
- 边数恒为 $ |V| - 1 $
- 无环（Acyclic）
- 若删除任意一条边，则图变为不连通
- 若添加任意一条边，则形成一个环
5. MST 数量统计方法
5.1 完全图（Complete Graph）的情况
如果图是完全图，那么生成树的数量可用 Cayley 公式 计算：
$$ \text{生成树数量} = V^{(V-2)} $$
然后遍历所有生成树，计算其边权和，找出最小值并统计出现次数，即可得到 MST 的数量。
伪代码如下：
algorithm TotalNumberOfMSTCompleteGraph(G, V, E, W):
N <- V^(V-2)
P <- store(edgeList)
print("Number of Spanning Trees is", N)
minList <- [ ]
for i <- 1 to N:
S[i] <- sum of edge weights in spanning tree i
minList.append(S[i])
minMST <- min(minList)
countMST <- count(minList, minMST)
print("Total number of MST is", countMST)
5.2 非完全图（Incomplete Graph）的情况
对于非完全图，我们使用 Matrix Tree Theorem（矩阵树定理） 来统计生成树数量。
步骤如下：
- 构建邻接矩阵 A
- 构建度矩阵 D
- 构建拉普拉斯矩阵 L = D - A
- 计算任意一个余因子（cofactor），即生成树数量
伪代码如下：
algorithm TotalNumberOfMSTIncompleteGraph(G, V, E, W):
A <- AdjacencyMatrix(G)
D <- DegreeMatrix(G)
L <- D - A
N <- (-1)^(1+1) * |M[1,1]|
P <- store(edgeList)
print("Number of Spanning Tree is", N)
minList <- [ ]
for i <- 1 to N:
S[i] <- sum of edge weights in spanning tree i
minList.append(S[i])
minMST <- min(minList)
countMST <- count(minList, minMST)
print("Total number of MST is", countMST)
6. 示例图运行结果
6.1 完全图示例
图 $ G_4 $ 有 3 个顶点：
生成树数量：$ 3^{3-2} = 3 $
边权和分别为：
- ST₁: 5
- ST₂: 4 ✅
- ST₃: 5
因此 MST 数量为 1。
6.2 非完全图示例
图 $ G_5 $ 有 4 个顶点：
邻接矩阵、度矩阵、拉普拉斯矩阵分别为：
$$ A = \begin{bmatrix} 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 1 \ 1 & 1 & 0 & 1 \ 1 & 1 & 1 & 0 \ \end{bmatrix},\quad D = \begin{bmatrix} 2 & 0 & 0 & 0 \ 0 & 2 & 0 & 0 \ 0 & 0 & 3 & 0 \ 0 & 0 & 0 & 3 \ \end{bmatrix},\quad L = \begin{bmatrix} 2 & 0 & -1 & -1 \ 0 & 2 & -1 & -1 \ -1 & -1 & 3 & -1 \ -1 & -1 & -1 & 3 \ \end{bmatrix} $$
计算余因子得：生成树数量为 8。
边权和分别为：
- 5, 6, 5, 8, 5, 7, 8, 8
最小边权和为 5，出现 3 次，因此 MST 数量为 3。
7. 时间复杂度分析
| 图类型 | 算法复杂度 |
|---|---|
| 完全图 | $ \mathcal{O}(V) $ |
| 非完全图 | $ \mathcal{O}(V^3) $ |
⚠️ 非完全图中，求矩阵行列式是最耗时的操作。
8. MST 的实际应用
- 网络设计（通信、电力、供水）
- 地图路径规划
- 图像分割
- 手写识别
- 聚类分析（Cluster Analysis）
9. 总结
本文介绍了：
- 生成树与最小生成树的定义
- 如何统计图中所有最小生成树的数量
- 对于完全图与非完全图分别给出了解决方案
- 给出了算法伪代码与示例运行结果
- 分析了算法的时间复杂度
通过这些方法，我们可以在不同类型的图中高效地统计最小生成树的数量，有助于更深入地理解图结构和生成树分布特性。