矩阵树定理

图论中,矩阵树定理(matrix tree theorem)或基尔霍夫定理(Kirchhoff theorem)是指生成树数量等于调和矩阵余子式(所以需要时间多项式计算)。

Gn顶点λ1λ2, ..., λn-1拉普拉斯矩阵的非零特征值,则

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

举例

 
L是这个钻石图的拉氏矩阵
 

删除任何一个行和一个列,比方说第一行和第一列:

 

 

接续矩阵

 

完全图 Kn 的调和矩阵是

 

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

证明大纲

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

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

使用柯西奈式[1]

 

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

参见

阅读

参考文献

  1. ^ Graphs, Matrices, Isomorphism. math.fau.edu. [2020-02-14]. (原始内容存档于2009-03-04).