无向树及其性质

分支结点：度数>=2的结点。

无向树：连通无回路的无向图。

森林：每个连通分支都是树的无向图。

叶子结点：度数为1的结点。

无向树的等价定义

定理: 设 G=<V,E>是n阶m边的无向图，以下命题是等价的 :

• G是树；
• G中任意两个顶点存在唯一的路径。
• G中无回路，且m=n-1
• G是连通的，且m=n-1
• G是连通的且G中任何边都是桥。
• G中无回路，但在任何两个不同的顶点之间加一条边，在所得图中得到唯一的一个含新边的回路

定理: 设T是n阶非平凡的无向树，则T中至少含有两片树叶

生成树

 生成树的定义

• G的生成树：T是G的子图并且是树。
• 生成树T的树枝：T中的边。
• 生成树T的弦：不在T中的边。
• 生成树T的余树T补：全体弦组成的集合的导出子图。（T补并不是一棵树）

生成树存在的条件

• 定理10-1：无向图具有生成树当且仅当G连通。
• 推论1：G是n阶m边的无向连通图，那m>=n-1
• 推论2：T补的边数为m-n+1

例题：G有6个结点，10条边的连通图，删去多少条边，才得到一颗生成树？

10-6+1 = 5，即删除T补

基本回路系统

最小生成树

这部分内容见数据结构与算法内容

根树及其应用

这部分内容主要也是在数据结构与算法中考察

尤其考察到了HuffmanTree的应用 以及树的遍历方式

并不多说什么!!!

1. • 有向树:一个有向图，略去图中所有的有向边的方向得到的无向图如果是一棵树，则称其为有向树
   • 有孩子的顶点称为内点，根是内点除非它是图中唯一的顶点，也即入度为1出度大于0的顶点称为内点，内点和根统称为分支点
   • 在根树中，从根到任一结点的通路的长度称为该结点的层数。所有顶点的最大层数称为树高。
2. 设T为根数，若将T中层数相同的顶点都标定次序，则称T为有序树。
3. r叉树：若T每个分支点至多有r个儿子，则称T为r叉树
4. 若r叉树是有序的，则称它为r叉有序树
5. 若T的每个分支点都恰好有r个儿子，则称T为r叉正则树；又若T是有序的，则称它为r叉正则有序树。
6. 若T是r叉正则树，且每个树叶的层数均为树高，则称T为r叉完全正则树。
7. 权：树的权指的树中的结点被赋予的一个有某种意义的数,这个数我们就称它为权.
8. 带权w1,w2…wi的2叉树中，权最小的2叉树称作最优2叉树。