天津理工大学：《离散数学》课程教学资源（PPT课件）第九章 树

第九章树

第九章 树

9.1无向树及生成树1、定义9.1无向树森林（1）连通而不含回路的连通图称为无向树，或树，用T表示。(2)每个连通分支均是树的非连通无向图称为森林，(3)设T=为一颗无向树，度为1的顶点称树叶，度为2的顶点称分支点

9.1无向树及生成树 1、定义9.1 无向树 森林 （1）连通而不含回路的连通图称为无向 树，或树，用T表示。 （2） 每个连通分支均是树的非连通无 向图称为森林。 （3） 设T=为一颗无向树，度为1 的顶点称树叶，度为2的顶点称分支点

9.1无向树及生成树2、定理9.1设G=,/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|=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=是n阶非平凡的树则T中至少有2片树叶

9.1无向树及生成树 3、定理9.2 设T=是n阶非平凡的树， 则T中至少有2片树叶

9.1无向树及生成树4、定义9.2生成树设G=是无向连通图，T是G的生成子图，并且T是树，则称T是G的生成树。（1）G在T中的边称为T的树枝。（2）G不在T中的边称为T的弦。（3）T的所有弦的集合的导出子图称为T的余树

9.1无向树及生成树 4、定义9.2 生成树 设G=是无向连通图，T是G的生成 子图，并且T是树，则称T是G的生成树。 （1）G在T中的边称为T的树枝。 （2）G不在T中的边称为T的弦。 （3）T的所有弦的集合的导出子图称为T的 余树

9.1无向树及生成树4、定义9.2生成树abobQboddO(b)C

9.1无向树及生成树 4、定义9.2 生成树 a b c d e a b c d e a b c d (a) (b) (c)

9.1无向树及生成树5、定理9.3任何连通图G至少存在一棵生成树推论1：设n阶无向连通图G有m条边，则m≥n-1。推论2：设n阶无向连通图G有m条边，T是G的生成树，T"是T的余树，T"中有m-n+1条边

9.1无向树及生成树 5、定理9.3 任何连通图G至少存在一棵生成树。 推论1：设n阶无向连通图G有m条边，则 m≥n-1。 推论2：设n阶无向连通图G有m条边，T 是G的生成树，T’是T的余树，T’中有m-n+1 条边

9.2根树及其应用1、定义9.6根树一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根树（1）入度为0的顶点称为树根(2)入度为1，出度为0的顶点称为树叶。(3)入度为1，出度大于0的顶点称为内点。(4)内点和树根统称为分支点

9.2 根树及其应用 1、定义9.6 根树 一棵非平凡的有向树，如果有一个顶点 的入度为0，其余顶点的入度均为1，则称此 有向树为根树。 （1）入度为0的顶点称为树根。 （2）入度为1，出度为0的顶点称为树叶。 （3） 入度为1，出度大于0的顶点称为内点。 （4）内点和树根统称为分支点

9.2根树及其应用V2O7VV(b)

9.2 根树及其应用 （a） （b） v0 v1 v2 v3 v4 v5 v6 v7 v0 v1 v2 v3 v4 v5 v6 v7

9.2根树及其应用1、定义9.6根树从树根到任意顶点v的通路长度称为v的层数，记为l(v)。层数最大的顶点层数称为树高。(1)层数？VV(2)树高？V5公

9.2 根树及其应用 1、定义9.6 根树 从树根到任意顶点v的通路长度称为v的层 数，记为l(v)。 层数最大的顶点层数称为树高。 v0 v1 v2 v3 v4 v5 v6 v7 （1）层数？ （2）树高？