你就把 * 当作一个扔进去数据吐出来结果的黑箱，怎么运行的不重要，只要把黑箱的结构记住就行了。
——某国集大神如是说。
其实是被证明击败了。证明什么的以后有空再说吧。
基本定义
邻接矩阵 \(A\)
不带权的时候，\(A_{i,j}\) 即为 \(i\) 连向 \(j\) 的边数，无向边拆成两个有向边。
如果带权的话 \(A_{i,j}\) 就是 \(i\) 连向 \(j\) 的所有边权和。
度数矩阵 \(D\)
\(i\ne j\) 时，\(D_{i,j}=0\)。\(D_{i,i}\) 就是点 \(i\) 的度数。
如果是有向图，则拆做入度矩阵 \(D^{in}\) 和出度矩阵 \(D^{out}\)。
带权的话就是相应边的边权和。
Laplace 矩阵 / Kirchhoff 矩阵
这两是一个东西。
对于无向图，\(L=D-A\)。对于有向图，\(L^{in}=D^{in}-A\)，\(L^{out}=D^{out}-A\)。
矩阵树定理
用于计数一个图的相应类别生成树个数，或者所有相应类别生成树的权重之和。定义生成树的权重为其上所有边权重之积。
不难发现前者实际上就是每条边边权视作 \(1\) 的结果。我们记图 \(G\) 的这个值为 \(w(G)\)。
公式部分
无向图
对于任意 \(k\in[1,n]\cap Z\)，有：
\[w(G)=\det L(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}
\]
也就是 \(G\) 的 Laplace 矩阵 \(L(G)\) 行列式关于 \(L(G)_{k,k}\) 的余子式的值。再通俗点也就是 \(L(G)\) 删除第 \(k\) 行列剩下的矩阵的行列式的值。
有向图
与无向图不同的是，这次选定的 \(k\) 必须是根节点。不难想到无向图之所有任选 \(k\) 是因为所有点都可以是根节点。
对于外向树，有：
\[w^{out}(G)=\det L^{in}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}
\]
对于内向树，有：
\[w^{in}(G)=\det L^{out}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}
\]