矩陣樹定理

Kirchhoff 矩陣樹定理（簡稱矩陣樹定理）解決了一張圖的生成樹個數計數問題。

本篇記號聲明

本篇中的圖，無論無向還是有向，都允許重邊，但是不允許自環。

無向圖情況

設 \(G\) 是一個有 \(n\) 個頂點的無向圖。定義度數矩陣 \(D(G)\) 為：

\[ D_{ii}(G) = \mathrm{deg}(i), D_{ij} = 0, i\neq j \]

設 \(\#e(i,j)\) 為點 \(i\) 與點 \(j\) 相連的邊數，並定義鄰接矩陣 \(A\) 為：

\[ A_{ij}(G)=A_{ji}(G)=\#e(i,j), i\neq j \]

定義 Laplace 矩陣（亦稱 Kirchhoff 矩陣）\(L\) 為：

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

記圖 \(G\) 的所有生成樹個數為 \(t(G)\)。

有向圖情況

設 \(G\) 是一個有 \(n\) 個頂點的有向圖。定義出度矩陣 \(D^{out}(G)\) 為：

\[ D^{out}_{ii}(G) = \mathrm{deg^{out}}(i), D^{out}_{ij} = 0, i\neq j \]

類似地定義入度矩陣 \(D^{in}(G)\)

設 \(\#e(i,j)\) 為點 \(i\) 指向點 \(j\) 的有向邊數，並定義鄰接矩陣 \(A\) 為：

\[ A_{ij}(G)=\#e(i,j), i\neq j \]

定義出度 Laplace 矩陣 \(L^{out}\) 為：

\[ L^{out}(G) = D^{out}(G) - A(G) \]

定義入度 Laplace 矩陣 \(L^{in}\) 為：

\[ L^{in}(G) = D^{in}(G) - A(G) \]

記圖 \(G\) 的以 \(r\) 為根的所有根向樹形圖個數為 \(t^{root}(G,r)\)。所謂根向樹形圖，是説這張圖的基圖是一棵樹，所有的邊全部指向父親。

記圖 \(G\) 的以 \(r\) 為根的所有葉向樹形圖個數為 \(t^{leaf}(G,r)\)。所謂葉向樹形圖，是説這張圖的基圖是一棵樹，所有的邊全部指向兒子。

定理敍述

矩陣樹定理具有多種形式。其中用得較多的是定理 1、定理 3 與定理 4。

定理 1（矩陣樹定理，無向圖行列式形式） 對於任意的 \(i\)，都有

\[ t(G) = \det L(G)\binom{1,2,\cdots,i-1,i+1,\cdots,n}{1,2,\cdots,i-1,i+1,\cdots,n} \]

其中記號 \(L(G)\binom{1,2,\cdots,i-1,i+1,\cdots,n}{1,2,\cdots,i-1,i+1,\cdots,n}\) 表示矩陣 \(L(G)\) 的第 \(1,\cdots,i-1,i+1,\cdots,n\) 行與第 \(1,\cdots,i-1,i+1,\cdots,n\) 列構成的子矩陣。也就是説，無向圖的 Laplace 矩陣具有這樣的性質，它的所有 \(n-1\) 階主子式都相等。

定理 2（矩陣樹定理，無向圖特徵值形式） 設 \(\lambda_1, \lambda_2, \cdots, \lambda_{n-1}\) 為 \(L(G)\) 的 \(n - 1\) 個非零特徵值，那麼有

\(t(G) = \frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}\)

定理 3（矩陣樹定理，有向圖根向形式） 對於任意的 \(k\)，都有

\[ t^{root}(G,k) = \det L^{out}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n} \]

因此如果要統計一張圖所有的根向樹形圖，只要枚舉所有的根 \(k\) 並對 \(t^{root}(G,k)\) 求和即可。

定理 4（矩陣樹定理，有向圖葉向形式） 對於任意的 \(k\)，都有

\[ t^{leaf}(G,k) = \det L^{in}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n} \]

因此如果要統計一張圖所有的葉向樹形圖，只要枚舉所有的根 \(k\) 並對 \(t^{leaf}(G,k)\) 求和即可。

BEST 定理

定理 5（BEST 定理） 設 \(G\) 是有向歐拉圖，那麼 \(G\) 的不同歐拉回路總數 \(ec(G)\) 是

\[ ec(G) = t^{root}(G,k)\prod_{v\in V}(\deg (v) - 1)! \]

注意，對歐拉圖 \(G\) 的任意兩個節點 \(k, k'\)，都有 \(t^{root}(G,k)=t^{root}(G,k')\)，且歐拉圖 \(G\) 的所有節點的入度和出度相等。

定理證明

前置知識：LGV 引理

定義 \([n]=\{1,2,\cdots,n\}\)，矩陣 \(A\) 的子式 \(A_{[S],[T]}\) 為選取 \(A_{i,j}\pod{i\in S,j\in T}\) 的元素得到的子矩陣。

定義一條邊 \(e\) 的權值為 \(\omega(e)\)。

以下的內向也指根向，表示有向邊的方向指向根。

引理 1（Cauchy–Binet） 給定 \(n\times m\) 的矩陣 \(A\) 和 \(m\times n\) 的矩陣 \(B\)，則有

\[ |AB|=\sum_{|S|=n,S\subseteq[m]}|A_{[n],[S]}||B_{[S],[n]}| \]

證明：考慮建出有向無環圖 \(G(V,E)\)，\(V=L\cup R\cup D\)，
\(L=\{l_1,l_2,\cdots,l_n\}\)，\(R=\{r_1,r_2,\cdots,r_n\}\)，
\(D=\{d_1,d_2,\cdots,d_m\}\)，\(E=E_L\cup E_R\)，
\(E_L=\{(l_i,d_j)\mid i\in[1,n],j\in [1,m]\}\)，\(E_R=\{(d_i,r_j)\mid i\in[1,m],j\in[1,n]\}\)，
\(\omega(l_i,d_j)=a_{i,j}\)，\(\omega(d_i,r_j)=b_{i,j}\)。

與「NOI2021」路徑交點的模型相同，容易發現上式左右兩側計算的都是 \(L\) 到 \(R\) 的不相交路徑組中，交點個數為偶數的方案數減去奇數的方案數，其中 \(S\) 表示路徑組經過的 \(D\) 中的點。

性質 1 Laplace 矩陣 \(L\) 的所有代數餘子式 \(C_{i,j}\) 的值都相等。

證明：刪去第 \(i\) 行後，設列向量是 \(\boldsymbol r_1,\boldsymbol r_2,\cdots,\boldsymbol r_n\)，則有 \(\sum\boldsymbol r_i=\boldsymbol 0\)。

將餘子式 \(M_{i,j}\) 中除了 \(\boldsymbol r_k\) 之外的所有 \(\boldsymbol r_i\) 都加到 \(\boldsymbol r_k\) 上，得到 \(A=[\boldsymbol r_1,\cdots,\boldsymbol r_{j-1},\boldsymbol r_{j+1},\cdots,\boldsymbol r_{k-1},-\boldsymbol r_j,\boldsymbol r_{k+1},\cdots,\boldsymbol r_n]\)。

將 \(-\boldsymbol r_j\) 取反並通過交換兩列移動到 \(\boldsymbol r_{j+1}\) 左邊，得到 \(|A|=M_{i,k}=(-1)^{1+(k-1)-(j+1)+1}M_{i,j}\)，所以 \(C_{i,j}=C_{i,k}\)。

同理，刪去第 \(i\) 列後行向量之和為 \(\boldsymbol 0\)，得到 \(C_{j,i}=C_{k,i}\)。

定理 1（Kirchhoff's Matrix Tree） 對於帶邊權的簡單無向圖 \(G(V,E)\)，若 \(T(V,E_T)\) 是 \(G\) 的生成樹，定義 \(\omega(T)=\prod_{e\in E_T}\omega(e)\)，\(\mathcal T\) 是 \(G\) 所有生成樹的集合，則 \(G\) 的 Laplace 矩陣的所有代數餘子式的值等於 \(\sum_{T\in\mathcal T}\omega(T)\)。

證明：根據性質 1，只需證明 \(C_{1,1}=\sum_{T\in\mathcal T}\omega(T)\)。對於一條邊 \(e=(u,v)\)，定義 \(\zeta(e,u)=v\)，\(\zeta(e,v)=u\)。

定義 \(u_i<u_j\iff i<j\)，\(E=\{e_1,e_2,\cdots,e_{|E|}\}\)，構造關聯矩陣：

\[ A_{i,j}=\begin{cases}\sqrt{\omega(e_j)} & u_i\in e_j\land u_i<\zeta(e_j,u_i) \\ -\sqrt{\omega(e_j)} & u_i\in e_j\land u_i>\zeta(e_j,u_i) \\ 0 & \text{otherwise}\end{cases} \]

容易發現 \(L=AA^T\)，定義 \(A\) 刪去第一行得到 \(B\)，則 \(M_{1,1}=BB^T\)。代入 Cauchy–Binet 公式得到：

\[ M_{1,1}=\sum_{|S|=n-1,S\subseteq[|E|]}|B_{[n-1],[S]}||(B^T)_{[S],[n-1]}|=\sum_{|S|=n-1,S\subseteq[|E|]}|B_{[n-1],[S]}|^2 \]

\(|B_{[n-1],[S]}|\) 的組合意義是對點 \(u_2,\cdots,u_n\)，分別選一條 \(S\) 中的邊，且每條邊都恰好被選一次。若 \(u_i\) 選擇了 \(e_j\)，就看做有向邊 \((u_i,\zeta(e_j,u_i))\)，所以也相當於給 \(S\) 中的邊定向，使得 \(u_2,\cdots,u_n\) 的出度為 \(1\)。

對於存在環的方案，構造對合映射（滿足 \(f(f(x))=x\) 的映射 \(f\)）：取環上點編號最小值最小的環（容易發現環的點不交，所以這樣的環唯一），將這個環上的邊反向。

若環長為奇數，則排列奇偶性不變，關聯矩陣中係數符號變化了奇數個；若環長為偶數，則排列奇偶性改變，關聯矩陣中係數符號變化了偶數個。所以貢獻值相反，出現環的權值都被兩兩抵消，對行列值沒有貢獻。

於是只用考慮不存在環的情況，此時有向圖只能是以 \(1\) 為根的內向樹，此時定向方案唯一（確定了邊集和根），也就是每個點選擇的出邊都唯一，所以 \(|B_{[n-1],[S]}|^2\) 即為該樹的邊權積，求和就得到 \(\sum_{T\in\mathcal T}\omega(T)\)。

性質 2 設 Laplace 矩陣的特徵值為 \(\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_{|V|}\)，則 \(\lambda_{|V|}=0\)。

證明：因為 \(L=AA^T\)，所以 \(L\) 是半正定矩陣，特徵值都非負。而 \(|M|=0\)，所以必定有 \(\lambda=0\)。

定義 \(k\)- 生成森林是圖的一個生成子圖 \((V,E)\)，使得這個子圖有 \(k\) 個連通分量且無環。

定理 2 定義 \(\mathcal T_k\) 表示無向圖 \(G\) 的 \(k\)- 生成森林的集合，\(Q(T)\) 表示森林 \(T\) 的每個連通分量的點數之積，\(L\) 的特徵多項式為 \(P(x)\)，則有

\[ F_k=\sum_{T\in\mathcal T_k}\omega(T)Q(T)=(-1)^{|V|-k}[x^k]P(x) \]

證明：考慮 \(P(x)=\det(xI-L)\)，枚舉排列行列式時，貢獻到 \([x^k]\) 相當於選擇相同編號的 \(k\) 行 \(k\) 列刪去，這些就是每個連通分量的根，其他點選擇出邊連到這些根（類似定理 1 的證明），\((-1)^{|V|-k}\) 表示將負號去掉。

推論 \(F_1=\prod_{i=1}^{|V|-1}\lambda_i\) 是生成樹個數的 \(n\) 倍。

定理 3 內向生成樹計數（見上）

證明：發現定理 1 的證明中用到了兩個關聯矩陣，於是我們考慮使用兩個不同的關聯矩陣 \(A,B\) 承擔不同的功能。

\[ \begin{aligned} A_{i,j}&=\begin{cases}\sqrt{\omega(e_j)} & u_i\text{ is }e_j\text{'s head} \\ -\sqrt{\omega(e_j)} & u_i\text{ is }e_j\text{'s tail} \\ 0 & \text{otherwise}\end{cases} \\ B_{i,j}&=\begin{cases}\sqrt{\omega(e_j)} & u_i\text{ is }e_j\text{'s head} \\ 0 & \text{otherwise}\end{cases} \end{aligned} \]

與定理 1 中不同的是，關聯矩陣 \(B\) 限制了只有邊的起點能選擇這條邊，剩下的討論均與定理 1 相同。

實現

一個無向圖的生成樹個數為鄰接矩陣度數矩陣去一行一列的行列式，可以使用 Gauss–Jordan 消元法。

例如，一個正方形圖的生成樹個數

\[ \begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \end{pmatrix}-\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}=\begin{pmatrix} 2 & -1 & 0 & -1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ -1 & 0 & -1 & 2 \end{pmatrix} \]

\[ \begin{vmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{vmatrix} = 4 \]

可以用高斯消元解決，時間複雜度為 \(O(n^3)\)。

實現

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define MOD 100000007
#define eps 1e-7

struct matrix {
  static const int maxn = 20;
  int n, m;
  double mat[maxn][maxn];

  matrix() { memset(mat, 0, sizeof(mat)); }

  void print() {
    cout << "MATRIX " << n << " " << m << endl;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << mat[i][j] << "\t";
      }
      cout << endl;
    }
  }

  void random(int n) {
    this->n = n;
    this->m = n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) mat[i][j] = rand() % 100;
  }

  void initSquare() {
    this->n = 4;
    this->m = 4;
    memset(mat, 0, sizeof(mat));
    mat[0][1] = mat[0][3] = 1;
    mat[1][0] = mat[1][2] = 1;
    mat[2][1] = mat[2][3] = 1;
    mat[3][0] = mat[3][2] = 1;
    mat[0][0] = mat[1][1] = mat[2][2] = mat[3][3] = -2;
    this->n--;  // 去一行
    this->m--;  // 去一列
  }

  double gauss() {
    double ans = 1;
    for (int i = 0; i < n; i++) {
      int sid = -1;
      for (int j = i; j < n; j++)
        if (abs(mat[j][i]) > eps) {
          sid = j;
          break;
        }
      if (sid == -1) continue;
      if (sid != i) {
        for (int j = 0; j < n; j++) {
          swap(mat[sid][j], mat[i][j]);
          ans = -ans;
        }
      }
      for (int j = i + 1; j < n; j++) {
        double ratio = mat[j][i] / mat[i][i];
        for (int k = 0; k < n; k++) {
          mat[j][k] -= mat[i][k] * ratio;
        }
      }
    }
    for (int i = 0; i < n; i++) ans *= mat[i][i];
    return abs(ans);
  }
};

int main() {
  srand(1);
  matrix T;
  // T.random(2);
  T.initSquare();
  T.print();
  double ans = T.gauss();
  T.print();
  cout << ans << endl;
}

例題

例題 1：「HEOI2015」小 Z 的房間

解矩陣樹定理的裸題。將每個空房間看作一個結點，根據輸入的信息建圖，得到 Laplace 矩陣後，任意刪掉 \(L\) 的第 \(i\) 行第 \(i\) 列，求這個子式的行列式即可。求行列式的方法就是高斯消元成上三角陣然後算對角線積。另外本題需要在模 \(k\) 的整數子環 \(\mathbb{Z}_k\) 上進行高斯消元，採用輾轉相除法即可。

例題 2：「FJOI2007」輪狀病毒

解本題的解法很多，這裏用矩陣樹定理是最直接的解法。當輸入為 \(n\) 時，容易寫出其 \(n+1\) 階的 Laplace 矩陣為：

\[ L_n = \begin{bmatrix} n& -1& -1& -1& \cdots& -1& -1\\ -1& 3& -1& 0& \cdots& 0& -1\\ -1& -1& 3& -1& \cdots& 0& 0\\ -1& 0& -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ -1& 0& 0& 0& \cdots& 3& -1\\ -1& -1& 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n+1} \]

求出它的 \(n\) 階子式的行列式即可，剩下的只有高精度計算了。

例題 2+

將例題 2 的數據加強，要求 \(n\leq 100000\)，但是答案對 1000007 取模。（本題求解需要一些線性代數知識）

解推導遞推式後利用矩陣快速冪即可求得。

推導遞推式的過程：

注意到 \(L_n\) 刪掉第 1 行第 1 列以後得到的矩陣很有規律，因此其實就是在求矩陣

\[ M_n = \begin{bmatrix} 3& -1& 0& \cdots& 0& -1\\ -1& 3& -1& \cdots& 0& 0\\ 0& -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& 0& \cdots& 3& -1\\ -1& 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n} \]

的行列式。對 \(M_n\) 的行列式按第一列展開，得到

\[ \det M_n = 3\det \begin{bmatrix} 3& -1& \cdots& 0& 0\\ -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& \cdots& 3& -1\\ 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n-1} + \det\begin{bmatrix} -1& 0& \cdots& 0& -1\\ -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& \cdots& 3& -1\\ 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n-1} + (-1)^n \det\begin{bmatrix} -1& 0& \cdots& 0& -1\\ 3& -1& \cdots& 0& 0\\ -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& \cdots& 3& -1\\ \end{bmatrix}_{n-1} \]

上述三個矩陣的行列式記為 \(d_{n-1}, a_{n-1}, b_{n-1}\)。
注意到 \(d_n\) 是三對角行列式，採用類似的展開的方法可以得到 \(d_n\) 具有遞推公式 \(d_n=3d_{n-1}-d_{n-2}\)。類似地，採用展開的方法可以得到 \(a_{n-1}=-d_{n-2}-1\)，以及 \((-1)^n b_{n-1}=-d_{n-2}-1\)。
將這些遞推公式代入上式，得到：

\[ \det M_n = 3d_{n-1}-2d_{n-2}-2 \]

\[ d_n = 3d_{n-1}-d_{n-2} \]

於是猜測 \(\det M_n\) 也是非齊次的二階線性遞推。採用待定係數法可以得到最終的遞推公式為

\[ \det M_n = 3\det M_{n-1} - \det M_{n-2} + 2 \]

改寫成 \((\det M_n+2) = 3(\det M_{n-1}+2) - (\det M_{n-2} + 2)\) 後，採用矩陣快速冪即可求出答案。

例題 3：「BZOJ3659」WHICH DREAMED IT

解本題是 BEST 定理的直接應用，但是要注意，由於題目規定「兩種完成任務的方式算作不同當且僅當使用鑰匙的順序不同」，對每個歐拉回路，1 號房間可以沿着任意一條出邊出發，從而答案還要乘以 1 號房間的出度。

例題 4：「聯合省選 2020 A」作業題

解首先需要用莫比烏斯反演轉化成計算所有生成樹的邊權和，因為與本文關係不大所以略去。

將行列式的項寫成 \(w_ix+1\)，最後答案是行列式的一次項係數，因為答案實際上是欽定一條邊之後的生成樹個數 \(\times\) 這條邊的邊權之和，那麼被乘上一次項係數的邊就是被欽定的邊。此時可以把高於一次的項忽略掉，複雜度 \(O(n^3)\)。

「北京省選集訓 2019」生成樹計數是較為一般化的情況：計算生成樹權值之和的 \(k\) 次方之和，用類似方法構造行列式的項即可，具體見洛谷題解。

例題 5：AGC051D C4

解無向圖歐拉回路計數是 NPC 問題，但這題的圖較為簡單，確定了 \(S-T\) 的邊中從 \(S\) 指向 \(T\) 的有多少條，就可以確定其他三條邊的定向方案，然後直接套用 BEST 定理就得到 \(O(a+b+c+d)\) 的做法。

註釋

根向樹形圖也被稱為內向樹形圖，但因為計算內向樹形圖用的是出度，為了不引起 in 和 out 的混淆，所以採用了根向這一説法。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：pw384, s0cks5, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用