第五章关系内容概述及课件

最近才发现一直发送高数文章，都忘记了离散宝宝了！赶紧补上！

第五章叫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