Cayley's Formula 與 Prüfer Code

這篇要來聊聊生成樹，在競程最常看到的生成樹題目，除了最小生成樹相關的之外，應該就是計數了。最小生成樹在這一篇聊過，這裡主要就是談談計數。計數就是計算某種東西的數量，本質上就是要能夠和

$\mathbb{N}$ 一一對應 (或 bijection) 而已。國高中的計數就只是算算排列組合數、要分成幾堆之類而已

然而，在樹的計數，因為樹本身的結構很特殊，計數並不是一件簡單的事情。這類關於樹的競程題非常少見，但是每次見到鐵定是難題，尤其那些會跟 Combinatorics 一起出現的怪東西們，更是令人頭痛

這篇筆記會以生成樹作為切入點，來聊聊 Cayley's Formula、Prüfer Code 與克希荷夫的矩陣樹定理，並提供三種證明 Cayley's Formula 的方法

由於有些東西真的太難了，可能不會講要怎麼證明 反正競程能用就好

生成樹

通常我們會討論生成樹，都是在一張一般的圖上討論。如果是樹的話，討論其生成樹沒什麼意義，因為樹的生成樹就是自己

定義

若一棵樹

$T$ 是一張連通圖

$G$ 的子圖，且

$V(T)=V(G)$ (即

$T$ 擁有所有

$G$ 的節點)，則稱

$T$ 為一棵生成樹

下圖就是上圖的生成樹

常見的生成樹例子

深度優先搜尋樹 DFS Tree

深度優先搜尋 (DFS) 會訪問圖上的所有節點。事實上將走訪路徑保留後，可以連接所有節點形成一顆生成樹

廣度優先搜尋樹 BFS Tree

相同地，BFS 也後產生一顆生成樹。此生成樹會有一個性質 : 根節點所有其他點的距離為最短

最短路徑樹

對於一張帶權圖，若利用 Dijkstra's algorithm，由於一定會遍歷整張圖的所有節點，因此肯定會形成一棵生成樹。而如果將出發點

$s$ 視為根，那麼

$s$ 到所有點的路徑邊權總和最小 (俗稱路徑最短)

Prüfer Code

上面介紹完生成樹，可以得知一張圖的生成樹可以有很多種，但是具體來說有幾種呢? 既然圖是一種有限結構，那生成樹的數量也應該是有限的吧! 那具體來說是幾種呢?

直接算真的非常困難，所以我們可以先把所有的樹都編成一組 Prüfer Code，說明 Prüfer Code 與生成樹是 bijection。如此一來，算 Prüfer Code 的數量就等於數生成樹的數量。這樣就可以導出一個公式 (Cayley's Formula) 來解決這個問題

備註 : 這裡我們討論的節點都有數字標籤

演算法

輸入

一棵樹

$T$。其中，節點集合

$S=[n]=\{1,...,n\}\subseteq \mathbb{N}$

輸出

一個由節點標籤組成的序列

$f(T)=(a_1,a_2,...,a_{n-2})$。其中，序列長度為

$n-2$

過程

1. 給一個圖
   $T$、維護序列
   $f(T)$
2. 總共迭代
   $n-2$ 次
3. 在第
   $i$ 次迭代時，把葉子中編號最小節點的鄰居當作
   $a_i$，並刪掉葉子中編號最小節點

舉例說明

給一張

$7$ 個節點的樹、

$f(T)=()$:

$$
刪除

$2$、

$f(T)=(7)$:

$$
刪除

$3$、

$f(T)=(7,4)$:

$$
刪除

$5$、

$f(T)=(7,4,4)$:

$$
刪除

$4$、

$f(T)=(7,4,4,1)$:

$$
刪除

$6$、

$f(T)=(7,4,4,1,7)$:

$$
刪除

$7$、

$f(T)=(7,4,4,1,7,1)$:

刪到只剩

$2$ 個節點就可以停了
輸出 : 序列

$(7,4,4,1,7,1)$

藉由這個演算法，可以知道每棵生成樹都會對應一個序列，接下來你可能會好奇這個序列是否代表唯一的生成樹，事實上答案是肯定的。下一段 Cayley's Formula 的證明中，會證明這件事

Cayley's Formula

公式

對於具有標籤

$[n]=\{1,...,n\}$ 的節點集合，總共有

$n^{n-2}$ 棵樹 (

$n\ge 2$)

舉個例子

當

$n=3$ 時，樹的數量為

$3^{3-2}=3$

注意 : 雖然三棵樹是同構 (isomorphism)，但因為編號不同，所以要視為三種不同生成樹

證明

首先推一下 Prüfer Code 總共有多少種可能 :

已知 Prüfer Code 長度為

$n-2$，序列每個位置可以填入

$n$ 種數字標籤，因此共有

$n^{n-2}$ 種可能

$$

接下來使用歸納法證明 Prüfer Code 與生成樹是 bijection :

令

$S^{n-2}$ 為序列的集合，

$S\subseteq \mathbb{N}$ 是大小為

$n$ 的節點集合

Basis step : 當

$n=2$
存在一個

$2$ 節點的樹，其序列長度為

$0$，是唯一的空序列

Induction step : 當

$n>2$
假設給定一個節點集合

$S$ 與序列

$a$，存在一個唯一的

$T$ 使得

$f(T)=a$
令第一個被刪除的葉節點叫

$x$。根據演算法，我們會紀錄

$a_1$ 在序列中，也就是

$x$ 的唯一鄰居，因此

$T$ 存在一條邊

$x{a}_1$。在刪除

$x$ 後，樹的節點集合變成

$S^{\prime }=S-\{x\}$，然後序列

$a^{\prime }=(a_2,...,a_n)$
根據歸納假設，僅存在一棵節點集合為

$S^{\prime }$ 樹

$T^{\prime }$ 使得

$f(T^{\prime })=a^{\prime }$
因為每棵序列為

$a$ 的樹都有加上

$x{a}_1$，所以僅存在最多一個可能使

$f(T)=a$。再者，將

$T^{\prime }$ 加上

$x{a}_1$ 會形成節點集合

$S$ 與序列

$a$，所以這就是那唯一的可能

由於樹和 Prüfer Code 是 bijection。Prüfer Code 的數量是

$n^{n-2}$，那麼樹的數量也是

$n^{n-2}$

一些拓展

公式 : 固定 degree 的情況下求有幾棵樹

給定一些整數

$d_1,d_2,...,d_n$，加起來為

$2n-2$
總共有

$\frac{(n-2)!}{\mathrm{\Pi }(d_i-1)!}$ 棵節點集合為

$[n]$ 的樹使每個節點

$i$ 都有度數為

$d_i$

推導

在序列中，每個元素

$x$ 都會出現

$d_x-1$ 次，因為在演算法中我們會把與其相連的葉節點都刪掉，直到

$x$ 成為葉節點或是成為最後兩個的其中一個節點。因此，在長度為

$n-2$ 的序列中，每個元素

$i$ 都出現了

$d_i-1$ 次。當我們隨便亂生一個串，總共會有

$(n-2)!$ 個序列，但其中有重複的，所以要除掉

$\mathrm{\Pi }(d_i-1)!$ 次

其實也可以寫成 multinomial coefficient 的形式

$\frac{(n-2)!}{(d_1-1)!(d_2-1)!...(d_n-1)!}={\displaystyle (\genfrac{}{}{0ex}{}{n-2}{d_1-1,d_2-1,...,d_n-1})}$

公式 : 求讓圖連通的方法數

給定

$k$ 個連通塊的大小

$s_1,s_2,...,s_k$，總節點數為

$\sum _{i=1}^k{s}_i=n$
讓圖連通的方法數 :

$n^{k-2}{\mathrm{\Pi }}_{i=1}^k{s}_i$

推導

我不會，但這篇有寫 (因為他重複使用變數，而且步驟有點跳，所以我看不懂)

另一種推導 Cayley's Formula 的方法

因為最近學了生成函數 (generating function)，所以給出用生成函數推導的方法

推導

計算

$n$ 個點上有根樹的數量叫

$t(n)$，若移除了根並觀察子樹，會得到一個遞迴式
天啊這要怎麼觀察

$\begin{array}{rl}t(n+1)& =(n+1)\sum _{k\ge 0}\sum _{i_1+i_2+...+i_k=n,i_j\ge 1}\frac{n!}{i_1!i_2!...i_k!}t(i_1)t(i_2)...t(i_k)\frac{1}{k!}\end{array}$

乘上

$x^{n+1}$ (因為我們要搞生成函數)，然後整理一下

$\begin{array}{rl}\frac{t(n+1)}{(n+1)!}{x}^{n+1}& =\sum _{k\ge 0}\frac{1}{k!}\sum _{i_1+i_2+...+i_k=n,i_j\ge 1}\frac{t(i_1)x^{i_1}}{i_1!}\frac{t(i_2)x^{i_2}}{i_2!}...\frac{t(i_k)x^{i_k}}{i_k!}\end{array}$

這就會是我們的生成函數

$T(x)$ 囉!! (最下面的等式是用泰勒展開搞回去)

$\begin{array}{rl}T(x)& =\sum _{n\ge 0}\frac{t(n+1)}{(n+1)!}{x}^{n+1}=\sum _{k\ge 0}\frac{1}{k!}\sum _{n\ge 0}\sum _{i_1+i_2+...+i_k=n,i_j\ge 1}\frac{t(i_1)x^{i_1}}{i_1!}\frac{t(i_2)x^{i_2}}{i_2!}...\frac{t(i_k)x^{i_k}}{i_k!}\\ & =x\sum _{k\ge 0}\frac{T(x{)}^k}{k!}\\ & =x{e}^{T(x)}\end{array}$

接下來把有

$T(x)$ 的都放到左邊

$\begin{array}{r}T(x)e^{-T(x)}=x\end{array}$

因為它長的很像拉格朗日反演的樣子，所以我們弄弄看拉格朗日反演公式
然後再平移一下多項式

$\begin{array}{rl}[x^n]T(x)& =\frac{1}{n}[x^{-1}]\frac{1}{(x{e}^{-x}{)}^n}\\ & =\frac{1}{n}[x^{-1}]x^{-n}{e}^{nx}\\ & =\frac{1}{n}[x^{n-1}]e^{nx}\\ & =\frac{1}{n}\frac{n^{n-1}}{(n-1)!}\\ & =\frac{n^{n-1}}{n!}\end{array}$

因此，

$t(n)=n^{n-1}$
最後，因為我們算的是有根的樹，但答案應該要是沒有根的樹，因此要除掉一個

$n$
得到

$n^{n-2}$ 為有標籤的節點所能形成的樹的數量

克希荷夫矩陣樹定理 Kirchhoff's Matrix Tree Theorem

克希荷夫的矩陣樹定理可以求出給定一張圖

$G$ 的生成樹數量。若要理解其方法，需要先知道要怎麼用矩陣玩圖論。這種用線性代數玩圖論的領域叫做 Spectual Graph Theory

首先，這裡的圖都假設連通，否則沒辦法討論其生成樹

鄰接矩陣 Adjancency Matrix

這應該資料結構就學過了，放在數學裡也是一樣

鄰接矩陣

$A\in {\mathbb{R}}^{N\times N}$ 是一個方陣。對於每個

$A_{i,j}$ 代表點對

$(i,j)$ 之間的邊數，其中有幾種性質

• 允許自環，每個自環會在對角線上的元素貢獻
  $2$
• 鄰接矩陣在無向圖是對稱的矩陣

度數矩陣 Degree Matrix

度數矩陣

$D\in {\mathbb{R}}^{N\times N}$ 是一個對角矩陣。對於每個節點

$i$，

$D_{i,i}$ 代表其度數，除了對角以外的部分皆為

$0$。其中，自環對度數貢獻為

$2$

拉普拉斯矩陣 Laplacian Matrix

拉普拉斯矩陣

$L=D-A$

有學過向量微積分的話應該很熟悉拉普拉斯運算子，就是梯度的散度那個，它本質上就是相鄰減自身，通通加總，並除掉一個分母。拉普拉斯矩陣也有相似的概念，只是不知道為什麼反過來了

餘因式 Minor

令

$B$ 為一個方陣，

$B$ 的 minor

$M_{i,j}$ 是一個消除第

$i$ 列第

$j$ 行後的矩陣的行列式

餘因子 Cofactor

在上一個定義中，

$B$ 的 cofactor 為

$C_{i,j}=(-1{)}^{i+j}{M}_{i,j}$

引理 1

令

$L$ 為某張無向圖的拉普拉斯矩陣，則所有

$L$ 的 minor 套上絕對值後都相同

引理 2

令

$L$ 為某張無向圖的拉普拉斯矩陣，則所有

$L$ 的 cofactor 都相同

邊收縮 Contraction

如下圖，收縮後的圖

$G.e$

矩陣樹定理 Matrix Tree Theorem

給定一張無向圖

$G=(V,E)$，對於任何節點

$i,j\in \{1,2,...,|V|\}$，

$G$ 的生成樹數量為

$\tau (G)=C_{i,j}$

證明概述

證明有很多版本，這裡採用我比較看得懂的版本，因為太複雜所以大概說一下就好
可能有點不太嚴謹

因為圖都是連通的，考慮一條邊

$e$，當我們在找生成樹的時候，

$e$ 要嘛在樹上要嘛不在 (廢話)。若

$e$ 在樹上，則我們不用考慮他，可以使用邊收縮並找出

$G.e$ 的生成樹數量。若

$e$ 不在樹上，相當於我們忽略它，因此就是要找

$G-e$ 的生成樹數量。因此，可以得到

$\tau (G)=\tau (G-e)+\tau (G.e)$ 有點像是對圖做遞迴的感覺

$$
我們可以對邊做歸納法

Basis case : 整張圖只有兩點與他們之間的

$d$ 條邊

$L=\left(\begin{array}{cc}d& -d\\ -d& d\end{array}\right)$，所以

$\tau (G)=C_{1,1}=L_{1,1}=d$

歸納假設 : 假設對

$G-e$ 與

$G.e$，定理都為真
Inductive step : 我們希望證明定理在

$\tau (G)$ 時為真
將兩節點

$i,j$ 特別挑出來，令

$d_i,d_j$ 為度數，

$d$ 為

$i,j$ 之間的邊數，則我們可以整理出以下行列式。其中，

$r_i$ 與

$r_j$ 是紀錄

$i,j$ 的相關訊息，

$L^{\prime }$ 是拉普拉斯矩陣中沒動到的其他部分

$det(L^G)=\left|\begin{array}{ccc}{d}_i& -d& r_i^T\\ -d& d_j& r_j^T\\ r_i& r_j& L^{\prime }\end{array}\right|$

當然我們也可以整理出

$G-e$ 的行列式

$det(L^{G-e})=\left|\begin{array}{ccc}{d}_i-1& -d+1& r_i^T\\ -d+1& d_j-1& r_j^T\\ r_i& r_j& L^{\prime }\end{array}\right|$

還有

$G.e$ 的行列式

$det(L^{G.e})=\left|\begin{array}{cc}{d}_i+d_j-2& r_i^T+r_j^T\\ r_i+r_j& L^{\prime }\end{array}\right|$

根據引理 1, 2，取

$i,i$ 也會是答案。為了結束歸納法，我們說明

$det(L_{i,i}^G)=det(L_{i,i}^{G-e})+det(L_{i,i}^{G.e})$

也就是

$\left|\begin{array}{cc}{d}_j& r_j^T\\ r_j& L^{\prime }\end{array}\right|=\left|\begin{array}{cc}{d}_j-1& r_j^T\\ r_j& L^{\prime }\end{array}\right|+\left|\begin{array}{c}{L}^{\prime }\end{array}\right|$

這可以用 Laplace expansion 展開來證

最後，根據歸納假設，因為定理在

$G-e$ 與

$G.e$ 為真，因此在

$G$ 也為真
所以

$C_{i,i}^G=C_{i,i}^{G-e}+C_{i,i}^{G.e}=\tau (G-e)+\tau (G.e)=\tau (G)$

舉例說明

下圖總共有八種生成樹

$$
當然我們也可以用矩陣樹定理算出來

$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right),D=\left(\begin{array}{cccc}2& 0& 0& 0\\ 0& 3& 0& 0\\ 0& 0& 3& 0\\ 0& 0& 0& 2\end{array}\right),L=\left(\begin{array}{cccc}2& -1& -1& 0\\ -1& 3& -1& -1\\ -1& -1& 3& -1\\ 0& -1& -1& 2\end{array}\right)$

將第

$2$ 行第

$2$ 列刪掉得到

$L_{2,2}=\left(\begin{array}{ccc}2& -1& 0\\ -1& 3& -1\\ 0& -1& 2\end{array}\right)$

$\begin{array}{rl}det(L^{\prime })& =\left|\begin{array}{ccc}2& -1& 0\\ -1& 3& -1\\ 0& -1& 2\end{array}\right|=2\left|\begin{array}{cc}3& -1\\ -1& 2\end{array}\right|+\left|\begin{array}{cc}-1& -1\\ 0& 2\end{array}\right|=2\times 5-2=8\end{array}$

導出 Cayley's Formula

Cayley's Formula 的條件與矩陣樹定理的條件有點不同

• Cayley's Formula : 有標籤的節點集合
• 矩陣樹定理 : 一張圖
  $G$

若把矩陣樹定理給的

$G$ 換成完全圖

$K_n$，那就相當於變成 Cayley's Formula 的條件，所以就可以計算拉普拉斯矩陣

$D^{K_n}=\left(\begin{array}{cccc}n& n& \dots & n\\ n& n& \dots & n\\ ⋮& ⋮& \ddots & ⋮\\ n& n& \dots & n\end{array}\right),A^{K_n}=\left(\begin{array}{cccc}1& 1& \dots & 1\\ 1& 1& \dots & 1\\ ⋮& ⋮& \ddots & ⋮\\ 1& 1& \dots & 1\end{array}\right)$

$L^{K_n}=D^{K_n}-A^{K_n}=\left(\begin{array}{cccc}n-1& -1& \dots & -1\\ n& n-1& \dots & -1\\ ⋮& ⋮& \ddots & ⋮\\ -1& -1& \dots & n-1\end{array}\right)$

然後再找出 cofactor

$C_{i,j}$ (刪哪行哪列都一樣)，其中 cofactor 的大小只有

$(n-1)\times (n-1)$

$C_{i,j}^{K_n}=\left|\begin{array}{cccc}n-1& -1& \dots & -1\\ -1& n-1& \dots & -1\\ ⋮& ⋮& \ddots & ⋮\\ -1& -1& \dots & n-1\end{array}\right|$

這個鬼東西並不好求，所以可以考慮找 eigenvalue。其中，我們需要用到以下性質 :

• 矩陣行列式就是所有 eigenvalue 相乘
• 矩陣的 trace 是其 eigenvalue 之和
• 若
  $\lambda$ 是矩陣
  $A$ 的 eigenvalue，則
  $\lambda +c$ 是
  $A+cI$ 的 eigenvalue

令

$L^i$ 是這個

$(n-1)\times (n-1)$ 矩陣，考慮

$L^i-nI$ 是一個所有元素都是

$-1$ 的矩陣

• 觀察 trace 會等於
  $(-1)\times (n-1)=1-n$ 又等於所有 eigenvalue 之合
• 所以可以得到
  $L^i-nI$ 的所有 eigenvalue 中只有一個是
  $1-n$，其他都是
  $0$
• 因此所有的 eigenvalue 就是剛才的結果加
  $n$，也就是
  $1,n,...,n$，共
  $n-2$ 個
  $n$ 與
  $1$ 個
  $1$
• 將它們所有 eigenvalue 乘起來就會是行列式的答案，也就是
  $n^{n-2}$

答案就這樣莫名其妙地算出來了

備註

這些東西一出現就肯定是難題，通常跟什麼 generating function、stirling numbers 等等噁心的東西一起出現，所以建議去學 Combinatorics 或是讀 Generatingfunctionology (一本書)

題目練習

OnlineJudge 10843 - Anne's game (Cayley's formula 裸題)
Codeforces 156 D. Clues (拓展 Cayley's formula)
CSES Prüfer Code (Prüfer Code 裸題)
Codeforces 917 D. Stranger Trees (做法很多，要想一下)
Codeforces 1762 E. Tree Sum (動動腦)
CSES Functional Graph Distribution (Cayley's formula，好像也要用 Stirling number，神奇的數學題)
ABC 253 Ex - We Love Forest (矩陣樹定理 + 位元 DP)
ABC 323 G - Inversion of Tree (矩陣樹)
Atcoder jsc2021 G - Spanning Tree (矩陣樹)

---

參考資料

• D.B.West - Introduction to Graph Theory 2/e
• CP-algorithms - Prüfer code
• Geeksforgeeks - Cayley's Formula
• [Tutorial] Generating Functions in Competitive Programming (Part 2)
• 師大演算法筆記 - graph spectrum

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2025/6/25