第七章树 71树及其性质 定义71:一个连通无回路的图称为树, 记为T。树中度数为1的顶点称为树叶(或 称悬挂点)。度数大于1的顶点称为分枝 点或内点。不相交的树的全体称为森林。 平凡图也可称为平凡树。(平凡图即只有 一个点)
第七章 树 7.1树及其性质 定义 7.1：一个连通无回路的图称为树, 记为T。树中度数为1的顶点称为树叶(或 称悬挂点)。度数大于1的顶点称为分枝 点或内点。不相交的树的全体称为森林。 平凡图也可称为平凡树。(平凡图即只有 一个点)
图a)是一棵树;(b是森林也就是无回 路的图,它的每个分支是一棵树
图 (a)是一棵树；(b)是森林,也就是无回 路的图,它的每个分支是一棵树
除了定义71给出树的定义外还有几个树的等 价定义,即下面的定理。 定理71:设图T有n个顶点有下列6条T是树的 等价定义: (1)T是无回路的连通图; (2T是无回路图,且e=n-1,其中e是边数; (3)T是连通图,且e=n-1; (4)T是无回路图且在T的任两个不相邻的顶点 之间添加一边,恰得到一条回路(称T为最大无回 路图); (5T是连通图,但删去任一边后,便不连通(称T 为最小连通图); (6)T的每一对不同的顶点之间有唯一的一条路
除了定义 7.1 给出树的定义外还有几个树的等 价定义, 即下面的定理。 定理7.1：设图T有n个顶点,有下列6条T是树的 等价定义: (1)T是无回路的连通图; (2)T是无回路图,且e=n-1,其中e是边数; (3)T是连通图,且e=n-1; (4)T是无回路图,且在T的任两个不相邻的顶点 之间添加一边,恰得到一条回路(称T为最大无回 路图); (5)T是连通图,但删去任一边后,便不连通(称T 为最小连通图); (6)T的每一对不同的顶点之间有唯一的一条路
证明:(1)→(2):T是无回路的连通图要证明T是无回路 图,且e=n-1,即证明e=n-1 对顶点数n采用归纳法,n=2时,因为T是无回路的连通图, 显然只能是下图所示: 故结论成立。 假设n=k时结论成立现考察n=k+1时,由于连通无回路以 及定理54 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为的点u它的关联边为 uv}
证明：(1)→(2): T是无回路的连通图要证明T是无回路 图,且e=n-1，即证明e=n-1 对顶点数n采用归纳法,n=2时,因为T是无回路的连通图， 显然只能是下图所示： 故结论成立。 假设n=k时结论成立,现考察n=k+1时,由于连通无回路以 及定理 5.4 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为1的点u,它的关联边为 {u,v}
(2)→(3):T是无回路图,且e=n-1,要证明T是连通 图,且e=n-1。即证明T是连通图用反证法
(2)→(3): T是无回路图,且e=n-1,要证明T是连通 图,且e=n-1。即证明T是连通图,用反证法