最后更新: 2025-01-21 18:38 查看: 140 次纠错评论(0) 课件开VIP

树的定义

## 树的定义
定义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$ ，故 $T$ 必无回路。如增加一边得到且仅得到一个回路。设 $v=k-1$ 时命题成立。
当 $v=k$ 时，因为 $T$ 是连通的，$e=v-1$ ．故每个结点 $u$ 有 $\operatorname{deg}(u) \geq 1$ ，可证明至少有一个结点 $u_0$ ，使 $\operatorname{deg}\left(u_0\right)=1$ 。否则，所有结点 $u$ 有 $\operatorname{deg}(u) \geq 2$ ，则 $2 e \geq 2 v$ 即 $e \geq v$ ，与假设 $e=v-1$ 矛盾。删去 $u_0$ 及其关联的边，得到新图T＇，由归纳假设可知 $T ^{\prime}$ 无回路，在 $T ^{\prime}$ 中加入 $u _0$ 及其关联边又得到 T ，故 T 是无回路的。若在连通图 T 中增加新边 $\left(u_i, u_j\right)$ ，则该边与 $T 中 u_i$ 到 $^2 u_j$ 的一条路构成一个回路，则该回路必唯一，否则若删去此新边T中有回路，矛盾。

证明 $(4) \Rightarrow(5)$
无回路，但增加一条新边，得到一个且仅有一个回路 $\Rightarrow$ 连通，但删去任一边后便不连通

若图丁不连通，则存在结点 $u_i$ 与 $u_i$ 两者间没有路，显然若加边 $\left\{u_i, ~ u\right\}$ 不会产生回路，与假设矛盾。又由于T无回路，去删去任一边，图就不连通。

证明 $(5) \Rightarrow(6)$
连通，但删去任一边后便不连通 $\Rightarrow$ 每对结点之间有一条且仅有一条路

由连通性可知，任两结点间有一条路，若存在两点，在他们之间有多于一条的路，则T中必有回路，删去该回路上任一条边，图仍是连通的，与（5）矛盾。

证明 $(6) \Rightarrow(1)$
每对结点之间有一条且仅有一条路 $\Rightarrow$ 无回路的连通图

任意两结点间有唯一一条路，则图T必连通，若有回路，则回路上任意两点间有两条路，与（6）矛盾。

## 树中的通路
 设 $T$ 是树，则 $\forall u , v \in V _{ T }, T$ 中存在唯一的 uv简单通路。
证明：$T$ 是连通图，$\therefore \forall u , v \in V _{ T }, T$ 中存在uv－简单通路。
假设 $T$ 中有两条不同的uv－简单通路 $P _1, P _2$ 。不失一般性，存在 $e =(x, y)$ 满足： $e \in P _1$ 但 $\notin P _2$ ，且在路径 $P _1$ 上 $x$ 比 $y$ 靠近 $u ^2$ 。令 $T^*=T-\{ e \}$ ，则 $T^*$ 中包含 $P _2$ ，于是 $\left( P _1\right.$ 中的 $x u -$ 段 $)+ P _2+\left( P _1\right.$ 中的 $v y-$段）是 $T^*$ 中的 $x y$－通路，$\therefore T^*$ 中含 $x y$－简单通路（记为 $P ^{\prime}$ ），则 $P ^{\prime}+ e$ 是 $T$ 中的简单回路，与树的定义矛盾。
 ![图片](/uploads/2025-01/89ecde.jpg)
 
## 有关树的几个等价命题
－设 $T$ 是简单无向图，下列四个命题等价：
（1）$T$ 是不包含简单回路的连通图。／／树的定义
（2）$T$ 中任意两点之间有唯一简单通路。
（3）$T$ 连通，但删除任意一条边则不再连通。
（4）$T$ 不包含简单回路，但在任意不相邻的顶点对之间加一条边则产生唯一的简单回路。
备注：
树是边最少的连通图
树是边最多的无简单回路的图

## 树中边和点的数量关系
设 $T$ 是树，令 $n =\left| V _{ T }\right|, m =\left| E _{ T }\right|$ ，则 $m=n-1$ 。
明．对 $n$ 进行归纳证明。当 $n =1, T$ 是平凡树，结论显然成立假设当 $n \leq k$ 是结论成立。

若 $n = k +1$ 。因为 $T$ 中每条边都是割边，任取 $e \in E _T, T-\{ e \}$ 含两个连通分支，设其为 $T_1, T_2$ ，并设它们边数分别是 $m _1, m_2$ ，顶点数分别是 $n_1, n_2$ ，根据归纳假设：$m_1=n_1-1, m_2=n_2-1$ 。注意： $n _1+ n _2= n , m _1+ m _2= m -1$ 。

$$
\therefore m=m_1+m_2+1=n-1 \text { 。 }
$$

## 连通图边数的下限
 顶点数为 $n ( n \geq 2)$ 的连通图，其边数 $m \geq n-1$ 。
（对于树，$m=n-1$ ，＂树是边最少的连通图＂）
 证明：对 $n$ 进行一般归纳。当 $n=2$ 时结论显然成立。
设 G 是边数为 m 的连通图，且 $\left| V _{ G }\right|= n >2$ 。任取 $v \in V_{ G }$ ，令 $G^{\prime}=G-v$ ，设 $G^{\prime}$ 有 $\omega(\omega \geq 1)$ 个连通分支 $G_1, G_2, \ldots, G_\omega$ ，且 $G_i$ 的边数和顶点数分别是 $m_i$ 和 $n_i$ 。
我们有 $n=n_1+n_2+\ldots+n_\omega+1, m \geq m_1+m_2+\ldots+m_\omega+\omega$（每个连通分支中至少有一个顶点在 $G$ 中与删除的 $v$ 相邻）。
由归纳假设， $m _{ i } \geq n _{ i }-1( i =1,2, \ldots \omega)$ 。
所以： $m \geq m _1+ m _2+\ldots+ m _\omega+\omega \geq n _1+ n _2+\ldots+ n _\omega-\omega+\omega= n -1$ 。

## 与边点数量关系有关的等价命题
－设 $T$ 是简单无向图，下列三个命题等价：
（1）$T$ 是树。
（2）$T$ 不含简单回路，且 $m=n-1$ 。
（3）$T$ 连通，且 $m=n-1$ 。
－（1）$\Rightarrow(2)$ ，已证。
－$(2) \Rightarrow(3)$ ，若不连通，分支数 $\omega \geq 2$ ，各分支为树（无简单回路，连通），则 $m = n -\omega< n -1$ ，矛盾。
－（3）$\Rightarrow(1)$ ，设 e 是 $T$ 中任意一条边，令 $T ^{\prime}= T - e$ ，且其边数和顶点数分别是 $m^{\prime}$ 和 $n$ ，则 $m^{\prime}=m-1=n-2<n-1, ~ \therefore T^{\prime}$ 是非连通图。因此， G 的任意边均不在简单回路中，$\therefore G$ 中无简单回路。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：没有了

下一篇：根树的定义

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