行列式求值
- 交换矩阵 \(A\) 两行，\(\det(A') = -\det(A)\) 。
- 将矩阵 \(A\) 的第 \(i\) 行乘 \(k\) 后，\(\det(A') = k\times\det(A)\)。
- 将矩阵 \(A\) 的第 \(i\) 行乘 \(k\) 后加到第 \(j\) 行上，\(\det(A')=\det(A)\)。
Matrix-Tree 定理
无向图
设 \(G\) 为无向图的邻接矩阵， \(D\) 为度数矩阵。
设 \(K = D-G\)，\(K'\) 为 \(K\) 去掉任意一行及其对应列的矩阵。
则图的生成树个数为 \(\det(K')\)。
有向图
设 \(G\) 为有向图的邻接矩阵，\(D_{in}\) 为入度矩阵，\(D_{out}\) 为出度矩阵。
设 \(K=D_{in}-G\)，\(K'\) 为 \(K\) 去掉第 \(r\) 行和第 \(r\) 列的矩阵。
则以 \(r\) 为根的外向树个数为 \(\det(K')\)。
设 \(K=D_{out}-G\)，\(K'\) 为 \(K\) 去掉第 \(r\) 行和第 \(r\) 列的矩阵。
则以 \(r\) 为根的内向树个数为 \(\det(K')\)。