矩阵树定理

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

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



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

 举例 
缩略图|L是这个钻石图的拉氏矩阵

对于右图的例子，首先求出调和矩阵 : 



随后求出余子式，也即删除任何一个行和一个列，例如第一行和第一列：



则

.

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



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

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

若是接续矩阵，则拉普拉斯矩阵 。在矩阵中，删除任何一个行或列得到矩阵，那么，其中  表示  删除第一行第一列后得到的余因子矩阵。

使用柯西-比内公式



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

 参见 

 普吕弗序列
 最小生成树

 阅读 


 .
 .


 参考文献 
Category:代数图论