《关系的闭包教学课件》由会员分享，可在线阅读，更多相关《关系的闭包教学课件（22页珍藏版）》请在金锄头文库上搜索。
1、7.5关系的闭包关系的闭包n闭包的概念闭包的概念n闭包的构造方法闭包的构造方法nWarshall算法算法n闭包的性质闭包的性质8/26/20241一、闭包定义一、闭包定义 关系关系R不具备自反性，但是如果在不具备自反性，但是如果在R中增加有序对中增加有序对,得到的新关系得到的新关系R1： R1=, R1具有自反性。具有自反性。引例：集合引例：集合A=1,2,R=, R也不具备对称性，增加有序对也不具备对称性，增加有序对后得到后得到R2 =,具有对称性。具有对称性。闭包运算即：闭包运算即：添加最少的有序对添加最少的有序对，使得原关系具，使得原关系具有某种性质的运算。有某种性质的运算。8/26/2
2、0242一、闭包定义一、闭包定义 定义：定义：设设R是是A上的二元关系，上的二元关系，R的自反（对称、的自反（对称、传递）闭包是关系传递）闭包是关系R1，则则 R1是自反的（对称的、传递的）是自反的（对称的、传递的） R R1 对对A上的任何自反的（对称的、传递的）关系上的任何自反的（对称的、传递的）关系R2，若，若R R2，则，则R1 R2。R的自反、对称和传递闭包分别记为的自反、对称和传递闭包分别记为r(R)、s(R)和和t(R)。8/26/20243一、闭包的构造方法一、闭包的构造方法例例1 1：A = a,b,c,d,e，R = ,求求r(R) 和和s(R)。 r(R) = , , ,
3、 ,s(R ) = , 定理：定理：设设R为为A上的关系上的关系, 则有则有 (1) r(R) = RR0 或或 r(R) = RIA (2) s(R) = RR 1 Mr = M + E Ms = M + M M 的转置矩阵的转置矩阵8/26/20244二、闭包的构造方法二、闭包的构造方法例例2：设：设A=a,b,c,d, R=, 通过通过R的关系图构造的关系图构造 r(R), s(R), t(R)的的关系图关系图。 r(R)t(R)s(R)R8/26/20245二、闭包的构造方法二、闭包的构造方法n关系关系R, r(R), s(R), t(R)的关系图的顶点集相等。的关系图的顶点集相等。n
4、为了得到为了得到r(R)的的关系图，在关系图，在R的关系图中，考察每的关系图中，考察每个顶点个顶点, 如果没有环就如果没有环就加上一个环加上一个环；n为了得到为了得到s(R)的关系图，在的关系图，在R的关系图中，考察每的关系图中，考察每条边条边, 如果有一条如果有一条 xi 到到 xj 的单向边的单向边, ij, 则在则在G中中加一条加一条 xj 到到 xi 的反方向边的反方向边；8/26/20246二、闭包的构造方法二、闭包的构造方法n为了得到为了得到t(R)的关系图，在的关系图，在R的关系图中，考察的关系图中，考察G的每个顶点的每个顶点 xi, 首先找出从首先找出从 xi 出发的每一条路径
5、，出发的每一条路径，然后考察从然后考察从 xi 到路径中任何结点到路径中任何结点 xj 是否有边，如是否有边，如果没有，就加上这条边。直到检查完所有的顶点。果没有，就加上这条边。直到检查完所有的顶点。8/26/20247二、闭包的构造方法二、闭包的构造方法 例例3： A = a,b,c,R = , 。 求求R的传递闭包。的传递闭包。 解解 : R, R，而而 R; R, R，而而 R; R, R，而而 R。所以所以 R1 =,8/26/20248二、闭包的构造方法二、闭包的构造方法R R=R2= ,R = ,= RR R = RR2 =,把把R1称作对称作对R的的传递扩张。传递扩张。8/26/
6、20249二、闭包的构造方法二、闭包的构造方法又因为又因为： R1, R1，而而 R1 R1, R1，而而 R1 R1, R1，而而 R1R1 =, R2 =, ,8/26/202410二、闭包的构造方法二、闭包的构造方法R1 R1 =, , =, R2具有传递性，所以具有传递性，所以R2是是R的传递闭包。的传递闭包。 R2 = R1(R1 R1) =, ,= RR2 R3 R48/26/202411二、闭包的构造方法二、闭包的构造方法 定理：定理：设设R为为A上的关系上的关系, 则有则有 t(R) = RR2R3设关系设关系R, t(R)的关系矩阵分别为的关系矩阵分别为M, Mt , 则则
7、Mt = M + M2 + M3 + 推论：推论：若若A为有限集合，为有限集合，R为为A上的关系上的关系, 那那么存在正整数么存在正整数t使得使得 t(R) = RR2Rt8/26/202412二、闭包的构造方法二、闭包的构造方法例例4：设：设A=1,2,3,R为为A上的二元关系上的二元关系 R=,，求，求t(R)解：解：8/26/202413二、闭包的构造方法二、闭包的构造方法8/26/202414三、三、Warshall算法算法例例5：A = a1,a2,a3,a4,a5, R = , ,，求，求R的传递闭包。的传递闭包。解：先写出解：先写出R的关系矩阵的关系矩阵考察第考察第1列，列，m5
8、1=1，于于是应将第是应将第1行元素加到第行元素加到第5行上去。行上去。8/26/202415三、三、Warshall算法算法由第一步得到：由第一步得到：考察第考察第2列元素，现有列元素，现有 m12 = 1和和m52 = 1，于是应于是应将第将第2行元素分别加到第行元素分别加到第1行和第行和第5行上去。行上去。8/26/202416三、三、Warshall算法算法由第二步得到：由第二步得到：考察第考察第3列元素，现有列元素，现有m13 = 1，m23 = 1，m33 = 1，m53 = 1。于是应将第于是应将第3行元素分别加到第行元素分别加到第1，2，3，5行上去。行上去。8/26/2024
9、17三、三、Warshall算法算法由第三步得到：由第三步得到：考察第考察第4列元素，现有列元素，现有m14 = 1，m24 = 1，m34 = 1，m54 = 1，于是应将第于是应将第4行元素加到第行元素加到第1行、第行、第2行、行、第第3行、第行、第5行上去行上去8/26/202418三、三、Warshall算法算法在第在第5列中没有元素为列中没有元素为1，所以上述矩阵即为，所以上述矩阵即为R的的传递闭包传递闭包t(R)的关系矩阵。的关系矩阵。8/26/202419四、闭包的性质四、闭包的性质定理：定理：设设R是非空集合是非空集合A上的关系，则上的关系，则（1）R是自反的当且仅当是自反的当
10、且仅当r(R)=R（2）R是对称的当且仅当是对称的当且仅当s(R)=R（3）R是传递的当且仅当是传递的当且仅当t(R)=R8/26/202420四、闭包的性质四、闭包的性质 定理：定理：设设R1和和R2是非空集合是非空集合A上的关系，上的关系，且且R1 R2 ，则：，则：8/26/202421四、闭包的性质四、闭包的性质 定理：定理：设设R是非空集合是非空集合A上的关系，上的关系，（1）若）若R是自反的，则是自反的，则s(R)与与t(R)也是自反的；也是自反的；（2）若）若R是对称的，则是对称的，则r(R)与与t(R)也是对称的；也是对称的；（3）若）若R是传递的，则是传递的，则r(R) 也是传递的；也是传递的；8/26/202422
