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