第10章：树
2020-06-09 23:28:28 0 举报AI智能生成
这个是离散数学里关于树这一章的思维导图
作者其他创作
大纲/内容
无向树（树）
定义：连通而不含回路的无向简单图
概念
叶：度数为1的结点
分支点（内部结点）：度数大于1的结点
森林：每个连通分支都是树的无向图
平凡树：平凡图（仅含一个结点的零图）
定理
六个命题等价
G连通而无回路
G中无回路，且m=n-1
G中是连通的，且m=n-1
G中无回路，但在G中任意两结点直接添加一条新边，就会得到唯一的一条基本回路
G是连通的，但删除G的任何一条边后，便不连通（n≥2）
G中每一对结点之间都有唯一的一条基本通路（n≥2）
任意非平凡树都至少含有两片叶
生成树
概念
树枝：生成树的边
弦：不在生成树但是在源图的边
生成树的补：弦的集合
生成树的权：生成树的每个树枝所赋权值之和
定理：一个图存在生成树的充要条件是图是连通的
求生成树的算法
破圈法：删除构成回路的边，总数为m-n+1（因为n个结点，有n-1条树枝）
避圈法：选取与已选取的边不构成回路的边，总共n-1条
广度优先搜索算法（计算机，了解）
最小生成树
定义：生成树的权最小
求最小生成树的算法
避圈法
Kruskal算法：挑选最小权边
Prim算法：选取临接结点
破圈法
有向树
定义：一个有向图，若略去所有有向边的方向得到的无向图是树
根数
定义：有一个结点入度为0，其余入度为1的非平凡有向树
概念
根：入度为0的结点
叶：出度为0的结点
内点：入度为1，出度大于0的结点（非根非叶）
分支点：根+内点，即非叶
结点的层数：根到该结点的通路长度
根数的高：最大的层数
祖先、后代：结点a到b可达，a是b的祖先，b是a的后代
父亲、儿子：<a,b>是根数中的有向边，结点a是b的父亲，b是a的儿子
兄弟：两个结点是同一个结点的儿子，则这两个结点是兄弟
堂兄弟：俩结点的父亲是兄弟
有序树：给边标序号
k元数：每隔分支点至多有k个儿子
k元完全树
根数的以v为根的子树
二元有序树的左儿子、右儿子
二元有序树的左子树、右子树
前缀
前缀码
二元前缀码
赋权二元树
赋权二元树的权
最优树
定理：k元完全数，叶树为t，分支点数为i，则ki=i+t-1
根树的遍历
先根
中根
后根
根树转化为二元树：弟弟变为右儿子
森林转化为二元树
求最优树
赫夫曼算法
根树应用（了解）
计算机的文件系统
波兰符号法与逆波兰符号法
决策树
博弈树
关键道路法
0 条评论
下一页
