最后更新: 2025-01-22 09:44 ● 参与者查看: 17 次纠错分享参与项目词条搜索

数的计数

现考虑标定完全图的生成树的数目。例如标定完全图 $K_3$ 的不同生成树共有 3 棵。一般情况下，标定 $K_n$ 的不同生成树究竟有多少？凯莱（Cayley）于 1889 年首先解决了这个问题，并给出证明，称为凯莱定理。现在我们来证明这个定理，其中图为标定图。

定理10．9 完全图 $K_n \quad(n \geqslant 2)$ 的不同生成树总数 $L(n)$ 为 $n^{n-2}$ 。
证明：在 $K_n$ 的不同生成树中，对于任意给定标号为 $v$ 的顶点，在每一棵生成树中，顶点 $v$的度数为 $1,2, \cdots, n-1$ 中之一。设给定顶点 $v$ 度数为 $k$ 的生成树总数记为 $L(n, k)$ ，那么 $K_n$ 的生成树总数为：

$$
L(n)=\sum_{k=1}^{n-1} L(n, k)
$$

下面我们来计算 $L(n, k)$ 。
设 $S$ 是任意生成树，使顶点 $v$ 有 $d(v)=k-1$ 。从 $S$ 中删去与顶点 $v$ 不关联的任一边 $\{w, y\}$ ，得到两棵子树，其中一棵子树包含顶点 $v$ 和 $w$ ，而另一棵子树包含顶点 $y$ 。现在连接 $v$ 和 $y$ ，得到生成树 $T$ ，使 $d(v)=k$ 。

从生成树 $S$ 通过上述过程得到生成树 $T$ ，称这对生成树 $(S, T)$ 为一个连合。我们的目的是要计算这种连合（ $S, T$ ）的总数。

因为 $S$ 是使顶点 $v$ 有 $d(v)=k-1$ 的生成树，$S$ 可以有 $L(n, k-1)$ 种选取方式。对于选取到的 $S$ ，由上述过程可知，$T$ 是唯一地由边 $\{w, y\}$ 决定，而 $\{w, y\}$ 的选取方式是边数 $n-1$ 减去顶点 $v$关联的边数，即 $n-1-(k-1)=n-k$ 种。所以连合 $(S, T)$ 的总数为 $(n-k) L(n, k-1)$ 。

另一方面，$T$ 是使顶点 $v$ 有 $d(v)=k$ 的生成树，从 $T$ 中删去 $v$ 及其关联的边，分别得到子树 $T_1$ ， $T_2, \cdots, T_k$ 。现在从 $T$ 中删去关联于 $v$ 的那些边中的一边，例如 $\left\{v, w_i\right\}$ ，其中 $w_i$ 在 $T_i$ 中，再连接 $w_i$ 和 $u$ ，其中 $u$ 在 $T_j(i \neq j)$ 中，这样便得到一棵生成树 $S$ ，并且 $d(v)=k-1$ 。从生成树 $T$ 通过这个过程得到生成树 $S$ ，也可以得到所有连合 $(S, T)$ 的总数。

因为 $T$ 是使顶点 $v$ 有 $d (v)=k$ 的生成树，$T$ 可以有 $L(n, k)$ 种选取方式。对于选取到的 $T$ ，由上述过程可知，$T_i$ 的顶点数是 $n_i$ ，除 $v$ 以及 $T_i$ 中的顶点外还有 $n-1-n_i$ 个顶点。所以连接 $T_i$ 中某 $w_i$ 和 $T_j(i \neq j)$中的顶点 $u$ ，共有 $n-1-n_i$ 种方式。因此连合 $(S, T)$ 的总数为：
$L(n, k)\left\{\left(n-1-n_1\right)^{\left.+\cdots+\left(n-1-n_k\right)\right\}=(n-1)(k-1) L(n, k)}\right.$
其中 $n_1+n_2+\cdots+n_k=n-1$（除顶点 $v$ 外尚有 $n-1$ 个顶点），因此 $(n-k) L(n, k-1)=(n-1)(k-1) L(n$ ，
k）
这是一个关于 $k$ 的递推关系，并且 $L(n, n-1)=1$ ，用迭代法求解。
 ![图片](/uploads/2025-01/2a7fbc.jpg)

上一篇：最小生成树

下一篇：有根树与二分树

本文对您是否有用？有用 (0) 无用 (0)