第11章 树及其应用

11.1 无向树及其性质

1.连通的且不包含圈的图称为树。树中度为1的结点称为叶。

2.树，m = n - 1

3.任何非平凡树至少有2个叶

4.阶大于2的树必有割点

11.2 生成树

1.如果连通图G的生成子图是一个树，则称这个树为 G 的生成树。若T是G的生成树，称T中的边是树枝，不在T中的边称为树补边，G - T称为树补。

2.每个连通图都含有生成树。

3.对任意阶连通图，其边数m ≥ n-1

4.设T是连通图G的生成树，则①G的任何边割集与T至少有一条公共边。②G的任何圈和树补至少有一条公共边。

5.由Kruskal算法（避图法）产生的子图G(S)是n阶连通图G=(V, E)的最小生成图。

6.Kruskal算法

11.3 根树及其应用

1.如果一个有向图G的基图是树，则称G为有向树。

2.外向树（有一个结点入度为0）；出度为0的结点为叶，出度不为0的点称为分枝点。

3.内向树（有一个结点出度为0）；根；叶；分枝点

4.父亲结点（直接先行）；儿子结点（直接后继）；兄弟；祖先（先行）；后裔（后继）

5.m叉树；完全m叉树；如果全部叶点位于同一层次，则称T为正则m叉树

6.若T是完全m叉树，其叶树为t，分枝点数为i，则(m-1) * i = t - 1

7.在根树中，一个结点的道路长度定义为根到这个结点的距离。根树的高度定义为树中最大的结点道路长度。

8.在一个分枝点树木为i的完全二叉树中，设I表示各分枝点道路长度之和，J表示各叶的道路长度之和，则J=I+2*i

9.Huffman最优树

10.前缀码；Huffman树