第九章树
第九章 树
9.1无向树及生成树1、定义9.1无向树森林（1）连通而不含回路的连通图称为无向树，或树，用T表示。(2)每个连通分支均是树的非连通无向图称为森林，(3)设T=<V,E>为一颗无向树，度为1的顶点称树叶，度为2的顶点称分支点
9.1无向树及生成树 1、定义9.1 无向树 森林 （1）连通而不含回路的连通图称为无向 树，或树，用T表示。 （2） 每个连通分支均是树的非连通无 向图称为森林。 （3） 设T=<V,E>为一颗无向树，度为1 的顶点称树叶，度为2的顶点称分支点
9.1无向树及生成树2、定理9.1设G=<V,E>,/V[=n,E|=m,下列命题是等价的：（1）G连通而不含回路（2）G的每对顶点之间具有唯一的一条路径（3）G是连通的且m=n-1。（4）G中无回路且m=n-1。（5）G中无回路，但在G中任何两个不相等的顶点之间增加一条边，就形成唯一的一条初级回路
9.1无向树及生成树 2、定理9.1 设G=<V,E>,|V|=n,|E|=m,下列 命题是等价的： （1）G连通而不含回路 （2）G的每对顶点之间具有唯一的一条路径。 （3）G是连通的且m=n-1。 （4）G中无回路且m=n-1。 （5）G中无回路，但在G中任何两个不相等的 顶点之间增加一条边，就形成唯一的一条初 级回路
9.1无向树及生成树3、定理9.2设T=<V，E>是n阶非平凡的树则T中至少有2片树叶
9.1无向树及生成树 3、定理9.2 设T=<V，E>是n阶非平凡的树， 则T中至少有2片树叶
9.1无向树及生成树4、定义9.2生成树设G=<V,E>是无向连通图，T是G的生成子图，并且T是树，则称T是G的生成树。（1）G在T中的边称为T的树枝。（2）G不在T中的边称为T的弦。（3）T的所有弦的集合的导出子图称为T的余树
9.1无向树及生成树 4、定义9.2 生成树 设G=<V,E>是无向连通图，T是G的生成 子图，并且T是树，则称T是G的生成树。 （1）G在T中的边称为T的树枝。 （2）G不在T中的边称为T的弦。 （3）T的所有弦的集合的导出子图称为T的 余树