最近才发现一直发送高数文章,都忘记了离散宝宝了!赶紧补上!
第五章叫Relation,研究二元关系及其性质、表示、运算、应用。
概念问题
二元关系:A与B的笛卡尔积的子集称为从A到B的二元关系。
集合上的关系:A到A的关系。
关系的性质
自反、反自反、对称、反对称、传递。
概念不罗列了,但要注意以下方面:
(1)所有性质的概念都是逻辑表达式,即为判断真假的问题,严格按定义判断真假即可;
(2)都是全称量词表示的逻辑表达式,故要都为真才算符合;
(3)都是用蕴涵的条件语句表示,注意前提为假则也为真,即不出现前真后假的都为真。
关系的表示
(1)集合表示法(适合做定义、表示);
(2)关系图表示法(适合得到直观感受、观察特征);
(3)关系矩阵表示法(适合做计算);特别强调,关系矩阵是布尔矩阵,即逻辑矩阵,描述A中第i个元素跟B中第j个元素有没有关系。
关系的运算
(1)交、并、差
R1ÇR2————M1ÙM2
R1ÈR2————M1ÚM2
(2)合成
合成运算非常重要,也容易出错,注意其顺序性、计算在集合、图、矩阵上分别的对应。
自己与自己的合成运算形成幂。
比如R^2在关系图上对应的是从每个点出发走两步能到的点直接连成的边。
再比如
R1°R2————M2M1
R^2————M^2
关系的应用
(1)n元关系的应用
总的说来,2元关系推广到n元关系,就变成了数据库的基本框架,一个n元有序对就是一个n个字段的记录,那么关系的运算就对应着数据库的操作。
这一块内容我们仅了解即可(跟数据库有重复)。
(2)闭包的应用
首先是三种闭包的概念,如果用一句话概括,R的自反/对称/传递闭包即为包含R的具有自反/对称/传递的关系中最小的关系。
然后其应用重点掌握传递闭包的应用,可以将由传递性可到达的点也直接通过连边来展现其连通性。
接着说三种闭包的计算:
(3)等价关系的应用
首先是等价关系的概念,及其延伸出的等价类、划分的概念。
其次,等价关系的应用简言之就是做分类。因为等价关系和划分之间是一一对应的。
a、若一个关系是集合A上的等价关系,写出每个元素的等价类,重复的去掉,则由不重复的等价类构成的集合,即为对原集合A的一个划分。
b、若一个子集族是集合A的划分,按照“落在同一个子集的就有关系即能配对”的规则写出二元有序对的集合,是一定满足自反、对称、传递的,即为等价关系。
(4)偏序关系的应用
首先是偏序的概念,以及延伸出的“小于等于”、“小于”、“可比”。
然后是全序,再然后是良序(概念自己对照吧)。
偏序关系的应用就比较多了:
a、字典顺序
说白了就是把偏序推广到串的排序上去。
b、哈赛图
说白了就是去掉环、去掉传递性能到达的边、去掉由下至上的方向后得到的简化图,此图对于后续应用至关重要。
画哈赛图时要注意:
第一、所有的边由下往上画;
第二、不要漏边,也不要保留可传递到达的边。(哈哈,说了等于没说,就是这么任性)
c、极元和最元
比如极小元指的是没有比它小的了,而最小元首先是跟其他的都可比而且比其他的都小。
要注意:
第一、最元不一定存在,极元一定存在;
第二、最元若存在则唯一,极元不一定唯一;
第三、最元一定是极元。
d、四个界
略,直接看定义即可。
e、格
某偏序的哈赛图中每两个元素都有最小上界和最大下界的即为格,在信息模型中有应用。
f、拓扑排序
某偏序的哈赛图中,某些点与点之间有前后顺序关系,某些点又不可比故没有前后顺序,那么我们按流水线对每个点进行排序,得到的将是一个与原图顺序不矛盾的拓扑排序。
构造方法的思路用一句话概括:依次在哈赛图中找出当前极小元,然后在图中删去找到的极小元及相关的边。
注意:
拓扑排序往往不是唯一的结果,但是为了答案的统一性,我们往往规定在同等情况下优先按字母顺序选择。
6、课件链接
链接:https://pan.baidu.com/s/1AiyRDnGtdIkEanfoaTCYuA
提取码:8f7e
领取专属 10元无门槛券
私享最新 技术干货