Cayley’s formula
1 Cayley’s Formula
$n$个不同的点可以构成$n^{n-2}$棵不同的树(labeled tree).
1.1 Proof of Cayley’s formula by double counting
- 记$n$个不同的点构成的不同的树的数量为$T_n$.
用算两次方法数从空图开始加边直到形成有根树的加边序列数:
法1: 从无根树开始, 选一个根, 再选边加入的顺序: $T_nn (n-1)!=T_n n!$
法2: 从空图开始, 一个一个加边:
- 最初没有边, $n$棵树
- 加了$n-k$边后, $k$棵树, 此时加边$(u,v)$, $u$任选, $v$必须是除了$u$所在树以外的树的根, 所以加边有$n(k-1)$种
- 因此加边序列种数为$\prod_{k=2}^n n(k-1)=n^{n-2}n!$
$T_n n!=n^{n-2}n!$, $T_n=n^{n-2}$
2 Prüfer code
2.1 Encoding
- 当前树$T_i$中最小编号叶结点为$u_i$, 则删除边$(u_i,v_i)$生成新的树$T_{i+1}$, 直到删除所有边($n-1$条).
- $(v_1,\cdots,v_{n-2})$即树$T_1$的Prüfer code.
2.2 Decoding
- 解码的过程就是恢复$(u_1,v_1),\cdots,(u_{n-1},v_{n-1})$的过程
- $v_{n-1}=n$
- $u_i=\text{smallest element of }\{1,2,\cdots,n\}\text{ not in }\{u_1,\cdots, u_{i-1}\}\cup\{v_i,\cdots, v_{n-1}\}$
2.3 Bijection proof of Cayley’s formula
- 双射
- 编码数量为$n^{n-2}$, 因此不同的树的数量为$n^{n-2}$.
3 Kirchhoff’s Matrix-Tree Theorem
$G$的邻接矩阵$A$($n\times n$):
3.1 Graph Laplacian
- $D$为$n\times n$对角阵满足
- 拉普拉斯矩阵$L$定义为$L=D-A$, 即
- incidence matrix $B$($n\times m$)
$L=BB^T$
3.2 The Matrix-tree Theorem
Kirchhoff’s Matrix-Tree Theorem: 对于任何$n$阶连通图$G$, $G$的生成树数量为$det(L_{i,i})$对于$\forall i\in [n]$, 其中$L_{i,i}$是$L$去掉第i行第i列的$(n-1)\times (n-1)$矩阵
- 证明核心公式:
对于$n\times m$矩阵$A$和$m\times n$矩阵$B$. 对于$\forall S\subseteq [m]$满足$|S|=n$, - 剩余证明见讲义
3.3 Cayley’s formula by the matrix-tree theorem
- $n$个不同点构成的树的数量为$K_n$的生成树数量
- 对于$G=K_n$, $\forall i\in[n]$, 满足$det(L_{i,i})=n^{n-2}$