矩阵树定理

在图论中，矩阵树定理（matrix tree theorem）或基尔霍夫定理（Kirchhoff theorem）是指图的生成树数量等于调和矩阵的行列式（所以需要时间多项式计算）。

若 G 有 n 个顶点，λ1, λ2, ..., λn-1 是拉普拉斯矩阵的非零特征值，则

 

这个定理以古斯塔夫·基爾霍夫名字命名。 这也是凯莱公式的推广（若图是完全图）。

举例 

 

删除任何一个行和一个列，比方说第一行和第一列：

 

则

接续矩阵是

凯莱公式 
完全图 Kn 的调和矩阵是

 

任何餘因子的行列式是 nn-2 。再说L的所有特征值是n，而且L只有n-1个特征向量。所以生成树的总数又是 nn-2 。

证明大纲 
拉氏矩阵有这个属性：任何行或列的元素总和等于0。所以，无论删除什么行或列，都是不变的。或者说L的任何餘因子有同样的行列式。

若K是接续矩阵，L = KKT。在矩阵K中，删除任何一个行或列得到矩阵F。设 FFT = M11 。

使用柯西奈式

 

可以表示这个行列式给予生成树的数量。

参见 

 普吕弗序列
 最小生成树

阅读 

 
 .
 .

参考文献 
代数图论