离散数学】树"/>
【离散数学】树
目录
无向树
定义
性质
生成树
子图
生成树
生成树的权
最小生成树
根树
定义
最优二叉树
前缀码
平面图
欧拉公式
无向树
定义
无向树:连通无回路的无向图
树叶:度数等于1的顶点
分支点:度数大于等于2的顶点
性质
设G=<V,E>是n阶m条边的无向图
有下列等价性质
- G是树
- G中任意两个顶点之间存在唯一的路径
- G是无回路的并且m=n-1
- G是连通的并且m=n-1
设T是n阶非平凡的无向树,则T至少有两片树叶
生成树
子图
设G=<V,E>,G'=<V',E'>,若V'∈V,E'∈E,则称G'为G的子图
若V'=V,则称G'为G的生成子图
生成树
如果无向图G的生成子图T是树,则称T是G的生成树
注意:无向图G有生成树当且仅当G是连通图
生成树的权
无向连通带权图G=<V,E,W>,T是G的一棵生成树
T的各边权之和称为T的权,记作W(T)
最小生成树
G的所有生成树中权最小的生成树
求解实例:
根树
定义
有向树:若有向树的基图是无向树 则称这个有向图为有向树
根树:一个顶点入度为0 其余顶点的入度为1的有向树
层数:从树根到顶点的路径长度(路径中的边数)
绘制根树:
在画根树时通常会把树根画在最上方 有向边的方向向下或者斜下方,并省去各边上的箭头
亲戚关系:
祖先,后代,父亲,儿子,兄弟
若T的每个分支点至多有r个儿子,则称T为r叉树
如上图:
V1是V5的祖先 V5是V1的后代
V1是V8的祖先 V8是V1的后代
V2是V5父亲 V5是V2的儿子
V2 V3 V4是兄弟
如上是一个三叉树
最优二叉树
权最小的二叉树
Wi——树叶节点的权值
l(Vi)——层数
求法
前缀码
2元前缀码:0-1符号串构成的前缀码
最佳前缀码:由最优二叉树产生的前缀码
例题:能否构成前缀码 观察长度为2或者3的元素 在集合中查找有无这个元素的顺向子集
例如adc 顺向子集为ad a aa 顺向子集为a
如果出现则不能构成
例题:
平面图
定义:
如果无向图G画在平面上使得除顶点处外无边相交,则称G为可平面图
- 给定平面图G的平面嵌入,G的边将平面划分成若干个区域,每个区域都称作G的一个面。
- 包围每个面的所有边的回路组成该面的边界,边界的长度为该面的次数
- 示例:三角形将平面分为两个区域,即两个面,回路的长度即三条边等于3.该面的次数也就是3
- 平面图所有面的次数之和等于边数的两倍
- 若在非平面图G中任意删除一条边,所得的图是平面图,则称G是极小非平面图
- 示例:K5和K3,3
欧拉公式
定义
连通平面图G的顶点数,边数和面数分别为n,m和r,则有n-m+r=2
设G是n(n>=3)阶m条边的简单平面图,则m<=3n-6
更多推荐
【离散数学】树
发布评论