最后更新: 2025-01-22 09:44 查看: 112 次纠错评论(0) 课件开VIP

数的计数

现考虑标定完全图的生成树的数目。例如标定完全图 $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)

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：最小生成树

下一篇：有根树与二分树

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