生成树和计数
定理 3.3.1 凯莱公式 Cayley
有标号的 $n$ 个节点的树一共有 $n^{n-2}$ 种.
\begin{Algorithm}[Prufer 序列] 由树生成 Prufer 序列
每次选取编号最小的叶子, 与其连接的点编号加入序列, 并删除这个叶子. 反复操作直到只剩两个点. \end{Algorithm}
推论 3.3.2
对于任意的正整数列 $d_1,\ldots,d_n$ 满足 $\sum\limits_{i=1}^n d_i=2n-2$, 那么有 $\dfrac{(n-2)!}{\prod_i (d_i-1)!}$ 种有标号树, 满足第 $i$ 个节点的度数恰好为 $d_i$.
定义 3.3.3
定义图 $G$, 的 Laplacian 矩阵为 $L(G)=D-A$, 其中 $D$ 是度数矩阵, $A$ 是邻接矩阵.
定理 3.3.4 矩阵树