一、无向树的定义

无向树是满足以下条件的连通无向图：

1. 无回路性：图中不含任何简单回路；
2. 连通性：任意两顶点间存在唯一路径；
3. 边数关系：若树有$n$个顶点，则恰有$n-1$条边（称为树公式）。

示例：

• 顶点集$V=\{a,b,c,d\}$，边集$E=\{ab, ac, ad\}$构成树（满足$4$顶点、$3$边）。

二、无向树的六个等价命题

以下命题在无向图$G$中互为等价：

编号	命题描述
1	$G$是无向树（连通且无回路）
2	$G$无回路，且$m = n-1$（$m$为边数，$n$为顶点数）
3	$G$连通，且$m = n-1$
4	$G$连通，但删除任意一条边后不再连通（极小连通性）
5	$G$无回路，但添加任意一条边后产生唯一回路（极大无回路性）
6	任意两顶点间存在唯一简单路径

注：以上命题可互相推导，构成无向树的核心性质体系。

三、生成树

定义

生成树是连通图$G$的一个生成子图且为树，即：

1. 包含$G$的所有顶点；
2. 是$G$的极小连通子图（边数最少）。

性质

• 边数：若原图$G$有$n$顶点，则其生成树恰有$n-1$条边；
• 存在性：连通图至少存在一棵生成树；
• 构造方法：通过破圈法（删除回路中的边）或避圈法（Kruskal算法）生成。

四、例题

例题1：判断无向树

题目：判断图$G=(V,E)$是否为树，其中$V=\{1,2,3,4\}$，$E=\{12,13,14,23\}$。
解：

1. 顶点数：$n=4$，边数：$m=4$；
2. 验证树公式：$m = n-1 \implies 4 \neq 3$，不满足；
3. 结论：$G$不是树（存在回路1-2-3-1）。

例题2：求生成树

题目：为下图构造生成树：

A ———— B ———— C
|      |
D ———— E

解：

1. 破圈法：删除边BE，得到生成树边集$\{AB, BC, AD, DE\}$；
2. 验证：包含所有顶点，无回路，边数$5-1=4$。

例题3：应用生成树计数

题目：完全图$K_4$有多少棵生成树？
解：

1. Cayley公式：完全图$K_n$有$n^{n-2}$棵生成树；
2. 计算：$4^{4-2} = 16$；
3. 结论：$K_4$有16棵生成树。

更新日志

2025/3/16 17:14

查看所有更新日志

• 8739a-update于 2025/3/16

版权所有

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)