生成树和计数

对于任意的正整数列满足 , 那么有种有标号树, 满足第个节点的度数恰好为。

约 1 分钟阅读

本页目录 1 节

生成树和计数 #

定理凯莱公式 Cayley

有标号的 $n$ 个节点的树一共有 $n^{n-2}$ 种.

\begin{Algorithm}[Prufer 序列] 由树生成 Prufer 序列 每次选取编号最小的叶子, 与其连接的点编号加入序列, 并删除这个叶子. 反复操作直到只剩两个点. \end{Algorithm}

推论

对于任意的正整数列 $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$ .

定义

定义图 $G$ , 的 Laplacian 矩阵为 $L(G)=D-A$ , 其中 $D$ 是度数矩阵, $A$ 是邻接矩阵.

定理矩阵树

讨论

正在加载评论…