【算法】矩阵树定理

定义

无向图

给定无向图 $G$

度数矩阵:图 $G$ 的度数矩阵 $D(G)$ 满足如下性质:

$$ d_{i,j}= \begin{cases} \sum_{k}[e(i,k)] & i=j\\ 0 & i\neq j \end{cases} $$

邻接矩阵:图 $G$ 的邻接矩阵 $A(G)$ 满足如下性质:

$$ a_{i,j}=[e(i,j)] $$

Kirchhoff 矩阵:图 $G$ 的 Kirchhof 矩阵 $C(G)$ 满足如下性质:

$$ C(G)=D(G)-A(G) $$

那么 $C[G]$ 的余子式的行列式值即为无向图 $G$ 的生成树个数

有向图

给定有向图 $G$

度数矩阵:类似的定义入度矩阵 $D^{in}(G)$ 和出度矩阵 $D^{out}(G)$ :

$$ d^{in}_{i,j}= \begin{cases} \sum_{k}[e(k,i)] & i=j\\ 0 & i\neq j \end{cases} \\ d^{out}_{i,j}= \begin{cases} \sum_{k}[e(i,k)] & i=j\\ 0 & i\neq j \end{cases} $$

邻接矩阵:类似的定义 $A(G)$ 满足如下性质:

$$ a_{i,j}=[e(i,j)] $$

Kirchhoff 矩阵:类似的定义入 Kirchhoff 矩阵 $C^{in}(G)$ 和出 Kirchhoff 矩阵 $C^{out}(G)$ :

$$ C^{in}(G)=D^{in}(G)-A(G)\\ C^{out}(G)=D^{out}(G)-A(G)\\ $$

以 $rt$ 为根的外向树个数为 $C^{in}(G)$ 在去除第 $rt$ 行和第 $rt$ 列的余子式的行列式值
以 $rt$ 为根的内向树个数为 $C^{out}(G)$ 在去除第 $rt$ 行和第 $rt$ 列的余子式的行列式值

扩展

矩阵树定理求出的值为:

$$ \sum_{T}\prod_{e\in T}p_e $$

在 $p_e=1$ 的特殊情况得到图 $G$ 的生成树个数

在 $p_e$ 为某个特定权值或者概率时为图 $G$ 的生成树的 “权值” 和或者是 “概率” 和

例题

BZOJ 3534 [SDOI2014]重建 题解

Comments

添加新评论