最后更新: 2025-01-21 18:38 查看: 70 次反馈刷题

树的定义

## 树的定义
定义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$ 中无简单回路。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：没有了

下一篇：根树的定义

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