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