最后更新: 2025-01-22 09:41 ● 参与者查看: 21 次纠错分享参与项目词条搜索

树及其性质

定义 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)$ ，导致矛盾。

上一篇：没有了

下一篇：生成树与割集

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