第七章树 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是连通图,用反证法
(3)→(4):在T是连通图,且e=n-的条件下, 证明T是无回路图且在T的任两个不相邻 的顶点之间添加一边,恰得到一条回路。 1)首先证明T是无回路的。 对顶点数n采用归纳法, n=2时e=1,且连通,只能是下图 显然T是无回路的
(3)→(4):在T是连通图,且e=n-1的条件下, 证明T是无回路图,且在T的任两个不相邻 的顶点之间添加一边,恰得到一条回路。 1)首先证明T是无回路的。 对顶点数n采用归纳法, n=2时e=1,且连通, 只能是下图 显然T是无回路的
假设n=k-1时结论成立,考察n=k时,由于T是连通 的,所以每个顶点度数≥(e=k-1)。可以证明至少 存在一个顶点u,使d(u)=1。Why?
假设n=k-1时结论成立,考察n=k时,由于T是连通 的,所以,每个顶点度数1(e=k-1)。可以证明,至少 存在一个顶点u,使 d(u)=1。Why?
2)再证明如果在连通图T的任两个不相邻 顶点之间添加一边,记为{vp,则该边与T 中从v到v的一条路 iyvi1…, Vissr 构成一条回路vpv"…,vs,vv) 若这条回路不唯一,由于T无回路,而 TU{,v}得到了回路,因此另一条回路C 也含有边{v,}
2)再证明如果在连通图T的任两个不相邻 顶点之间添加一边,记为{vi ,vj },则该边与T 中从vi到vj的一条路 (vi ,vi1 ,…, vis,vj ) 构成一条回路(vi ,vi1 ,…, vis,vj ,vi )。 若这条回路不唯一，由于T无回路，而 T∪{vi ,vj }得到了回路，因此另一条回路C' 也含有边{vi ,vj }
(4)→(5):在T是无回路图且在T的任两个 不相邻的顶点之间添加一边,恰得到一条 回路的条件下证明T是连通图,但删去任 一边后,便不连通。 若T不连通,则存在顶点v和v,在v与v之 间没有路。显然若加一边vv不会产 生回路,与假设矛盾。 又由于T无回路则删去任一边便不连通
(4)→(5): 在T是无回路图,且在T的任两个 不相邻的顶点之间添加一边,恰得到一条 回路的条件下证明T是连通图,但删去任 一边后,便不连通。 若T不连通, 则存在顶点vi和vj ,在vi与vj之 间没有路。显然,若加一边{vi ,vj },不会产 生回路,与假设矛盾。 又由于T无回路,则删去任一边,便不连通
(5)(6):在T是连通图但删去任一边后, 便不连通的条件下证明T的每一对不同的 顶点之间有唯一的一条路。 由于T是连通的任两点之间有一条路 如果某两个顶点之间多于一条路,则T中 必含有回路,Why?)删去该回路上任一边, 图仍连通与假设矛盾。 (6)→(1):在T的每一对不同的顶点之间有 唯一的一条路的条件下,证明T是无回路 的连通图。显然图是连通的。若有回路, 则回路上任两点之间有两条路,从而导致 矛盾
(5)→(6): 在T是连通图,但删去任一边后, 便不连通的条件下证明T的每一对不同的 顶点之间有唯一的一条路。 由于T是连通的,任两点之间有一条路。 如果某两个顶点之间多于一条路,则T中 必含有回路,(Why?) 删去该回路上任一边, 图仍连通,与假设矛盾。 (6)→(1): 在T的每一对不同的顶点之间有 唯一的一条路的条件下，证明T是无回路 的连通图。显然图是连通的。若有回路, 则回路上任两点之间有两条路, 从而导致 矛盾