邻接矩阵

如果有一条边 $(u,v,w)$,则 $a_{u,v}$ 和 $a_{v,u}$ 加上 $w$

度数矩阵

如果有一条边 $(u,v,w)$,则 $d_{u}$ 和 $d_v$ 加上 $w$

基尔霍夫矩阵

设 $M$ 矩阵为:
$$
\begin{cases}
M_{i,j}=-\sum a_{i,j} \quad (i \not= j) \\
M_{i,i}=d_i \\
\end{cases}
$$

矩阵树定理

对于基尔霍夫矩阵的任意一个 $n-1$ 阶主子式的行列式的值为:
$$
\sum_{T r e e} \prod_{E \in T r e e} E(u, v)
$$
即所有生成树的边权的成积的和

外向树

$$
\begin{cases}
M_{i j}=-e(i, j) \\
M_{i i}=\sum_{j=1}^{n} e(i, j) \\
\end{cases}
$$

这次需要删掉第 $i$ 行第 $i$ 列

内向树

$$
\begin{cases}
M_{i j}=-e(i, j) \\
M_{i i}=\sum_{j=1}^{n} e(j, i) \\
\end{cases}
$$

这次需要删掉第 $i$ 行第 $i$ 列