怎么做英文的网站首页,怎么做快三彩票网站,外贸网络整合营销推广方案,wordpress get_header目录 1.基本概念及其相关运用
2.生成树
3.有向树
4.最优树
5.前缀码 1.基本概念及其相关运用
#xff08;1#xff09;无向树#xff1a;连通而且没有回路的无向图就是无向树#xff1b;
森林就是有多个连通分支#xff0c;每个连通分支都是树的无连通的无向图…目录 1.基本概念及其相关运用
2.生成树
3.有向树
4.最优树
5.前缀码 1.基本概念及其相关运用
1无向树连通而且没有回路的无向图就是无向树
森林就是有多个连通分支每个连通分支都是树的无连通的无向图
树叶就是这个无向图里面的度数是1的节点分支点就是度数大于等于2的节点简单的讲就是没有其他的分支的顶点就叫做树叶还可以从这个地方继续细分的顶点就叫做分支点 2无向树的特点
无向树的三个特点边数等于顶点数减去1连通而且没有回路 3随堂测验对于无向树的进一步理解
无向树的任意的一条边都是桥就是割边任意的两个不同的节点之间只有一条路径可以抵达因为无向树里面要求是没有回路如果有第二条路径可以抵达不就是构成回路了这样的话就不满足这个无向树的定义了无向树就是一个简单图不相邻的节点之间添加一条边就会形成初级的回路 实际问题求解这个树叶的数量我们需要用到握手定理就是度数和等于边数的两倍边的数量根据 边数等于顶点数减去1 这个等量关系得出最后根据握手定理进行求解反正就是要用到这个无向树的性质和握手定理求解树叶的个数
4实战演练 这个试画出六阶的无向树这个六阶的表示是这个树有6个顶点根据这个定理无向树里面的边数等于顶点数减去1说明这个无向树是有5条边我们在根据这个握手定理就可以的出来这个 无向树的度数和就是边数的两倍也就是10这个时候我们再进行列举所有的可能会出现的情况因为是6个顶点最大的数字度数就只能是5否则就会出现重边和环不满足这个无向树的定义了其中的第四种情况是可以画出来两种可能的情况的
这个就是利用握手定理度数和等于边数的两倍边数等于顶点数减去1利用这两个等量关系就可以基本上解决这个无向树里面的所有的相关问题在这个等量关系里面边数是发挥了桥梁的作用因为这个边数是顶点数减去1边数的两倍就是度数和边数这个变量把握手定理和无向树里面的定理给串联了起来
5综合练习 树都是二部图这个是没有问题的因为这个二部图的判定定理就是没有奇数圈而我们的数是不会有回路的所以肯定就没有圈肯定是满足二部图的定义的
哈密顿图的定义就是经过所有的节点返回判定定理就是这个没有奇度数的顶点这个时候我们的数如果有树叶的话肯定是有奇度数的顶点的不一定是欧拉图树里面的平凡树是哈密顿图也是欧拉图其他的数都不是哈密顿图和欧拉图
平面图的要求就是不交叉这个树肯定不会交叉我们正常情况下去画一棵树都是不会交叉的Krs就是一个二部图rs分别表示的是两个不同的集合里面的节点的个数k10就是一个数只有一片树叶的树k11和k12都是树所以这个krs有的是树有的不是树
2.生成树
1生成树和余树 对于右边的一个平面图包括这个红色的和黑色的如果这个平面图的生成子图是一棵树我们就把这个生成子图叫做这个平面图的生成树生成树里面涉及到这个平面图里面的边我们叫做数值没有包括到生成树里面的边我们叫做弦这些弦组成的图形叫做余树
什么是生成子图首先这个生成子图肯定是一个平面图的子图这个是很明显的其次生成子图还需要满足这个生成子图需要包括这个原来的平面图上面的所有的顶点而且没有重边没有环实际上对于一个图而言是可以有很多个生成子图的所以一个连通图可以有很多个不同的生成树
虽然这个生成子图剩下的弦的集合叫做余树但是这个并不是真正的树因为显然这个余树是不联通的不符合树的定义
2最小生成树
我们上面介绍的生成树是可能有多个的这些情况里面的这个权重最小的就是最小生成树最小生成树同样也不是唯一的
这个求解最小生成树的算法有这个避圈法这个方法的主要逻辑就是躲避开所有的圈按照从小到大的权重进行相应的排列不能形成圈满足这个树的定义 3.有向树
1有向树就是指那些不关注方向的情况下这个是一棵树我们就可以称之为有向树 有向树里面有这个根数只有一个入度是0的顶点其余的顶点的入度是1这个入度是0的顶点我们称之为树根
这个树根就是这个图里面的最上面的那个点出度是0的节点我们称之为树叶出度大于等于1 的节点我们叫做内点内点和树根就组成了这个分支点这个树高和树的层数也是我们关注的这个定义和我们在数据结构里面的定义是有所区别的我们这里定义的树高指的就是从根树开始经过的边的个数 所以这个图里面的红色节点的层数就是3因为这个树根只需要经过三条边就可以到达这个节点的位置 2根树的分类 3随堂演练
这个题目上面的五元正则树表示这个树如果有子节点那么就必须要有5个子节点我们根据题目的要求画出这个正则树分支点就是这个树根和内点的总称这个图里面有1个树根两个内点所以这个分支点的个数就是3个 4根树的相关证明
这个二元正则树就是如果有节点需要有两个节点第一个证明就是用的握手定理和这个边数树叶数和这个顶点数之间的转换我们需要先画出来这个已知的图形射出一个变量n表示这个树的顶点的数量根据这个握手定理树根的度是2树叶的度是1剩下的这个内点的个数就是n-1-t其中这个里面1表示的就是树根t就是这个树里面的树叶的数量剩下的就是内点一个内点的度是3因此我们就可以根据这个度数等于边数的两倍列方程mn-1联立即可求解
r元正则树其实是一样的逻辑就是这个内点的度数是r1i-1求出来的就是这个内点的数量第一个r表示的就是这个树根的度数第三个t表示的就是所有的树叶的度数和
我们通过这连个证明就可以发现只要是相关的题目必须同时拥有边数和顶点数这两个变量第一个是给出来了边数我们需要自己设一个变量n表示顶点数第二个是给出了分支节点的个数树叶的个数实际上就是给出了所有的节点的个数我们需要定义一个变量m表示边数 4.最优树
1权重乘上对应的长度求和就是该带权二叉树的权这里的权重求和并不是这个树上面的所有节点而是树叶节点在所有的二叉树里面权值最小的我们称之为最优二叉树
2哈夫曼算法求解最优树问题 这个算法就是在原来的权重集合的基础上面不断的更新这个权重让这个最小的两个权重组成新的 权重集合不断的更新这个分支节点和树叶直到形成一个完整的树为止 3算法运用 这个题目就是哈弗曼编码的一个应用题目上面给出的就是出现的权重 和对应的频率我们就是根据这个频率的大小进行排序的首先按照从小到大的顺序进行排列选出来这个权重最小的59组成14重新对于这个权重集合进行排序再从这个剩下的5个权重里面选择最小的12和13相加得到25再对于这个集合重新排列接下来就是把这个14 16组成新的权重依次进行下去直到形成最终的最优树为止
实际上我们可以发现这个最优树上面除了我们的权重之外还有这个01这些标识这个就是我们接下来要介绍的前缀码的知识
5.前缀码
1相关定义 前缀码就是一个集合里面的某些元素是不是其他某个元素的前缀码这个如果是的话就会出现歧义的现象因此这个我们把如果这个集合里面没有一个序列是另外的一个序列的前缀我们就把这样的序列结合叫做前缀码
2前缀码的定理 这样我们学习了前缀码之后就可以使用这个前缀码解决上面的问题了这个01就是一种二叉的标识我们根据这个就可以写出任意的二叉树的前缀码同理我们根据任意的一个前缀码都是可以画出这个与之对应的二叉树的
3实际应用 上面的这个就是一个实际的问题通信里面的八进制的不同的数字的使用的次数是不一样的这个是用我们使用哈夫曼算法对于这个问题求解他的最优树他的百分比就可以理解为这个对应的权重按照上面的方法不断地合并并对于这个新的序列集合排序得到了这个最优树我们通过这个树叶节点的权重乘上对应的层数从树根开始到这个节点的经过的边数得到的就是285平均下来的一个就是2.85,我们如果想要传输10的n次方数据就需要二进制数字2.85*10的n次方个但是使用等长码就需要3*10的n次方个这个也显示出来我们使用哈夫曼编码的优势
通过上面的例子我们也可以知道对于这个不同的数字在于我们的日常使用中的频率是不一样的在这个最优二叉树里面我们经常使用的数字靠近树根而且这个前缀码简洁那些不是很经常使用的数字就远离这个树根而且对应的前缀码就会比较复杂这个也是变长编码的一大特点。
