最后更新: 2025-01-21 18:38 查看: 93 次反馈能力测评会员8.2元/月赞助

树的定义

## 树的定义
定义7-7.1 一个连通且无回路的无向图称为树，简记T。树中度数为1的结点称为树叶，度数大于1的结点称为分枝点或内点。一个无回路的无向图称作森林，它的每个连通分图是树。

![图片](/uploads/2025-01/bd840b.jpg)
 
 ![图片](/uploads/2025-01/26017e.jpg){width=500px}
 
 树与森林举例
  ![图片](/uploads/2025-01/996b46.jpg)
  
  
  ## 
定理7-7.1 给定图T，以下是树的等价定义：
(1)无回路的连通图
(2)无回路且e=v-1，其中e是边数，v是节点数
(3)连通且e=v-1
(4)无回路，但增加一条新边，得到一个且仅有一个回路
(5)连通，但删去任一边后便不连通
(6)每一对结点之间有一条且仅有一条路

$$
\text { 证明 }(1) \Rightarrow(2)
$$

无回路的连通图 $\Rightarrow$ 无回路且 $e=v-1$
设在图T中，当 $v =2$ 时，连通无回路， T 中边数 $e=1$ ，因此 $e=v-1$ 成立。
假设 $v=k-1$ 时成立，当 $v=k$ 时，因为无回路且连通，故至少有一条边的一个端点 $u$ 的度数为 1 。设该边为 $(u, w)$ ，删去结点 $u$ ，就得到一 $k-1$ 个结点的连通无回路图 $T ^{\prime}$ ，边数
$e^{\prime}=v^{\prime}-1=(k-1)-1=k-2$ ，于是再将结点 $u$ 以及关联边 $( v , w )$ 加到图 $T ^{\prime}$ 中得到原图 $T ^{\prime}$ ，此时 $e=e^{\prime}+1=(k-2)+1=k-1, v=v^{\prime}+1=(k-1)+1=k$ ，故 $e=v-1$ 成立。

证明 $(2) \Rightarrow(3)$
无回路且 $e=v-1 \Rightarrow$ 连通且 $e=v-1$
若T不连通，且有 $k$ 个连通分枝 $T_1, \ldots, T_k(k \geq 2)$ ，
由于每个分图是连通无回路，则可证：如 $T _{ i }$ 有 $v _{ i }$个结点，$v_i<v$ 时，$T_i$ 有 $v_i-1$ 条边，

$$
\begin{aligned}
& v=v_1+v_2+\ldots+v_k \\
& e=\left(v_1-1\right)+\left(v_2-1\right)+\ldots+\left(v_k-1\right)=v-k
\end{aligned}
$$

但 $e=v-1$ ，故 $k=1$ ，与假设 $G$ 不连通即 $k \geq 2$ 矛盾。

$$
\text { 证明 }(3) \Rightarrow(4)
$$

连通且 $e = v -1 \Rightarrow$ 无回路，但增加一条新边，得到一个且仅有一个回路
当 $v=2$ 时，$e=v-1=1$ ，故

免费注册看余下 70%

非VIP会员每天5篇文章，开通VIP 无限制查看

《高等数学》难点解析

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

高等数学测评 函数与极限一元函数微分学一元函数积分学微分方程空间向量与代数多元微分学多元积分学无穷级数

《线性代数》难点解析

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

线性代数测评 行列式矩阵向量空间

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

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

概率统计测评 事件与概率一维随机变量与事件多维随机变量与事件随机变量的数字特征大数定律与中心极限定理统计量与抽样分布参数估计假设检验

上一篇：没有了

下一篇：根树的定义

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