矩阵树定理-526互联

矩阵树定理

对于无向图\(G\)，定义度数矩阵\(D\)满足：

\[D(i,j)=\begin{cases}deg_i&i=j\\0&i\neq j\end{cases} \]

对于有向图\(G\)，定义\(D^{in}\)为图\(G\)的入度矩阵，\(D^{out}\)为图\(G\)的出度矩阵，同样有：

\[D^{in}(i,j)=\begin{cases}in_i&i=j\\0&i\neq j\end{cases} \]

\[D^{out}(i,j)=\begin{cases}out_i&i=j\\0&i\neq j\end{cases} \]

定义\(G\)的邻接矩阵\(A\)满足：

\[A(i,j)=\begin{cases}0&i=j\\adj_{i,j}&i\neq j\end{cases} \]

其中\(adj_{i,j}\)表示点\(i\)与点\(j\)之间的边数。

定义\(G\)的基尔霍夫\(\text{Kirchhoff}\)矩阵（又称\(\text{Laplace}\)矩阵）\(L\)满足：

\[K(G)=D(G)-A(G) \]

记无向图\(G\)的生成树数量为\(t(G)\)，有向图根向生成树数量为\(t^{root}(G,u)\)，有向图叶向生成树数量为\(t^{leaf}(G,u)\)

定理

1.无向图矩阵树定理：

\[\forall i\in[i,n]t(G)=\text{det}K(G)\begin{pmatrix}1,2,\cdots i-1,i+1,\cdots n\\1,2,\cdots i-1,i+1,\cdots n\end{pmatrix} \]

其中\(K(G)\begin{pmatrix}1,2,\cdots i-1,i+1,\cdots n\\1,2,\cdots i-1,i+1,\cdots n\end{pmatrix}\)即去掉第\(i\)行和第\(i\)列的矩阵。

2.有向图矩阵树定理：

\[\forall i\in[i,n]t^{root}(G)=\text{det}K^{out}(G)\begin{pmatrix}1,2,\cdots i-1,i+1,\cdots n\\1,2,\cdots i-1,i+1,\cdots n\end{pmatrix} \]

\[\forall i\in[i,n]t^{leaf}(G)=\text{det}K^{in}(G)\begin{pmatrix}1,2,\cdots i-1,i+1,\cdots n\\1,2,\cdots i-1,i+1,\cdots n\end{pmatrix} \]

3.BEST定理：
设有向欧拉图\(G\)的欧拉回路数量为\(ec(G)\)，则有

\[ec(G)=t^{root}(G,i)\prod\limits_{u\in V}(deg_u-1)! \]

设以\(k\)为起点的欧拉回路数量为\(ec(G,k)\)，则有

\[ec(G,k)=t^{root}(G,k)deg_k\prod\limits_{u\in V}(deg_u-1)! \]

当边有边权时，把边权当做重边即可。

证明

参考矩阵树定理及其无向图形式证明

定义图\(G\)的关联矩阵\(M(G)\)为一个大小为\(n\times m\)的矩阵并满足：

\[M(G)=\begin{cases}-1& i\;is\;the\;end\;of\;edge_j\\1& i\;is\;the\;start\;of\;edge_j\\0&otherwise\end{cases} \]

定义图\(G\)的减关联矩阵\(M_0(G)\)为关联矩阵\(M(G)\)去掉最后一行后的大小为\((n-1)\times m\)的矩阵。

定义图\(G\)的子减关联矩阵\(M_0(G)[S]\)为选出\(M_0(G)\)中的(n-1)列构成的子集\(S\)。

引理1：

\[M\times M^T=K \]

证明：

\[M\times M^T(i,j)=\sum\limits_{k=1}^mM(i,k)\times M^T(k,j)=\sum\limits_{k=1}^mM(i,k)\times M(j,k) \]

当\(i,j\)不为边\(k\)的端点时，贡献为0；

当\(i=j\)时，\(M(i,k)=M(j,k)\)，贡献为1，总贡献即为\(deg_i\)

当\(i\neq j\)时，\(M(i,k)=-M(j,k)\)，贡献为-1,总贡献即为\(-A(i,j)\)

引理2：

若\(S\)构成的边集不是生成树，\(detM_0[S]=0\)，否则\(detM_0[S]=1/-1\)

证明：若\(S\)没有构成生成树，那么至少存在一个简单环\(C(e_{i_1},e_{i_2}\cdots e_{i_k})\)。首先，对于\(M_0[S]\)中处于简单环对应的行，恰好有两列非0，而对于简单环对应的列，恰好存在两个元素为1和-1。

要证明\(det=0\)，就需要证明\(i_1,i_2,\cdots i_k\)列线性相关。我们考虑依次合并所有列。我们拿\(i_1\)行消\(i_2\)列，那么\(e_{1_v}\)和\(e_{2_u}\)抵消了，只剩\(e_{1_u},e_{2_v}\)为1/-1。以此类推，合并到\(i_j(j\neq k)\)列时，消完后只剩\(e_{1_u},e_{j_v}\)为1/-1。最后合并到第\(k-1\)列时，已经和第\(i_k\)相等了，这就证明了\(i_1,i_2,\cdots i_k\)列线性相关，也就说明了\(detM_0[S]=0\)。

引理3：\(\text{Binet-Cauchy}\)定理

\[\sum\limits_{S}det(A_S)\times det(B_S)=det(C) \]

其中\(A\)是一个\(m\times n\)的矩阵，\(B\)是一个\(n\times m\)的矩阵，\(C\)是一个\(n\times n\)的矩阵，满足\(C=B\times A\)，\(S\)是集合\(\{1,2,\cdots m\}\)的一个大小为\(n\)子集，\(A_S\)表示\(A\)中保留\(S\)行得到的\(n\times n\)的矩阵，\(B_S\)表示\(B\)中保留\(S\)列得到的矩阵。

设\(P,Q\)是两个长度为\(n\)的排列，那么等式左边等于：

\[\sum\limits_{S}(\sum\limits_{P}(-1)^{\lambda(P)}\prod_{i}A_{S_i,P_i})(\sum\limits_{Q}(-1)^{\lambda(Q)}\prod_{i}B_{i,S_{Q_i}}) \]

\[=\sum\limits_{S}(\sum\limits_{P}(-1)^{\lambda(P)}\prod_{i}A_{S_i,P_i})(\sum\limits_{Q}(-1)^{\lambda(Q^{-1})}\prod_{i}B_{Q^{-1}_{Q_i},S_{Q_i}}) \]

\[=\sum\limits_{S}(\sum\limits_{P}(-1)^{\lambda(P)}\prod_{i}A_{S_i,P_i})(\sum\limits_{Q}(-1)^{\lambda(Q^{-1})}\prod_{i}B_{Q^{-1}_{i},S_{i}}) \]

\[=\sum\limits_{S}(\sum\limits_{P}(-1)^{\lambda(P)}\prod_{i}A_{S_i,P_i})(\sum\limits_{Q}(-1)^{\lambda(Q)}\prod_{i}B_{Q_{i},S_{i}}) \]

再因为\(\lambda(P_Q)\)与\(\lambda(P)+\lambda(Q)\)的奇偶性相同可得：

\[=\sum\limits_{S}\sum\limits_{P}\sum\limits_{Q}(-1)^{\lambda(P)+\lambda(Q)}\prod\limits_iA_{S_i,P_i}B_{Q_i,S_i} \]

等式右边有：

\[det(C)=\sum\limits_P(-1)^{\lambda(P)}\prod\limits_iC_{i,P_i} \]

又因为\(C(i,j)=\sum\limits_{k=1}^mB(i,k)A(k,j)\)，所以：

\[det(C)=\sum\limits_P(-1)^{\lambda(P)}\prod\limits_i(\sum\limits_{k=1}^mB(i,k)\times A(k,P_i)) \]

设\(R\)是一个从1~m中选\(n\)个数的可重排列，那么就有：

\[=\sum\limits_P(-1)^{\lambda(P)}\sum\limits_R\prod\limits_{i=1}^nB_{i,R_i}A_{R_i,P_i} \]

我们发现，如果\(R\)中存在两个相同元素\(R_i=R_j\)，那么对于\(P\)和交换\(P_i,P_j\)后的\(P'\)，他们会抵消，因此我们可以只用关心\(R\)是无重排列的情况，即先枚举一个大小为\(S\)的子集，再枚举排列，那么有：

\[=\sum\limits_S\sum\limits_Q\sum\limits_P(-1)^{\lambda(P)}\prod\limits_iB_{i,S_{Q_i}}A_{S_{Q_i},P_i} \]

\[=\sum\limits_S\sum\limits_Q\sum\limits_P(-1)^{\lambda(P)}\prod\limits_iB_{Q_i,S_i}A_{S_i,P_{Q_i}} \]

枚举\(P'=P_{Q}\)，可得：

\[=\sum\limits_S\sum\limits_Q\sum\limits_{P'}(-1)^{\lambda(P')+\lambda(Q)}\prod\limits_iB_{Q_i,S_i}A_{S_i,P'_i} \]

\[=\sum\limits_S\sum\limits_P\sum\limits_{Q}(-1)^{\lambda(P)+\lambda(Q)}\prod\limits_iA_{S_i,P_i}B_{Q_i,S_i} \]

证毕。

最后是证明为什么去掉基尔霍夫矩阵最后一行最后一列的是对的（其他情况同理）。

由引理1可得：\(K_0=M_0\times M^T_0\)，再由引理3可知\(\text{det}K_0=\sum\limits_S\text{det}M_0[S]\text{det}M^T_0[S]=\sum\limits_S\text{det}^2M_0[S]\)，再由引理2可知，若边集\(S\)构成生成树，则贡献为\((\pm1)^2=1\)，若不构成生成树则贡献为0，因此\(\text{det}K_0\)就是生成树数量。

例题

1.【模板】Matrix-Tree 定理

题意：求一个图（可能有向有可能无向）的生成树权值和，权值定义为边权的乘积。

思路：模板题，只是要求边权乘积，把边权当成重边就可以了。

2.[JSOI2008]最小生成树计数/[JSOI2010] 巨额奖金

题意：求一个图的最小生成树数量。

思路：首先我们要观察到最小生成树的两个性质：一是对于所有最小生成树，权值相同的边数量相等 ，二是只连接权值\(\leqslant w\)的边时，所有最小生成树的连通性相同。有了这两个性质就很简单了。首先，我们假设现在要处理权值为\(w\)的边，那么就把已经连上了边权\(<w\)的边的连通块缩起来，然后对新图加入权值为\(w\)的边，求出生成树数量，最后根据乘法原理将每一种在最小生成树上出现过的权值的贡献乘起来即可。

3.[省选联考 2020 A 卷] 作业题

题意:对于无向图\(G\)的一棵生成树\(T\)，定义\(T\)的权值为\((\sum\limits_{i=1}^{n-1}w_{e_i})\times \gcd(w_{e_1},w_{e_2},\cdots w_{e_{n-1}})\)，其中\(w\)为边权，求所有生成树的权值和。

思路：考虑莫反：

\[\sum\limits_{T}(\sum\limits_{i=1}^{n-1}w_{e_i})\times \gcd(w_{e_1},w_{e_2},\cdots w_{e_{n-1}}) \]

\[=\sum\limits_T\sum\limits_{i=1}^{n-1}w_{e_i}\sum\limits_{d|w_{e_1},d|w_{e_2}\cdots d|w_{e_{n-1}}}\varphi(d) \]

因此我们枚举\(d\)，去掉原图中边权不是\(d\)的倍数的边建成一张新图，然后就只需求\(\sum\limits_T\sum\limits_{i=1}^{n-1}w_{e_i}\)。但是常规的矩阵树定理只能求边权乘积，那怎么求边权和呢？容易（ ~~其实不容易~~ ）想到把边权换作\(1+w_{e_i}x\)，那么求出乘积后的\(x^1\)项的系数就是原先的边权和，并且我们在计算时只用保留常数项和一次项即可。