矩阵树定理

矩阵树定理(Matrix-Tree Theorem)是代数图论中的一个基础定理,用于将图的结构属性(生成树的组合计数)转化为线性代数运算(求矩阵行列式)。

  1. 莱布尼茨公式 (Leibniz formula)

表示对集合 的一个排列。

是所有 个可能排列的集合(对称群)。

是排列 的符号差(逆序数奇偶性)。

如果 是偶排列则为 ,奇排列则为 。 是矩阵中第 行、第 列的元素。