Download presentation
Presentation is loading. Please wait.
1
无向树和根树
2
无向树 定义13.1 连通无 回路的无向图称 为无向树，简称 树。每个连通分 支都是树的无向 图称为森林。平 凡图称为平凡树。 在无向树中，悬 挂顶点称为树叶， 度数大于或等于 2的顶点称为分 支点。
3
定理13.1 设G=<V,E>是n阶m条边的无 向图，则下面各命题是等价的：
(3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1. (5) G 是连通的且 G 中任何边均为桥. (6) G 中没有回路，但在任何两个不同 的顶点之间加一条新边，在所得图 中得到惟一的一个含新边的圈.
4
根树的画法——树根放上方，省去所有有向边上的箭头
5
根树 (1) T 为有序根树——同层上顶点标定 次序的根树 (2) 分类 ① r 叉树——每个分支点至多有r 个儿子
6
定理 一棵2叉树产生一个二元前缀码. 推论 一棵正则2叉树产生惟一的前缀码（按左子树标0，右子树标1） 图所示二叉树产生的前缀码为 { 00, 10, 11, 011, 0100, 0101 }
7
定义13.5 T是有向树（基图为无向树） (1) T 为根树——T 中一个顶点入度为0，其余的 入度均为1. (2) 树根——入度为0的顶点 (3) 树叶——入度为1，出度为0的顶点 (4) 内点——入度为1，出度不为0的顶点 (5) 分支点——树根与内点的总称 (6) 顶点v的层数——从树根到v的通路长度 (7) 树高——T 中层数最大顶点的层数 (8) 平凡根树——平凡图
Similar presentations
