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

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

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181129G0Y8EI00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券