离散数学---树

目录

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,因此我们就可以根据这个度数等于边数的两倍列方程,m=n-1联立即可求解;

r元正则树其实是一样的逻辑,就是这个内点的度数是r+1,i-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次方个,这个也显示出来我们使用哈夫曼编码的优势;

通过上面的例子,我们也可以知道对于这个不同的数字,在于我们的日常使用中的频率是不一样的,在这个最优二叉树里面,我们经常使用的数字靠近树根,而且这个前缀码简洁,那些不是很经常使用的数字就远离这个树根,而且对应的前缀码就会比较复杂,这个也是变长编码的一大特点。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/689726.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

QGraphicsView实现简易地图20『鹰眼视图-全图显示』

前文链接:QGraphicsView实现简易地图19『迁徙图』 鹰眼视图-全图显示 能够显示所有已加载的瓦片地图,支持当前视口的范围显示器。鼠标在鹰眼视图上移动时,支持是否干预主视图地图加载两种模式,即移动时是否让主视图加载空白处的瓦…

揭秘800G以太网——简介

什么是800G以太网? 800G以太网是一种高带宽以太网标准,每秒可传输800 Gbps(千兆位每秒)的数据速率。它代表了以太网技术的又一进步,旨在满足不断增长的数据传输需求以及处理大量数据的能力。因此,800G以太…

翻译软件就用DT浏览器

翻译软件就用DT浏览器

【纯干货】深度学习各算法的优缺点和适用场景!建议收藏。(上篇)

. .纯 干 货 . 目录 前馈神经网络 1、梯度下降(Gradient Descent) 2、随机梯度下降(Stochastic Gradient Descent, SGD) 3、小批量梯度下降(Mini-batch Gradient Descent) 4、动量(Mo…

【CSS】opacity 父元素设置透明度影响子元素显示效果解决方案

<div class"father"><div class"children"></div> </div>.father{background:#000000,opacity:0.6 } 给父元素设置透明度时&#xff0c;子元素显示效果会搜到父元素透明度的影响&#xff0c;如下图 解决方法&#xff1a; .fathe…

【纯血鸿蒙】——响应式布局如何实现?

前面介绍了自适应布局&#xff0c;但是将窗口尺寸变化较大时&#xff0c;仅仅依靠自适应布局可能出现图片异常放大或页面内容稀疏、留白过多等问题。此时就需要借助响应式布局能力调整页面结构。 响应式布局 响应式布局是指页面内的元素可以根据特定的特征&#xff08;如窗口…

展厅设计中的不同区域划分

1、公共区域 公共区域一般来说是不受限制的区域&#xff0c;这种情况下&#xff0c;会使我们想到的区域是大厅、售卖区、视频播放等&#xff0c;这些公共区域的相关设施比较完善&#xff0c;只是需要普通的安全保护设施及警报设备即可。 2、展览区域 展览区域是参观者能够触及到…

【Car Guide.2】Basic Knowledge

文章目录 【History】【投诉榜】【油 VS 电】【三元锂 vs 磷酸铁锂】【本田、丰田、大众】飞度 【杂谈】 【History】 法国&#xff0c;标志&#xff0c;雪铁龙 美国&#xff0c;通用集团&#xff0c;有别克&#xff08;GL8)&#xff0c;凯迪拉克&#xff0c;雪佛兰&#xff…

Unity3d简单对话系统的实现——使用Dialogue editor完成对话系统

目录 前言 使用方法 1.下载dialogue editor 2.新建空物体 3.对对话内容进行编辑 4.对话画布建立 5.触发对话框代码 结束语 前言 今天是坚持写博客的第21天&#xff0c;很高兴自己可以坚持&#xff0c;也希望能与大家一起进步。我们今天来看unity3d当中的一个可以轻松实…

高通CSIPHY combo mode介绍

目录 使用MIPI Switch 使用高通平台CSIPHY的Combo Mode YYYY使用Combo Mode电路图如下: 如何设置combo PHY mode CSIInfo configuration when camera works in normal mode 平台SoC一般都有多个CSIPHY以满足当前手机相机设计多摄的情况,但是一款SoC CSIPHY的个数也是一定…

使用Aspose技术将Excel/Word转换为PDF

简介&#xff1a;本文将介绍如何使用Aspose技术将Excel文件转换为PDF格式。我们将使用Aspose-Cells-8.5.2.jar包&#xff0c;并演示Java代码以及进行测试。 一、Aspose技术概述 Aspose是一款强大的文档处理库&#xff0c;支持多种编程语言&#xff0c;如Java、C#、Python等。…

C++ | Leetcode C++题解之第137题只出现一次的数字II

题目&#xff1a; 题解&#xff1a; class Solution { public:int singleNumber(vector<int>& nums) {int a 0, b 0;for (int num: nums) {b ~a & (b ^ num);a ~b & (a ^ num);}return b;} };

融云:应用出海新增长引擎,GPT-4o 后的 AI 创新与用户运营

近日&#xff0c;融云与 TikTok、维卓联合在京举办了“十年出海&#xff0c;遇上 AI”私享会。 会上&#xff0c;融云解决方案架构师于洪达带来了《应用出海新增长引擎&#xff0c;AI 创新与用户精细化运营》主题分享&#xff0c;探讨在 AI 技术大潮下应用出海通过创新运营方式…

【C++进阶】深入STL之list:模拟实现深入理解List与迭代器

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ ⏩收录专栏⏪&#xff1a;C “ 登神长阶 ” &#x1f921;往期回顾&#x1f921;&#xff1a;初步了解 list &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀STL之list &#x1f4d2;1. list…

Java | Leetcode Java题解之第132题分割回文串II

题目&#xff1a; 题解&#xff1a; class Solution {public int minCut(String s) {int n s.length();boolean[][] g new boolean[n][n];for (int i 0; i < n; i) {Arrays.fill(g[i], true);}for (int i n - 1; i > 0; --i) {for (int j i 1; j < n; j) {g[i]…

nvm,node不是内部命令,npm版本不支持问题(曾经安装过nodejs)

nvm安装后nvm -v有效&#xff0c;node指令无效 环境变量配置无问题 推荐方案 下载你需要的node版本 Index of /dist/ (nodejs.org) 下载后解压到你的nvm存储版本的位置 cmd进入切换你的使用版本&#xff08;此时你的nodejs是从网上下载的&#xff0c;npm文件是存在的&…

基于SSM+Jsp的高校信息资源共享平台

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

lua vm 五: upvalue

前言 在 lua vm 中&#xff0c;upvalue 是一个重要的数据结构。upvalue 以一种高效的方式实现了词法作用域&#xff0c;使得函数能成为 lua 中的第一类值&#xff0c;也因其高效的设计&#xff0c;导致在实现上有点复杂。 函数 (proto) upvalue 构成了闭包&#xff08;closu…

数据结构(C语言)之对归并排序的介绍与理解

目录 一归并排序介绍&#xff1a; 二归并排序递归版本&#xff1a; 2.1递归思路&#xff1a; 2.2递归代码实现&#xff1a; 三归并排序非递归版本&#xff1a; 3.1非递归思路&#xff1a; 3.2非递归代码实现&#xff1a; 四归并排序性能分析&#xff1a; 欢迎大佬&#…

51单片机-LCD液晶显示

目录 前言: 一. LCD1602模块简介 二. 代码功能实现 三.总结 前言: 本文主要是51单片机的LCD液晶显示,使用的是LCD1602.下面是详细介绍和完整代码,欢迎大家的点赞,评论和关注.感谢. 一. LCD1602模块简介 LCD1602 模块具有以下特点&#xff1a; 显示特点&#xff1a; 可以…