矩阵树定理

这个定理共分为三个部分：

• 给出无向图，求这个图的生成树个数
• 给出有向图和其中的一个点，求以这个点为根的生成外向树个数。
• 给出有向图和其中一个点，求以这个点为根的生成内向树个数。

部分一

我们对这个图构造两个矩阵，分别是这个图的连通矩阵和度数矩阵。连通矩阵𝑆1的第𝑖行第𝑗列上的数字表示原无向图中编号为𝑖和编号为𝑗的两个点之间的边的条数。度数矩阵𝑆2只有斜对角线上有数字，即只有第𝑖行第𝑖列上有数字，表示编号为𝑖的点的度数是多少。我们将两个矩阵相减，即𝑆2−𝑆1，我们记得到的矩阵为𝑇，我们将矩阵𝑇去掉任意一行和一列（一般情况去掉最后一行和最后一列的写法比较多）得到𝑇′，最后生成树的个数就是这个矩阵𝑇′的行列式。

部分二

我们对这个图构造两个矩阵，分别是这个图的连通矩阵和度数矩阵。连通矩阵𝑆1的第𝑖行第𝑗列上的数字表示原无向图中编号为𝑖和编号为𝑗的两个点之间编号𝑖的点指向编号为𝑗的点的条数。度数矩阵𝑆2只有斜对角线上有数字，即只有第𝑖行第𝑖列上有数字，表示编号为𝑖的点的入度是多少。我们将两个矩阵相减，即𝑆2−𝑆1，我们记得到的矩阵为𝑇，我们将矩阵𝑇去掉根所在行和根所在列得到𝑇′，最后生成树的个数就是这个矩阵𝑇′的行列式。

部分三

我们对这个图构造两个矩阵，分别是这个图的连通矩阵和度数矩阵。连通矩阵𝑆1的第𝑖行第𝑗列上的数字表示原无向图中编号为𝑖和编号为𝑗的两个点之间编号𝑖的点指向编号为𝑗的点的条数。度数矩阵𝑆2只有斜对角线上有数字，即只有第𝑖行第𝑖列上有数字，表示编号为𝑖的点的出度是多少。我们将两个矩阵相减，即𝑆2−𝑆1，我们记得到的矩阵为𝑇，我们将矩阵𝑇去掉根所在行和根所在列得到𝑇′，最后生成树的个数就是这个矩阵𝑇′的行列式。