关系的闭包教学ppt课件

1、7.5关系的闭包关系的闭包n闭包的概念闭包的概念n闭包的构造方法闭包的构造方法nWarshall算法算法n闭包的性质闭包的性质一、闭包定义一、闭包定义 关系关系R不具备自反性，但是假设在不具备自反性，但是假设在R中添加有序对中添加有序对,得到的新关系得到的新关系R1： R1=, R1具有自反性。具有自反性。引例：集合引例：集合A=1,2,R=, R也不具备对称性，添加有序对也不具备对称性，添加有序对后得到后得到R2 =,具有对称性。具有对称性。闭包运算即：添加最少的有序对，使得原关系具闭包运算即：添加最少的有序对，使得原关系具有某种性质的运算。有某种性质的运算。一、闭包定义一、闭包定义 定义：

2、设定义：设R是是A上的二元关系，上的二元关系，R的自反对称、的自反对称、传送闭包是关系传送闭包是关系R1，那么，那么 R1是自反的对称的、传送的是自反的对称的、传送的 RR1 对对A上的任何自反的对称的、传送的关系上的任何自反的对称的、传送的关系R2，假设，假设RR2，那么，那么R1R2。R的自反、对称和传送闭包分别记为的自反、对称和传送闭包分别记为r(R)、s(R)和和t(R)。一、闭包的构造方法一、闭包的构造方法例例1 1：A = a,b,c,d,eA = a,b,c,d,e，R = ,R = ,求求r(R) r(R) 和和s(R)s(R)。 r(R) = , , , ,s(R ) = ,

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

4、中，调查每的关系图中，调查每个顶点个顶点, 假设没有环就加上一个环；假设没有环就加上一个环；n为了得到为了得到s(R)的关系图，在的关系图，在R的关系图中，调查每的关系图中，调查每条边条边, 假设有一条假设有一条 xi 到到 xj 的单向边的单向边, ij, 那么在那么在G中加一条中加一条 xj 到到 xi 的反方向边；的反方向边；二、闭包的构造方法二、闭包的构造方法n为了得到为了得到t(R)的关系图，在的关系图，在R的关系图中，调查的关系图中，调查G的每个顶点的每个顶点 xi, 首先找出从首先找出从 xi 出发的每一条途径，出发的每一条途径，然后调查从然后调查从 xi 到途径中任何结点到途径

5、中任何结点 xj 能否有边，能否有边，假设没有，就加上这条边。直到检查完一切的顶假设没有，就加上这条边。直到检查完一切的顶点。点。二、闭包的构造方法二、闭包的构造方法 例例3： A = a,b,c,R = , 。 求求R的传送闭包。的传送闭包。 解解 : R, R，而，而 R; R, R，而，而 R; R, R，而，而 R。所以所以 R1 =,二、闭包的构造方法二、闭包的构造方法R R=R2= ,R = ,= RR R = RR2 =,把把R1称作对称作对R的传送扩张。的传送扩张。二、闭包的构造方法二、闭包的构造方法又由于：又由于： R1, R1，而，而 R1 R1, R1，而，而 R1 R1

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

7、t(R) = RR2Rt二、闭包的构造方法二、闭包的构造方法例例4：设：设A=1,2,3,R为为A上的二元关系上的二元关系 R=,，求，求t(R) 001100010R RM M解：解： 0100011000011000100011000102R RM M二、闭包的构造方法二、闭包的构造方法 1000100010011000100100011003R RM MR RR RR RM MM MM M 74285R RR RR RM MM MM M 396R RR RR RM MM MM M 11111111132)(R RR RR RR Rt tM MM MM MM M三、三、WarshallWa

8、rshall算法算法例例5：A = a1,a2,a3,a4,a5, R = , ,，求，求R的传送闭包。的传送闭包。解：先写出解：先写出R的关系矩阵的关系矩阵 0100100000011000010000010M调查第调查第1列，列，m51=1，于，于是应将第是应将第1行元素加到第行元素加到第5行上去。行上去。 三、三、WarshallWarshall算法算法由第一步得到：由第一步得到： 0101100000011000010000010M调查第调查第2列元素，现有列元素，现有 m12 = 1和和m52 = 1，于是应，于是应将第将第2行元素分别加到第行元素分别加到第1行和第行和第5行上去。行

9、上去。 三、三、WarshallWarshall算法算法 0111100000011000010000110M由第二步得到：由第二步得到：调查第调查第3列元素，现有列元素，现有m13 = 1，m23 = 1，m33 = 1，m53 = 1。于是应将第。于是应将第3行元素分别加到第行元素分别加到第1，2，3，5行上去。行上去。 三、三、WarshallWarshall算法算法由第三步得到：由第三步得到： 0111100000011000110001110M调查第调查第4列元素，现有列元素，现有m14 = 1，m24 = 1，m34 = 1，m54 = 1，于是应将第，于是应将第4行元素加到第行元

10、素加到第1行、第行、第2行、行、第第3行、第行、第5行上去行上去三、三、WarshallWarshall算法算法 0111100000011000110001110M在第在第5列中没有元素为列中没有元素为1，所以上述矩阵即为，所以上述矩阵即为R的的传送闭包传送闭包t(R)的关系矩阵。的关系矩阵。四、闭包的性质四、闭包的性质定理：设定理：设R是非空集合是非空集合A上的关系，那么上的关系，那么1R是自反的当且仅当是自反的当且仅当r(R)=R2R是对称的当且仅当是对称的当且仅当s(R)=R3R是传送的当且仅当是传送的当且仅当t(R)=R四、闭包的性质四、闭包的性质 定理：设定理：设R1和和R2是非空集合是非空集合A上的关系，上的关系，且且R1 R2 ，那么：，那么：)()(3)()(2)()(1212121R Rt tR Rt tR Rs sR Rs sR Rr rR Rr r ）（）（）（四、闭