离散Note

本文最后更新于:几秒前

离散数学

image-20220829101009261

蕴含式 假的意味着一切都是假的(四种形式)

如果猪会飞 那我就是国王

用真值表求取主析取范式和主合取范式

用真值表判断命题符号化是否正确

判定一个公式永真还是用假

求取命题公式之间的关系(等价 蕴含

image-20220901084158087

命题变元

下面第一条与双条件是一样的

image-20220901082220641

image-20220901082141427

利用对偶律和真值表,可以把命题公式简化

把命题规范化的问题,我们称为范式问题

image-20220901092245753

幺元 零元 逆元(基于幺元定义)的唯一性(左右逆元同时存在

image-20220830194310591

封闭、可结合 等价于 半群

image-20220830195148643

描述代数系统间的关系 同态与同构

image-20220830195812803

image-20220830195827047

image-20220830195844364

集合论

朴素集合论——康托尔(理发师悖论

公理集合论(避免了悖论的产生

集合的定义

  • 集合是由指定范围内满足给定条件的所有对象聚集在一起构成,每一个对象成为这个集合的元素
  • 外延公理+空集存在公理+无序对公理+并集公理+幂集公理+无穷公理+替换公理+正则公理+选择公理(ZFC公理化集合论)

ZF代表两个重要的理论创建者,C代表的是选择公理

集合的数学符号(记住常见的集合字母代表,N,Z,Q)

集合的基本概念及公理化集合论 - 知乎 (zhihu.com)

(52 封私信 / 80 条消息) 集合论中的每一条公理背后的动机是什么,少了其中一条会有什么后果? - 知乎 (zhihu.com)

集合的基本特性:

  1. 确定性
  2. 互异性
  3. 无序性

空集 全集

相等关系、包含关系

n元集的子集:

image-20220904100718929

幂集:(亦称为集族,即集合的集合

image-20220904100817970

集合的运算

集合算符

集合运算律\bigcup\bigcap

image-20220904102503998

集合相等的基本思路:证明两个集合互为子集

可数集和不可数集

集合的大小

无穷的层次(阿列夫)

image-20220904103418662

自然数集的定义

皮亚诺公理

image-20220904103510507

冯.诺依曼的自然数定义

image-20220904103718562

集合大小的比较

有限集可以通过而比较元素的数量来比较大小

无限集则需要通过一种一一对应的关系来比较大小

image-20220904104722482

等势

image-20220904103953375

可数集合

image-20220904104059889

image-20220904104538634

不可数集合

image-20220904105619942

(这个开区间是一个参照

序与笛卡尔积

有序组

image-20220906115312438

笛卡尔积

image-20220906115534041

笛卡尔积运算

image-20220906115726181

n重笛卡尔积推广

image-20220906115917435

关系与其表示

image-20220906121157775

关系是一种特殊的集合

二元关系

image-20220906121339803

二元关系运算

image-20220906121445783

二元关系枚举

image-20220906121945513

几种重要关系

image-20220906122118170

定义域和值域

image-20220906122707459

image-20220906122300010

二元关系概念的推广

image-20220906122817399

关系的表示

集合表示

image-20220906123143458

图形表示

ABA\neq B

image-20220906123331741

A=BA=B

image-20220906123437314

矩阵表示

image-20220906180442394

布尔矩阵的并和交运算

image-20220906181213877

布尔矩阵的积运算

image-20220906181907210

布尔矩阵积运算的定义和运算方式与普通矩阵乘法是极其类似的

而两种乘法实际上是可以相互转化的,

在普通矩阵乘法中,我们用B中的列元素与A的行元素对应相乘再相加,从而取得对应位置的元素值;

在布尔矩阵的积中,我们用B的列元素与A的行元素对应合取再析取,从而就能取得相应位置的布尔值

``

关系的运算

关系的并交差补

image-20220906182754832

例子:

image-20220906182910003

关系的复合运算

image-20220906183639791

复合运算的三种关系表示法

集合表示法

关系图

关系矩阵

image-20220906183823198

image-20220906184415540

(布尔矩阵积中的k)

关系的逆运算

image-20220906200721604

逆运算的三种表示法

image-20220906201419007

image-20220906201439199

关系的幂运算

定义幂运算的前提是运算符符合结合律

我们已经知道关系的复合运算符合结合律

image-20220906202107875

R0=IAR^0=I_A,将R的0次幂定义为恒等关系,才能让第三条定义成立

*幂运算的收敛性

image-20220906202705363

幂运算会随着幂次的增加逐渐稳定,呈现出一种趋于收敛和稳定的特性

image-20220906203402168

image-20220906203408161

image-20220906203919383

image-20220906203949457

关系的性质

自反和反自反

image-20220906204409067

image-20220906204604342

判断一个A上的关系R是否具有自反性,就看关系集合内是否具有每个元素的自环

image-20220906204937120

image-20220906204953845

对称和反对称

image-20220906205243159

image-20220906205627580

image-20220906205955849

image-20220906210152644

传递性

image-20220906210316809

image-20220906210656533

注意第二条S依旧满足定义,也就是也就符合传递性;

感性上理解,有点像是,不存在的关系和存在的关系得出了不存在的关系

image-20220906210829857

关系性质的判定定理

对于具体集合上的具体关系,我们可以通过表示法来判定关系性质;而对于抽象集合上的抽象关系,则有一定的局限性,这使我们通过集合运算的角度,对关系性质给出相应的判定定理

image-20220908114644366

证明:

image-20220908115438411

关系性质的判定方法总结

image-20220908115650072

image-20220908120048169

关系性质的保守性

关系可以做集合基本运算和其特有的符合和求逆运算,而我们一般会留意在经过关系运算后,关系原有的性质是否保持,这也就是关系性质的保守性问题

image-20220908120235488

可看出,逆运算和交运算对关系性质是能保持关系性质的

关系的闭包

引言

image-20220908121057205

实际应用意义:研究函数调用关系,构造函数直接调用的闭包,求出最小传递关系。

image-20220908121753729

*关系图求闭包

image-20220908122238939

*利用关系运算求闭包

我们能通过关系图求闭包的思路很好地理解关系运算求闭包的思路

image-20220908122427474

注意,第三条公式,如果A无限集的话,我应该注意关系的幂运算会随着次数的增大趋于收敛稳定

特殊关系

自反、对称、传递这些关系性质的组合分类

等价关系

image-20220908140439071

image-20220908140828175

等价关系图

image-20220908141133923

同余关系的等价证明

image-20220908141414306

image-20220908141657708

tips:

等价类就是一个集合通过集合上的等价关系作出的划分

这些子集都可以形成集合上的全关系

*等价类

image-20220908142606099

从图中我们可以看到等价类的一些特性:

  • 等价类是非空的,至少包含元素自身
  • 等价类有可能有相同的元素,有可能不同
  • 所有等价类的元素就组成了全集

等价类的性质

image-20220908142957251

image-20220908143633191

商集

image-20220908144002610

显然,关系不同,那么他们的商集也是不一样的;

而且,商集可以将集合划分成若干个具有共同性质的组。

应用场合:计算机网络报文转发、数据挖掘、黑盒测试(等价划分法)

计算商集的通用过程

image-20220908144959937

集合划分

通过研究等价关系,我们发现同一个等价类的元素具有相同的性质,我们可以据此将集合元素划分为不同的类别,即集合划分

image-20220908145502806

通过商集,我们可以对集合进行划分

image-20220908150351975

同一个集合有多种不同的划分,不同的等价关系导出不同的划分

反之而言,确定了集合的一种划分,是否可以导出这种等价关系

image-20220908151339594

image-20220908151419041

例子:

image-20220908151810674

image-20220908151834067

命题逻辑

命题的定义:

image-20220904110401423

非命题:

image-20220904110337111

复合命题:

image-20220904110454458

命题连接词:

image-20220904110659971

优先顺序往下降低,同级从左往右

相关应用:

image-20220904111006234

原子命题、命题变元、命题公式

image-20220904111104950

image-20220904111205309

命题公式的分类:

image-20220904111332743

公式相等:

image-20220904111502816

基本等价关系

image-20220904111755946

image-20220904111822692

(矛盾律和排中律通常会放在一起来使用)

image-20220904111926710

相关应用:

image-20220904112605602

范式

范式的定义

image-20220904112808243

替代真值表,命题公式的一种标准形式

image-20220904113257874

tips:

image-20220904113628659

范式存在定理:(求出范式的基本步骤

image-20220904113845441

范式与真值

image-20220904200951109

主范式

image-20220904201136626

极小项

image-20220904201435431

极大项

image-20220904201524934

极小项与极大项性质类似

编码

编码的意义

image-20220904201801421

image-20220904202155934

(可以通过集合来理解)

主析取范式和主合取范式的定义:

image-20220904202541432

主范式的求解

主范式定理:

任何一个公式都有与之等价的主析取范式和主合取范式

范式求解方法:

  1. 公式转换法
    步骤:

    image-20220904202954167

  2. 真值表技术

image-20220904203746523

image-20220904203712864

例子:

image-20220904204139185

范式的相互转换

image-20220904204708864

主范式的性质与应用

image-20220904204915599

例子:

image-20220904205058264

总结:

  • n个命题变元对应着2n2^n个不同的极大项和极小项

  • 若赋予所有的极小项一组完全指派,则只会让其中一项为真,其余都为假;赋予极大项一组完全指派,则只会让其中一项为假,其余都为真;这样看,极小项和极大项的定义方式实为所有完全指派建立了一种一一对应的关系;

  • 求主析取范式时,我们只需选出所有成真指派对应的极小项,再进行析取,就能构造出一个轻易看出命题公式何时为真的公式;而析取范式也类似

  • 对于主析取范式,完全成真指派,会使范式中的极小项中的一项为真,其余为真,从而他们的析取为真;完全成假指派,会使范式中的所有极小项全部为假,从而他们的析取为假。(主合取范式类似

  • 感性上理解,范式显示了一个命题公式的本征;对所有极小项的析取似乎代表着一个事物满足它的一种特征就是这种事物,对所有极大项的合取似乎代表着一个事物所有的特性缺一不可

命题演算和推理形式

推理,即从一组前提合乎逻辑地推出结论的思维过程

定义:

image-20220904210744884

推理的判定定理

image-20220904211017295

例子:

image-20220904211326632

推理定律-基本蕴含关系

image-20220904211642797

演绎法推理

规则:

image-20220904212315445

(规则CP就是前件Q可以与P合取推出R)

三规则+基本等价公式+基本蕴含公式,可作为推理与演绎的基础,从而构造出一个完整的命题推理演算体系

演绎-直接证明法

(演绎就是证明推理有效的一系列过程)

例子:

image-20220904213051514

上面的思路是 P和Q的析取 已经有了前提 接着推出R即可

tips:

I 指的是基本蕴含关系

E指的是基本等价关系

通常是从结论出发倒推(但从前提除法才更加符合数学思维且具有数学意义)

演绎-规则CP证明法

image-20220905183611682

演绎-间接证明法(反证法、归谬法)

image-20220905183959583

tips:

一个矛盾式则必有R¬RR\wedge\neg{R}的形式

反证即是将结论的否定加入到前提中,推出矛盾,从而得证

反证法实际上是CP规则的一种变型

image-20220905185213928

例子:

image-20220905184952087

上述推理为典型的"二难推论"

二难推论:

例如,“如果甲反抗,乙要攻击甲;如果甲不反抗,乙也要攻击甲;甲或者反抗,或者不反抗;乙总是要攻击甲”。

这个二难推理具有以下形式:如果A,那么C;如果B,那么C;A或B,所以,C。

再如,“如果甲承认错误,那么他要接受批评;如果甲不承认错误,那么他要接受惩罚;甲或者承认错误,或者不承认错误;所以,甲或者接受批评,或者接受惩罚”。

这个二难推理具有以下形式:如果A,那么C;如果B,那么D;A或B,所以,C或D。

以上两种二难推理形式,叫做“二难推理构成式”。

二难推理是假言推理与选言推理联合而成的推理,因此,它服从假言推理与选言推理的规则

推理的应用

一、

image-20220905185513134

image-20220905190009018

不是……就是……实际上是异或的关系,但这里用析取不影响推理的结果

二、

image-20220905190148542

image-20220905190908274

从这个例子可以看出,我们区分出了推理的有效性结论的真实性

由于假的前提的存在,我们推出了“不真实”的结论;但推理形式是有效正确的(类似的情况有条件联结词)

image-20220905184131604

谓词逻辑

image-20220905192410627

image-20220905192416488

上述例子,用命题逻辑不足以推出的

个体词和谓词

个体词

image-20220905192756685

谓词

image-20220905192926931

image-20220905193333479

量词

image-20220905193603413

更为准确的表达如下:

image-20220905193930962

谓词逻辑符号化

谓词逻辑符号化的两条规则

image-20220905194300787

量词相关的真值确定

image-20220905194415782

谓词翻译和真值

image-20220905194644926

个体域有限的情况下,有下结论:

image-20220905194917744

符号化实例

单元谓词

image-20220905195236663

多元谓词

image-20220905195542610

**tips:**量词的顺序不可以随意颠倒

将一组语句符号化

image-20220905195933866

image-20220905200034763

谓词合式公式

四类符号

image-20220905200158551

注意3,4

函数符号可以用于表达个体词之间的转换关系,为个体词表示带来了极大的便利性

image-20220905200554435

合式公式

image-20220905200650967

依旧是递归地给出定义

例子:

image-20220905200847471

合式公式何时成为命题,下面会给出回答

自由变元与约束变元

定义

image-20220905201205443

image-20220905201238079

image-20220905201250101

两个规则

image-20220905201423198

例子:

image-20220905201555411

*闭式

公式中没有自由变元

image-20220905201745783

x=0这个公式没有具体的个体域,不封闭,所以不是一个命题

公式的解释

公式的解释和分类

类似于命题与真值表

公式的解释

image-20220905202304176

例子:

image-20220905202449752

公式的分类

!image-20220905203130709

这里类似于命题逻辑中永真和永假;因为我们无法穷举出公式的所有可能,所以我们不能确定一个命题是否永真或者永假,但是我们可以去观察公式是否有效,所以我们这样分类。

谓词公式的可判定性

image-20220905203347514

谓词公式的等价关系

image-20220905203734741

[谓词逻辑]谓词演算的永真式 - 知乎 (zhihu.com)

谓词演算中的基本等价公式(谓词的等价)

image-20220905204317232

image-20220905204440211

观察括号

image-20220905204613187

前束范式

image-20220905204759851

定义

image-20220905204835177

求解步骤

image-20220905205023273

注意分配律是合取还是析取

例子:

image-20220905205221189

谓词演算和推理

推理形式

image-20220905205358560

而,谓词演算也有自己特殊的蕴含关系

推理规律

image-20220905205726534

注意第二蕴含式是合取还是析取

*推理规则

  1. US消去全称量词image-20220905210325974
  2. ES消去存在量词image-20220905210516111
  3. UG添加全称量词image-20220905210641121
  4. EG添加存在量词
    image-20220905210734457

谓词的演绎推理

image-20220906111753322

例子:

三段论

image-20220906112024842

三步走策略

关于ES和US

image-20220906112911469

该推理不正确

image-20220906113058485

谓词推理的难点image-20220906113135468

CP规则证明法

image-20220906113800749

反证法

image-20220906114324938

应用

image-20220906114656828

image-20220906114639290

**tips:**正推和反推要合理利用

代数系统

代数运算

image-20220911201347991

表示法:

image-20220911201412396

例子:

image-20220911201621111

二元运算的定义

image-20220911201730501

例子:

image-20220911201758264

一元运算的定义

image-20220911201847940

拓展:一般意义上的n元代数运算

image-20220911202013121

二元运算律

image-20220911194551725

image-20220911194704002

image-20220911195157925

二元运算律的判定

运算表判定

image-20220911195016594

image-20220911195000708

image-20220911195615570

image-20220911195546153

image-20220911195801890

代数系统

image-20220911200122739

代数系统的判定

image-20220911200252986

代数系统间关系

代数系统间的关系有:同类型,子代数,同态同构

同类型的代数系统

image-20220911200526296

子代数

image-20220911200745760

判定关键:非空子集(找到A中的某个元素属于B)+运算封闭

任何代数的子代数系统一定存在,因为任何一个代数系统都是它自身的子代数(即平凡子代数

image-20220911201104244

同态

满同态

image-20220911202255426

证明:

image-20220911202651389

image-20220911202934225

不同类型的图——图的引入

无向图 有向图

image-20220924163216837

多重图 有环图

image-20220924163233940

利用图论建立数学模型进行分析:

image-20220924163523801

无序对和有序积

image-20220924163728383

与笛卡尔积的定义进行对比

图的定义

image-20220924164024435

V为 结点(node) 或 顶点(vertex),E为边(edge)

例子:

image-20220924164142485

图的表示

  • 图形表示法
  • 集合表示法
  • 邻接矩阵

image-20220924164455985

邻接矩阵

image-20220924165042573

注意结点是有次序的

image-20220924165548938

邻接点与邻接边

image-20220924165728843

一些简单的特殊图

image-20220924165834505

图的分类

根据边有无方向

image-20220924170059464

一般可以把混合图化作有向图,方便问题分析

所以我们讨论的图的类型大致可分为:有向图和无向图

根据有无平行边

image-20220924170429560

我们研究的图主要是:线图和多重图

例子:image-20220924170551506

按有无权值分类

image-20220924170713177

image-20220924170818954

实际应用:

image-20220924171016783

寻找最短路径:行走路径越短,钻孔效率越高

综合分类

根据上面几种分类角度进行综合分类

image-20220924171159377

子图和补图

图是用集合进行定义的,有集合就意味着包含关系,图的子集便是子图

子图

image-20220924171538119

例子:

image-20220924171904250

完全图

image-20220924172117734

补图

image-20220924172329848

例子:

image-20220924172506383

**tips:**画补图要注意,结点不变,还有别漏掉孤立结点

邻接矩阵求补图

image-20220924172835108

补图的应用

image-20220924173624496

握手定理——图论的基本定理

结点的度数

对于结点:

image-20220924175340141

例子:

image-20220924175458473

对于整个图:

image-20220924175757056

邻接矩阵计算度数

image-20220924180032468

image-20220924180120590

握手定理

image-20220924180305281

image-20220924180708044

应用例子:

image-20220924180507699

握手定理的推论——图的一些基本特征

image-20220924180835905

image-20220924181055377

图的度数序列

image-20220924181409505

图的同构

为什么引入图的同构这个概念

image-20220924181541810

定义

image-20220924181708165

例子:

image-20220924181845764

判断同构的关键步骤:

找出结点之间的对应关系,接着观察结点之间的关系是否相同。

容易知道,在两个n个结点的图之间,有n!n!种结点对应关系;n越大,结点对应关系越难找到,这时候我们要结合图的特征去进行判断分析。

同构的必要条件

  • 结点数相同
  • 边数相同
  • 读书相同的结点数相同

tips:

若不满足同构的三个必要条件,则说明两个图不同构;

图同构的三个必要条件不能作为充分条件使用,如下

image-20220924182608645

通路和回路

定义和分类

image-20220924183502886

记号的简化

image-20220924183935382

问题的引入

image-20220924184053880

通路数量

image-20220924184305797

若是多重图,需要对规则做出一些修改

证明:

image-20220924184540754

应用:

1、

image-20220924185014679

image-20220924184959595

image-202209241852338882、

image-20220924185445357

可达性和最短通路

一般来说,我们关心的不是通路的多少,而是关注通路是否存在以及最短通路

可达的定义

image-20220924185835694

可达关系的判定

引理

image-20220924190936673

对于一个具有n个结点的图,如果A1,,An1A^1,……,A^{n-1}aija_{ij}元素都为0,那么An,An+1,A^n,A^{n+1},……里的aija_{ij}元素都会为0;所以我们对A1,An1A^1,……,A^{n-1}进行分析,找到一个aija_{ij}为非零的矩阵的幂,就证明可达。

image-20220924191259559

可达关系判定定理

image-20220924191756151

image-20220924192016548

可达性矩阵

image-20220924191934291

简洁求法:

image-20220924192225479

图接上一小节的例子image-20220924192233957

短程线及距离

image-20220924192504000

结点间距离的判定定理

image-20220924192618119

例子:

image-20220924193112976

无向图的连通性

可达——>连通 个体——>整体

定义

image-20220924193339331

无向图结点间的可达关系

image-20220924193653989

形象来说,如果A可达B,B也可达A;A可达B,B可达C,那么A可达C;而A是反身可达。

注意,任何一个等价关系都对应着一个集合的划分

可达关系——>连通分支

image-20220924193907429

点割集与边割集

image-20220924194036487

所以,我们会去讨论在删除一个或一些结点的情况下,图连通性的变化

图的删除操作

image-20220924194232981

点割集

image-20220924194346374

边割集

image-20220924194529732

注意:点割集和边割集,意味着删掉图中对应的集合里所有元素,才能让产生新分支,缺一不可

点连通度与边连通度

image-20220924194824026

例如,有些图删除一个结点就不连通,有的删除多个结点才会不连通,这意味着图连通的稳定性,而删除边也类似。

image-20220924195128509

例子:

image-20220924195346054

有向图的连通性

无向图结点的可达关系是等价关系;而由于有向图的边具有方向性,有向图结点的可达关系仅仅有自反性和传递性,但不具有对称性,因此不是等价关系

定义与分类

image-20220924195717542

image-20220924200443645

显然,强连通图必然是单向连通图;单向连通图鄙视(弱)连通图。反之都不成立

有向图类型的判定

  • 强连通图:G中存在一条经过所有结点至少一次的回路
  • 单向连通图:G中存在一条经过所有结点至少一次的通路
  • 邻接矩阵判定法:image-20220924201847525

三类连通分支

image-20220924202030638

连通分支的判定

image-20220925091535750

?单向连通分支实际上由强连通分支或若干个弱连通分支组合而形成的

树的模型——引入

组织结构

image-20220925091907230

文件系统

image-20220925091927450

并行处理系统

image-20220925092120057

树的应用

二元搜索树

image-20220925092356165

决策树

image-20220925092458761

前缀码

image-20220925092807580

无向树定义

image-20220925093048558

image-20220925093157849

**tips:**单独一棵树也可以视作森林

树的六种等价定义(性质)

树的其他六种等价定义

设无向图G=<V,E>G=<V,E>V=N|V|=NE=m|E|=m,则下面各个命题都是等价的:

  1. GG连通而不含回路(即GG是树);
  2. GG中无回路,且m=n1m=n-1;
  3. GG是连通的,且m=n1m=n-1;
  4. GG中无回路,但在任二结点之间增加一条新边,就得到唯一的一条基本回路;
  5. GG是连通的,但删除任一条边后,便不连通(n2n\geq{2});
  6. GG中每一对结点间有唯一条基本通路(n2n\geq{2})

采用循环论证去证明六个命题之前的等价关系 :

(1)(2)(3)(4)(5)(6)(1)(1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(4)\Rightarrow(5)\Rightarrow(6)\Rightarrow(1)

image-20220925094723544

image-20220925095041248

image-20220925095453089

树的特点

image-20220925095612228

少一条边,多一条边都不行

树的性质

image-20220925095823680

应用:

image-20220925100022201

握手性质经常与树的性质一起使用

生成树

问题引入

image-20220925100222239

定义

image-20220925100327337

G2为生成树

生成树存在条件

一个图G=<V,E>G=<V,E>存在生成树\LeftrightarrowGG是连通的

image-20220925100641844

生成树算法

求连通图G=<V,E>G=<V,E>的生成树的算法:

  • 破圈法:循环寻找图中回路并删除回路中的一条边,直到删除的边的总数为mn+1m-n+1(寻找回路)
  • 避圈法:循环选取G中一条与已选取的边不构成回路的边,直到选取的边的总数为n1n-1(验证回路是不存在的)

image-20220925101258002

显然,一个连通图的生成树是不唯一的;

上述两种方法很多时候都是不实用的,较常用的算法是用深度优先算法和广度优先算法来求出生成树,

生成树的广度优先算法

image-20220925101911490

例子:

image-20220925102258878

找到每一个点的邻接点,并且进行标记,不需要判断回路,即可找出生成树

生成树在网络中的应用——IP组播

image-20220925102538960

最小生成树

image-20220925102732622

Kruskal算法

image-20220925102932225

image-20220925103252706

按权值从小到大,依次选出不构成回路的边中的最小者,直到选出了11条边(一共有12个结点)

Prim算法

Kruskal需要判定回路,算法复杂度也较高,而Prim算法巧妙地避开了回路的判定,

image-20220925103813897

image-20220925104214967

有向树和根数

  • 一个有向图,在忽略所有有向边方向性后所得到的无向图是一棵树,则这个有向图称为有向树;
  • 一颗非平凡的有向书,如果恰有一个结点入度为0,其余所有结点入度均为1,则称之为根数(root tree)或外向树(outward tree);入度为0的结点称为,出度为0的结点称为,出度大于0的结点(入度不为0)称为内点,而内点和根统称为分支点
  • 在根树中,从跟到任一结点v的通路长度,称为该结点的层数;层数相同的结点被视为在同一层;所有结点的层数中最大的称为根数的高

根数表示——倒置法

image-20220925105553159

树的家族关系

在根树中,若viv_ivjv_j可达,则称viv_iviv_i祖先,vjv_j是viv_i后代;又若<vi,vj><v_i,v_j>是根树的有向边,则称viv_ivjv_j父亲,vjv_jviv_i的儿子;若两节点是同一个结点的儿子,则称两节点是兄弟

有序和k元树

image-20220925110313805

image-20220925110345198

二元有序树

一般k元树和二元树之间非常易于转换,二元树的应用最广泛,所以我们研究的一般是二元树

image-20220925110502102

满k元树性质

image-20220925110642510

应用:

image-20220925110850012

方案一采用多处理器并行方案,只需一次加法运算的时间;而方案二采用串行处理,需要四次加法运算的时间。

树的遍历问题

如何系统地访问树的结点,使得每个结点恰好访问一次,这便是根数的遍历问题

image-20220925111938254

二元树的遍历

image-20220925112127673

表达式的二叉树

image-20220925112449647

image-20220925112555114

image-20220925112701807

二义性举例

image-20220925112932810

根树的遍历

image-20220925113054673

最优树与哈夫曼算法

前缀码

image-20220925113501740

用二元树产生二元前缀码

image-20220925113657961

最优树

image-20220925113845971

哈夫曼算法——最优树求取算法

image-20220925113919565

例子:

image-20220925114024760

前缀码构造

image-20220925114202264

决策问题

image-20220925114306826


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!