$Matrix$ $Tree$ $theorem$
定理
1 | 对于一个无向图 G, 他的生成树个数等于其基尔霍夫矩阵的任意一个 N - 1 阶主子式的行列式的绝对值。 |
构造方式
度数矩阵 $D$ :
在一个 $N \times N$ 矩阵中 $D[i][i] = i的度数$ ，其余为 $0$ 。
邻接矩阵 $A$ :
在一个 $N \times N$ 矩阵中 $D[i][j] = i \to j 的边数$ ，其余为 $0$ 。
基尔霍夫矩阵 $K = D - A$ 。
行列式求法
已求出基尔霍夫矩阵，随意去掉一行一列计算新的行列式，绝对值即生成树个数，有公式
$$
det(K) = \sum_T(-1)^{\tau(T)}\times K_{1, T_1}\times K_{2, T_2}\times \ldots \times K_{n, T_n}
$$
复杂度 $O(N\times N!)$
思考优化求解的方式。
性质
$1.$ 互换矩阵两行 （列），行列式变号。
证明在参考资料里
$2.$ 矩阵若有两行 （列)完全相同，行列式为 $0$ 。
简单说明一下，若有两行（列）都相同，那么可以都被消去，$K[i][i]$ 当中有两个会变 $0$ ，导致行列式归 $0$ 。
也可以通过性质 $1$ 证明，具体看资料 。
$3.$ 如果矩阵的某一行(列)中的所有元素都乘以同一个数k，新行列式的值等于原行列式的值乘上数k。
把原求和式每一项提出一个 $k$ 即可。
$ps:$ 推论 如果矩阵的某一行(列)中的所有元素都有一个公因子k，则可以把这个公因子k提到行列式求和式的外面。
$4.$ 如果把矩阵的某一行(列)加上另一行(列)的k倍，则行列式的值不变。
懒得打证明了，去看资料去
优化求解方式
首先，对于一个上（下）三角矩阵，其行列式是 $\prod_{i = 1}^{n}K[i][i]$ ，根据性质四可知，我们可以采用高斯消元的方式把矩阵消成一个上（下）三角矩阵，然后即可直接求解行列式的值。
为什么是这样？
我们可以观察最初的求和公式，我们发现对于一个上（下）三角矩阵，他的逆序对个数为 $0$ ，所以我们的答案就变成了 $\prod_{i = 1}^{n} K[i][i]$ 。
$Solution$
套上矩阵树定理，有
$$
Sum = \sum_{Tree} \prod_{(u, v)\in E} P_{u, v}
$$
由题意得
$$
Ans = Sum \times \prod_{u, v}(1 - P_{u, v})
$$
把式子拆出来，再设一个 $K[i][j]$
$$
Ans = Sum \times \prod_{(u, v)\in E}K_{u, v} \times (1 - P_{u, v}) \prod_{(u, v)\notin E}(1 - P_{u, v})
$$
而答案是
$$
Ans = Sum \times \prod_{(u, v)\in E}P_{u, v} \prod_{(u, v)\notin E}(1 - P_{u, v})
$$
所以只要使
$$
K_{u, v} = \frac{P_{u, v}}{1 - P_{u, v}}
$$
即可。
然后我们再把 $\prod_{u, v}(1 - P_{u, v})$ 拆出来，剩下的部分通过高消求出行列式，乘积即为答案。
另外，我们发现当 $P_{i, j} = 1$ 时，会输出 $nan$ ，所以如果我们判断 $P_{i, j} = 1$ ，就将 $P_{i, j}$ 减去 $eps$ 。
$Code:$
1 |
|