基尔霍夫矩阵-矩阵树定理

发表于 更新于 分类于

求一个图的生成树个数

一个图的生成树个数是其基尔霍夫矩阵任意主余子式的值。

基尔霍夫矩阵： - \(D_{ii}\): Degree(i) - \(D_{ij}\): i 到 j 的边数取负数

对于 n 阶矩阵，去掉任意的第 R 行 R 列，求剩下的 n-1 阶行列式的绝对值即最小生成树个数。

根据题目特点，可利用特殊数据推出行列式结果，数据范围允许时可按照行列式性质计算行列式。

例如一个图：

1
2
3
4
5
1---2
|  /|
| / |
|/  |
3---4

其基尔霍夫矩阵为：

1
2
3
4
5
    (1) (2) (3) (4)
(1)  2  -1  -1   0 
(2) -1   3  -1  -1
(3) -1  -1   3  -1
(4)  0  -1  -1   2

去掉第 4 行第 4 列为：

1
2
3
4
    (1) (2) (3)
(1)  2  -1  -1 
(2) -1   3  -1 
(3) -1  -1   3

计算行列式得 8，所以这个图有 8 种生成树。

对有向图，还可以计算内向树与外向树，内向树指树上的边由子结点指向父节点，让 \(D_{ii}\) 表示入度即可。外向树反之。