关系的闭包教学课件

《关系的闭包教学课件》由会员分享，可在线阅读，更多相关《关系的闭包教学课件（22页珍藏版）》请在装配图网上搜索。

1、关系的闭包教学课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望一、闭包定义一、闭包定义 关系关系R不具备自反性，但是如果在不具备自反性，但是如果在R中增加有序对中增加有序对,得到的新关系得到的新关系R1：R1=,R1具有自反性。具有自反性。引例：集合引例：集合A=1,2,R=,R也不具备对称性，增加有序对也不具备对称性，增加有序对后得到后得到R2=,具有对称性。具有对称性。闭包运算即：闭包运算即：添加最少的有序对添加最少的有序对，使得原关系具，使得原关系具有某

2、种性质的运算。有某种性质的运算。5/12/20232一、闭包定义一、闭包定义 定义：定义：设设R是是A上的二元关系，上的二元关系，R的自反（对称、的自反（对称、传递）闭包是关系传递）闭包是关系R1，则，则 R1是自反的（对称的、传递的）是自反的（对称的、传递的）R R1 对对A上的任何自反的（对称的、传递的）关系上的任何自反的（对称的、传递的）关系R2，若，若R R2，则，则R1 R2。R的自反、对称和传递闭包分别记为的自反、对称和传递闭包分别记为r(R)、s(R)和和t(R)。5/12/20233一、闭包的构造方法一、闭包的构造方法例例1 1：A=a,b,c,d,e，R=,求求r(R)和和s

3、(R)。r(R)=,s(R)=,定理：定理：设设R为为A上的关系上的关系,则有则有 (1)r(R)=RR0 或或 r(R)=RIA (2)s(R)=RR 1 Mr=M+E Ms=M+M M 的转置矩阵的转置矩阵5/12/20234二、闭包的构造方法二、闭包的构造方法例例2：设：设A=a,b,c,d,R=,通过通过R的关系图构造的关系图构造 r(R),s(R),t(R)的的关系图关系图。r(R)t(R)s(R)R5/12/20235二、闭包的构造方法二、闭包的构造方法n关系关系R,r(R),s(R),t(R)的关系图的顶点集相等。的关系图的顶点集相等。n为了得到为了得到r(R)的关系图，在的关系

4、图，在R的关系图中，考察每的关系图中，考察每个顶点个顶点,如果没有环就如果没有环就加上一个环加上一个环；n为了得到为了得到s(R)的关系图，在的关系图，在R的关系图中，考察每的关系图中，考察每条边条边,如果有一条如果有一条 xi 到到 xj 的单向边的单向边,ij,则在则在G中中加一条加一条 xj 到到 xi 的反方向边的反方向边；5/12/20236二、闭包的构造方法二、闭包的构造方法n为了得到为了得到t(R)的关系图，在的关系图，在R的关系图中，考察的关系图中，考察G的每个顶点的每个顶点 xi,首先找出从首先找出从 xi 出发的每一条路径，出发的每一条路径，然后考察从然后考察从 xi 到路

5、径中任何结点到路径中任何结点 xj 是否有边，如是否有边，如果没有，就加上这条边。直到检查完所有的顶点。果没有，就加上这条边。直到检查完所有的顶点。5/12/20237二、闭包的构造方法二、闭包的构造方法 例例3：A=a,b,c,R=,。求求R的传递闭包。的传递闭包。解解:R,R，而而 R;R,R，而而 R;R,R，而而 R。所以所以 R1=,5/12/20238二、闭包的构造方法二、闭包的构造方法R R=R2=,R=,=RR R=RR2 =,把把R1称作对称作对R的的传递扩张。传递扩张。5/12/20239二、闭包的构造方法二、闭包的构造方法又因为又因为：R1,R1，而而 R1 R1,R1，

6、而而 R1 R1,R1，而而 R1R1=,R2=,5/12/202310二、闭包的构造方法二、闭包的构造方法R1 R1=,=,R2具有传递性，所以具有传递性，所以R2是是R的传递闭包。的传递闭包。R2=R1(R1 R1)=,=RR2 R3 R45/12/202311二、闭包的构造方法二、闭包的构造方法 定理：定理：设设R为为A上的关系上的关系,则有则有 t(R)=RR2R3设关系设关系R,t(R)的关系矩阵分别为的关系矩阵分别为M,Mt,则则 Mt=M+M2+M3+推论：推论：若若A为有限集合，为有限集合，R为为A上的关系上的关系,那那么存在正整数么存在正整数t使得使得 t(R)=RR2Rt5

7、/12/202312二、闭包的构造方法二、闭包的构造方法例例4：设：设A=1,2,3,R为为A上的二元关系上的二元关系 R=,，求，求t(R)解：解：5/12/202313二、闭包的构造方法二、闭包的构造方法5/12/202314三、三、Warshall算法算法例例5：A=a1,a2,a3,a4,a5,R=,，求，求R的传递闭包。的传递闭包。解：先写出解：先写出R的关系矩阵的关系矩阵考察第考察第1列，列，m51=1，于，于是应将第是应将第1行元素加到第行元素加到第5行上去。行上去。5/12/202315三、三、Warshall算法算法由第一步得到：由第一步得到：考察第考察第2列元素，现有列元素

8、，现有 m12=1和和m52=1，于是应，于是应将第将第2行元素分别加到第行元素分别加到第1行和第行和第5行上去。行上去。5/12/202316三、三、Warshall算法算法由第二步得到：由第二步得到：考察第考察第3列元素，现有列元素，现有m13=1，m23=1，m33=1，m53=1。于是应将第。于是应将第3行元素分别加到第行元素分别加到第1，2，3，5行上去。行上去。5/12/202317三、三、Warshall算法算法由第三步得到：由第三步得到：考察第考察第4列元素，现有列元素，现有m14=1，m24=1，m34=1，m54=1，于是应将第，于是应将第4行元素加到第行元素加到第1行、第

9、行、第2行、行、第第3行、第行、第5行上去行上去5/12/202318三、三、Warshall算法算法在第在第5列中没有元素为列中没有元素为1，所以上述矩阵即为，所以上述矩阵即为R的的传递闭包传递闭包t(R)的关系矩阵。的关系矩阵。5/12/202319四、闭包的性质四、闭包的性质定理：定理：设设R是非空集合是非空集合A上的关系，则上的关系，则（1）R是自反的当且仅当是自反的当且仅当r(R)=R（2）R是对称的当且仅当是对称的当且仅当s(R)=R（3）R是传递的当且仅当是传递的当且仅当t(R)=R5/12/202320四、闭包的性质四、闭包的性质 定理：定理：设设R1和和R2是非空集合是非空集合A上的关系，上的关系，且且R1 R2，则：，则：5/12/202321四、闭包的性质四、闭包的性质 定理：定理：设设R是非空集合是非空集合A上的关系，上的关系，（1）若）若R是自反的，则是自反的，则s(R)与与t(R)也是自反的；也是自反的；（2）若）若R是对称的，则是对称的，则r(R)与与t(R)也是对称的；也是对称的；（3）若）若R是传递的，则是传递的，则r(R)也是传递的；也是传递的；5/12/202322