首页 > 编程学习 > 矩阵树定理公式集(证明真的太ex了)

矩阵树定理公式集(证明真的太ex了)

发布时间:2022/12/10 17:36:56

求法一
传送门
求法二

1.生成树计数

拉普拉斯矩阵 L\mathcal{L}Ln×nn \times nn×n 的一个矩阵
Li,i=degiL_{i,i} = deg_iLi,i=degi
Li,j=−number_of_edge(i,j)(i≠j)L_{i, j} = -number\_of\_edge (i, j)(i \neq j)Li,j=number_of_edge(i,j)(i=j)

生成树数量为 L\mathcal{L}L 的任意一个 n−1n - 1n1 阶主子式的行列式

2.i 为根的内向树计数

关联矩阵 MMMn×mn \times mn×m 的一个矩阵
jjj 条边的起点是 iii, Mi,j=1M_{i,j} = 1Mi,j=1
jjj 条边的终点是 iii, Mi,j=−1M_{i,j} = -1Mi,j=1
否则为 000

基本关联矩阵:MMM 删去任何一行的矩阵

矩阵 NNN
jjj 条边的起点为 iiiNi,j=1N_{i,j} = 1Ni,j=1
否则为 000

iii 为根的内向树的方案数为 MNTMN^{T}MNT 删去第 iiiiii 列的主子式的行列式

3.i 为根的外向图计数

建反向图,变为 2.2.2.

4.s 出发的欧拉回路数量

did_idi 表示 iii 的出度,TuT_uTu 表示以 uuu 为根的内向生成树的数量
sss 出发的欧拉回路数量为 Ts×ds!×∏i≠s(di−1)!T_s \times d_s! \times \prod_{i \neq s} (d_i - 1)!Ts×ds!×i=s(di1)!

5.整个图的欧拉回路数量

任意指定一个 sss,整个图的欧拉回路数量为 Ts×∏(di−1)!T_s \times \prod(d_i - 1)!Ts×(di1)!


本文链接:https://www.ngui.cc/article/show-747538.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000