离散数学·环路空间、断集空间、根树

发布于：2022-10-20 ⋅ 阅读:(948) ⋅ 点赞:(0)

环路空间

环路

在这里插入图片描述

圈是环路

单看这一页还是有点看不懂

定理

在这里插入图片描述

环和运算就是对称差，删掉2个图中公共的边

在这里插入图片描述

例

在这里插入图片描述
基本回路系统+所有基本回路系统的环和
然后再并起来

断集空间

在这里插入图片描述
注意最后一句，帮助理解

例

在这里插入图片描述
前2个割集那里应该是想要写断集的，但是割集也是断集，所以没问题
第3个是断集，但不是割集

还是比较好理解的
基本割集系统+所有基本割集系统的环和

根树

在这里插入图片描述
注意有向树

在这里插入图片描述
注意是有向树，只不过省去了方向

例

在这里插入图片描述
注意方向一定要可以顺下来

其他概念

在这里插入图片描述

r叉数——最大出度数不超过r
正则~~——除了树叶以外的结点出度数都是r
后面的涉及的不多

定理

在这里插入图片描述

握手定理：d⁺(v)=d^-(v)=m

用握手定理的话很好解释

例

在这里插入图片描述

根子树、左右子树

在这里插入图片描述

周游、前序、中序、后序

在这里插入图片描述
周游有点像哈密顿图（但没有回路）
经典的前序、中序、后序

前缀码

在这里插入图片描述
前缀 —— 不能放在另一个码前面（00不是010的前缀，01是010的前缀）

最佳前缀码

在这里插入图片描述
没什么好说的

最优二叉树

在这里插入图片描述

练习（作业）

13题

在这里插入图片描述

这是课本上的答案

在这里插入图片描述

这是我写得答案
其实，这道题还算比较简单的。但之所以收录这道题，主要是因为这道题，我能独立做出来🚂🚂🚂

16题

在这里插入图片描述

这道题难度不大，不需要细看了
注意环路空间和断集空间都要包含空集
注意环路（断集）空间写成 C₁(S₁)，这样有下标的形式
可以审题，然后练练基本割集是怎么画的【我建议是对图上的每一个区域（点、几个点+几条边）都尝试着能否做出割集】

21题

在这里插入图片描述

波兰符号法、逆波兰符号法：

之前忘记放 波兰符号法，逆波兰符号法 了

在这里插入图片描述

先根据题目中的原式，建立二叉树（中序）
根据前序、后序写出相应的表达式

本文含有隐藏内容，请开通VIP 后查看