第十章树
第十章 树
树的实例
树的实例 a e d c b
10.1树及其性质 定义101(树) 个连通无回路的图称为树,记为T 树中度数为1的顶点称为树叶(悬挂点) 度数大于1的顶点称为分枝点或内点。 不相交的树的全体称为森林 平凡图称为平凡树 图10.1
10.1 树及其性质 定义10.1（树） 一个连通无回路的图称为树，记为T。 树中度数为1的顶点称为树叶（悬挂点）。 度数大于1的顶点称为分枝点或内点。 不相交的树的全体称为森林。 平凡图称为平凡树 图10.1
10.1树及其性质 定理10.1 设图7有n个顶点,有下列6条T是树的等价定义 (1)7是无回路的连通图; (2)T是无回路图,且e=n-l,其中e是边数; (3)T是连通图,且e=n-l; (4)T是无回路图,且在T的任何两个不相邻的顶点之 间添加一边,恰得一条回路(称T为最大无回路图) 5)T是连通图,但删去任一边后,便不连通(称T为 最小连通图)。 (6)T的每一对不同的顶点之间有唯一的一条路
10.1 树及其性质 定理10.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); (2)→(3); (3)→(4); (4)→(5); (5)→(6); (6)→(1);
证明方法： （1）（2）； （2）（3）； （3）（4）； （4）（5）； （5）（6）； （6）（1）；