小编点评

**矩阵树定理** 矩阵树定理是无向图的矩阵树定理的推广。其主要应用于计算无向图中所有路径的长度和权重之和。 **无向图矩阵树定理** 对于无向图 \\(A\\)，其矩阵树定理如下： $$\sum_{T} \prod_{e \in T} w_e = \det(D - A)$$ 其中： * \\(T\\) 是所有简单路径的集合 * \\(e\\) 是所有路径中的边 * \\(w_e\\) 是每条边的权重 * \\(D\\) 是度数矩阵 * \\(A\\) 是邻接矩阵 **矩阵树定理的推导** 矩阵树定理可由以下公式推导： $$D_{i, i} = \sum_j w(i, j)$$ 其中 \\(D_{i, i}\\) 是度数矩阵 \\(D\\) 的对角元素， \\(w(i, j)\\) 是边 \\(i \\to j\\) 的边权。 **矩阵树定理的应用** 矩阵树定理可以用于计算无向图中所有路径的长度和权重之和。例如，以下代码计算无向图 \\(A\\) 中所有简单路径的长度和权重之和： ```python def matrix_tree_sum(A): # 初始化结果矩阵 result = [[0 for _ in range(len(A[0])) for _ in range(len(A))] for _ in range(len(A))] # 计算每个节点的度数 for i in range(len(A)): for j in range(len(A[0])): result[i][j] = sum([A[i][k] for k in range(len(A)) if k != j]) # 计算所有路径的长度和权重之和 for path in all_paths(A): result[0][0] += product([A[i][j] for i, j in path]) return result[0][0] ``` **结论** 矩阵树定理是无向图矩阵树定理的推广，可以用于计算无向图中所有路径的长度和权重之和。

正文

矩阵树定理

本文不作为教学向文章。

比较好的文章参考：

• 矩阵树-定理以及凯莱公式

• 【学习笔记】矩阵树定理（Matrix-Tree）_繁凡さん的博客-CSDN博客

• 矩阵树定理入土 - ixRic 的博客 - 洛谷博客

对于无向图

无向图中应该是矩阵树定理的常用场景。

无向图的矩阵树定理讲的是：

求行列式的矩阵为 \(D - A\)，也就是度数矩阵 \(D\) 减去邻接矩阵 \(A\)。

其中 \(A_{i, j} = \sum w(i, j)\)，也就是 \(i \to j\) 的边的边权之和（允许重边）。

其中 \(D_{i, i} = \sum_j w(i, j)\)，也就是所有通向 \(i\) 的边的边权之和。

这好像在无向图中也适用。

如果我们需要计数的话，就把边权设为 \(1\) 即可。

---

在 [SDOI2014]重建 - 洛谷 中，求的是 \(\sum_T \prod_{e \in T} p_e \prod_{e \not\in T} (1 - p_e)\)。

我们可以轻易的把 \(\prod_{e \not\in T} (1 - p_e)\) 它变为 \(\cfrac {\prod_e (1 - p_e)}{\prod_{e \in T} (1 - p_e)}\)。

剩下的就简单了。于是余下的是建矩阵的问题。

根据上面所说，也很简单了。

---

对于有向图

\(A, D\) 的定义与上面类似。

只是注意两个点：

• 内向树和外向树

• 根

在求 \(\det\) 的时候需要删掉一行，删掉的那一行作为的是根！

内向树和外向树？内向即是指向根的方向，外向即是根向外指。

此时 \(D\) 需要有变化：\(D_{i, i} = \sum_j w(i, j)\) 就是根向外指，是外向树。如果为 \(\sum_j w(j, i)\) 则是内向树。

无向图中随意，因为无论外向还是内向结果都是一样的。