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

树及其性质

定义 10.1（树） 一个连通无回路的图称为树，记为 T。树中度数为 1 的顶点称为树叶（悬挂点）。度数大于 1 的顶点称为分枝点或内点。不相交的树的全体称为森林。平凡图称为平凡树。
图 10.1 所示是森林，它的每个分支是一棵树。
 ![图片](/uploads/2025-01/159b1e.jpg)
 除了定义 $1 0 . 1$ 给出树的定义外，还有几条等价的树的定义。
定理10．1 设图 $T$ 有 $n$ 个顶点，有下列 6 条树的等价定义。
（1）$T$ 是无回路的连通图。
（2）$T$ 是无回路图，并且 $e=n-1$ ，其中 $e$ 是边数。
（3）$T$ 是连通图，并且 $e=n-1$ 。
（4）$T$ 是无回路图，并且在 $T$ 的任何两个不相邻的顶点之间添加一边，恰得一条回路（也称 $T$ 为最大无回路图）。
（5）$T$ 是连通图，但删去任一条边后，便不连通（也称 $T$ 为最小连通图）。
（6）$T$ 的每一对不同的顶点之间有唯一的一条路。
证明：（1）$\Rightarrow(2)$ ：以顶点数 $n$ 为归纳变量，采用归纳法证明。当 $n=1$ 时，$e=0$ ，所以 $e=n-1$ 成立。假设 $n=k$ 时命题成立，当 $n=k+1$ 时，因 $T$ 是无回路的连通图，由定理8．10，可以推出至少有一个度数为 1 的顶点 $v$ ，在 $T$ 中删去 $v$ 及其关联边 $\{u, v\}$ ，得 $k$ 个顶点的连通无回路的图 $T^{\prime}$ ，由归纳假设，它有 $k-1$ 条边。所以原图 $T$ 边数为 $(k-1)+1$ ，顶点数为 $k+1$ ，所以 $e=n-1$ 。因此 $T$ 是无回路图，并且 $e=n-1$ 。
$(2) \Rightarrow(3):$ 假设 $T$ 不连通，则 $T$ 有 $k$ 个连通分支 $T_1 \cdots, T_k(k \geqslant 2)$ ，顶点数及边数分别为 $n_1, \cdots$ ，

$n_k, e_1, \cdots, e_k$ ，因为每个连通分支是无回路连通图，所以符合树的定义，即 $e_i=n_i-1$ 成立。则 $e=$ $e_1+\cdots+e_k=n-k, k>1$ ，这与 $e=n-1$ 前提矛盾。所以 $T$ 是连通的，并且是 $e=n-1$ 的图。
（3）$\Rightarrow(4)$ ：首先证明 $T$ 无回路。对顶点数 $n$ 采取归纳法；因为 $T$ 是连通的，并且 $e=n-1$ ，所以当 $n=2$ 时，$e=n-1=1$ ，显然 $T$ 是无回路的。假设顶点数为 $k-1$ 时无回路。当顶点数为 $k$时，$e=k-1$ ；则可以证明至少有一个顶点 $v$ ，使 $d(v)=1$ 。因为如果每个顶点的度数至少为 2 ，则所有顶点度数之和大于或等于 $2 k$ ，所以在 $T$ 中至少有 $k$ 条边，导致矛盾。故至少有一个顶点 $v$ ，使 $d(v)=1$ 。删去 $v$ 及其关联边得图 $T^{\prime}$ ，则由归纳假设 $T^{\prime}$ 无回路，再加回 $v$ 及关联边得图 $T$ ，则 $T$ 也无回路。

其次，如果在连通图 $T$ 的任两个不相邻顶点之间添加一边，记为 $\left\{v_i, v_j\right\}$ ，则该边与 $T$ 中从 $v_i$ 到 $v_j$ 的一条路构成一条回路。这条回路是唯一的，因为如果不唯一；则删去该边 $\left\{v_i, v_j\right\}$ 后，在 $T$ 中仍有回路，从而导致矛盾。
（4）$\Rightarrow(5)$ ：若 $T$ 不连通，则在 $T$ 中存在顶点 $v_i$ 和 $v_j$ ，在 $v_i$ 与 $v_j$ 之间没有路。显然，若增加边 $\left\{v_i, v_j\right\}$ 不会产生回路，与假设矛盾。又由于 $T$ 无回路，则删去任意一条边，$T$ 便不连通。
$(5) \Rightarrow(6)$ ：因为 $T$ 是连通的，所以任意两点之间有一条路。如果某两个顶点之间多于一条路，则 $T$ 中必有回路，删去该回路上任一条边，图仍连通，与假设矛盾。所以，每一对顶点间必有唯一的一条通路。
（6）$\Rightarrow(1)$ ：因为每一对顶点有唯一的一条通路，所以图是连通的。若图有回路，则回路上任意两点之间有两条路，从而导致矛盾。

推论 若 $G$ 是 $n$ 个顶点，$\omega$ 个分枝的森林，则 $G$ 有 $n-\omega$ 条边。
证明留作习题。
定理 10.2 在任意一棵非平凡树 $T$ 中，至少有两片树叶。
证明：由于 $T$ 是连通的，对于 $T$ 的任一顶点 $v_i, d\left(v_i\right) \geqslant 1$ ；又因为 $T$ 是图，所以 $\sum_{i=1}^n d\left(v_i\right)=2(n-1)$ 。如果在某树中至多有一个顶点度数为 1 ，其他顶点的度数均大于或等于 2 ，于是 $\sum_{i=1}^n d\left(v_i\right) \geqslant 2(n-1)+1=2 n-1>2(n-1)$ ，导致矛盾。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：没有了

下一篇：生成树与割集

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