离散数学关系的闭包.ppt

《离散数学关系的闭包.ppt》由会员分享，可在线阅读，更多相关《离散数学关系的闭包.ppt（15页珍藏版）》请在优知文库上搜索。

1、离散数学离散数学集合论集合论 2 / 68主要内容n集合代数n二元关系n函数集合的基本概念集合的运算有穷集合的计数集合恒等式有序对与笛卡儿积二元关系关系的运算关系的性质 关系的闭包等价关系与划分偏序关系函数的定义与性质函数的复合与反函数双射函数与集合的基数 3 / 687.5 关系的闭包一一. . 闭包的定义闭包的定义定义定义7.147.14 设设R R是非空集合是非空集合A A上的关系上的关系,R,R的自反闭包的自反闭包( (对称闭包对称闭包, ,传递闭包传递闭包) )是是 A A上的关系上的关系 R R , ,它满足它满足: :(1)(1) R R 是自反的是自反的 ( (对称的对称的,

2、,传递的传递的) )；(2) R(2) R R R ; ;(3) (3) 对对A A上任何包含上任何包含 R R 的自反关系的自反关系 ( (对称关系对称关系, ,传递关系传递关系) ) R R 都有都有R R R R . .注注: :R R的自反闭包记为的自反闭包记为 r(R),r(R),对称闭包记为对称闭包记为 s(R),s(R),传递闭包记传递闭包记 为为 t(R).t(R). Reflexive, Symmetric, Transtive: r(R), s(R), t(R). 4 / 68闭包的计算定理定理 7.107.10 设设R R是是A A上的关系上的关系, ,则则(1) r(R

3、)=RR(1) r(R)=RR0 0; ;(2) s(R)= RR(2) s(R)= RR-1-1; ;(3) t(R)= RR(3) t(R)= RR2 2RR3 3. .证明证明：(1) (1) 由由I IA A= R= R0 0 R RRR0 0 知知, , RR RR0 0 是自反的是自反的, ,且且R R R RRR0 0. .设设R R是是A A上包含上包含R R的自反关系的自反关系, ,则则 R R R R , I , IA A R R, 因而因而 x,y R RRR0 0 R RIIA A R RR R = = R R 即即 RRRR0 0 R R . .可见可见RRRR0 0

4、满足自反闭包的定义满足自反闭包的定义, ,从而从而 r(Rr(R)= RR)= RR0 0. . (2) (2) 略略. . 5 / 68闭包的计算(3)(3)先证先证R RRR2 2 t(R),t(R),为此只需证明对任意正整数为此只需证明对任意正整数n n都有都有 R Rn n t(R). t(R). 用归纳法用归纳法. .当当n=1n=1时时, , R R1 1 = R = R t(R).t(R).假设假设 R Rn n t(R), t(R), 下证下证 R Rn+1n+1 t(R)t(R)事实上事实上, ,由于由于 R Rn+1 n+1 = R= Rn n R R t(t( R Rn

5、n R)R) t(t( t(R)t(R) t(R)t(R) t(Rt(R) )从而从而 R Rn+1 n+1 t(R) . t(R) . 由归纳法完成证明由归纳法完成证明. 6 / 68闭包的计算下证下证 RRRR2 2 是传递的是传递的. . 事实上事实上, ,对任意对任意 ,( ( RR RR2 2)( )( RR RR2 2) ) t (t ( R Rt t) ) s(s( R Rs s) ) t t s( s( R Rt t R Rs s) ) t t s( s( R Rt+st+s) ) RRRR2 2从而从而 RRRR2 2 是传递的是传递的. . 因因t(R)t(R)是传递闭包是

6、传递闭包, , 故故t(Rt(R) ) RR RR2 2. .由以上两方面知由以上两方面知, , t(R) t(R) RRRR2 2 . . 7 / 68通过关系矩阵求闭包 证证: :由定理由定理7.67.6和定理和定理7.107.10立即得证立即得证. .通过关系矩阵求闭包通过关系矩阵求闭包设关系设关系R, r(R), s(R), t(R)R, r(R), s(R), t(R)的关系矩阵分别为的关系矩阵分别为M, MM, Mr r, M, Ms s, M, Mt t, , 则则: : M Mr r = M+E, = M+E, M Ms s = M+M= M+M, , M Mt t = M+M

7、= M+M2 2+M+M3 3+ +, , 其中其中E E是与是与M M同阶的单位矩阵同阶的单位矩阵.M.M是是M M的转置矩阵的转置矩阵, ,矩阵元素相矩阵元素相加时使用加时使用逻辑加逻辑加. .推论推论 设设R R是有限集合是有限集合A A上的关系，则存在正整数上的关系，则存在正整数r r使得使得 t(Rt(R)= RR)= RR2 2RRr r. .r(R) = RIAr(R) R IA mxy = 1 exy = 1 nnnnnnnnnnnnnnncccccccccbbbbbbbbbaaaaaaaaa221222211121122122221112112212222111211njib

8、acijijij ,1, 8 / 68通过关系图求闭包 设关系设关系R, r(R), s(R), t(R)R, r(R), s(R), t(R)的关系图分别记为的关系图分别记为G, GG, Gr r, G, Gs s, G, Gt t, , 则则G Gr r, G, Gs s, G, Gt t的顶点集与的顶点集与G G的顶点集相同的顶点集相同. .除了除了G G的边外的边外, ,依下述方法添依下述方法添加新边加新边: :(1)(1)对对G G的每个顶点的每个顶点, ,如果无环如果无环, ,则添加一条环则添加一条环, ,由此得到由此得到G Gr r; ;(2)(2)对对G G的每条边的每条边,

9、,如果它是单向边如果它是单向边, ,则添加一条反方向的边则添加一条反方向的边. .由此由此得到得到G Gs s; ;), 2 , 1(klxlj(3) 对对G G的每个顶点的每个顶点x xi i , ,找出从找出从x xi i 出发的所有出发的所有2 2步步, 3, 3步步, , , , n n步长步长的有向路的有向路 ( (n n为为G G的顶点数的顶点数).).设路的终点分别设路的终点分别为为 , ,如果从如果从 x xi i 到到 x xj j 无边无边, ,则添上这则添上这条边条边. .如上处理完所有顶点后得到如上处理完所有顶点后得到 G Gt tkjjjxxx,21 9 / 68Wa

10、rshall算法n设设A=xA=x1 1,x,x2 2, ,x,xn n,R,R为为A A上的二元关系上的二元关系,R,R的关系矩阵为的关系矩阵为M:M:1. 1. M Mt t = M+M = M+M2 2+ +M+Mn n2. Warshall2. Warshall算法算法考虑矩阵序列考虑矩阵序列 M M0 0,M,M1 1, ,M,Mn n= = M Mt t : k=0,1, : k=0,1,n,nM Mk ki,j=1i,j=1 当且仅当当且仅当 在在G GR R中存在一条从中存在一条从x xi i到到x xj j的路径的路径并且除端点外中间只经过并且除端点外中间只经过 x x1 1

11、,x,x2 2, ,x,xk k 中的顶点中的顶点. .M Mk+1k+1i,j=1i,j=1 当且仅当当且仅当 在在G GR R中存在一条从中存在一条从x xi i到到x xj j的路的路径并且除端点外中间只经过径并且除端点外中间只经过 x x1 1,x,x2 2, ,x,xk k, ,x xk+1k+1 中的顶中的顶点点M Mk ki,j=1 i,j=1 或者或者M Mk ki,i,k+1k+1=1 M=1 Mk k k+1k+1,j=1,j=1 10 / 68Warshall算法示例n设设 A=a,b,c,d, R=,求求 t( R ).解解0000100001010010M000001

12、00001110010M10000100001110111M20000100011111111M30000100011111111Mt(R)4Mk+1i,j=1 Mki,k+1=1 Mkk+1,j=1 11 / 68闭包的性质 定理定理7.117.11 设设R R是非空集合是非空集合A A上的关系上的关系, ,则则(1) R (1) R 是自反的当且仅当是自反的当且仅当r(R)=Rr(R)=R(2) R (2) R 是对称的当且仅当是对称的当且仅当 s(R)=Rs(R)=R(3) R (3) R 是传递的当且仅当是传递的当且仅当 t(R)=Rt(R)=R 证证:(1) :(1) 充分性显然充分

13、性显然. .下证必要性下证必要性. . 因因 R R 是包含了是包含了 R R 的自反关系的自反关系, ,故故r(R)r(R) R.R. 另一方面另一方面, ,显然显然 R R r(R). r(R). 从而从而,r(R)=R.,r(R)=R. (2), (3) (2), (3)略略. .定理定理7.127.12 设设 R R1 1 和和 R R2 2 是非空集合是非空集合A A上的关系上的关系, ,且且 R R1 1 R R2 2 , , 则则(1)r(R(1)r(R1 1) ) r(Rr(R2 2); (2)s(R); (2)s(R1 1) ) s(R s(R2 2); (3)t(R); (

14、3)t(R1 1) ) t(R t(R2 2) ) 证明略证明略 12 / 68闭包的性质定理定理7.137.13 设设 R R 是非空集合是非空集合A A上的关系上的关系（1 1）若）若R R是自反的是自反的, ,则则 s(R) s(R) 和和 t(R) t(R) 也是自反的也是自反的. .（2 2）若）若R R是对称的是对称的, ,则则 r(R) r(R) 和和 t(R) t(R) 也是自反的也是自反的. .（3 3）若）若R R是传递的是传递的, ,则则 r(R) r(R) 也是传递的也是传递的. .证明证明: :只证只证 (2) .(2) .先考虑先考虑r(R). r(R). 因因R

15、R是是 A A上的对称关系。故上的对称关系。故R=RR=R-1-1 , , 同时同时 I IA A = I= IA A-1 -1 , ,于是于是 (RI(RIA A) )-1-1=R=R-1-1IIA A-1 -1 ( (根据习题根据习题7.20). 7.20). 从而从而 r(R)r(R)-1 -1 = (RR= (RR0 0) )-1 -1 = (RI= (RIA A) )-1 -1 = R= R-1-1IIA A-1 -1 = RI= RIA A = r(R) .= r(R) .这便说明这便说明 r(R) r(R) 是对称的是对称的. . 下面证明下面证明t(R)t(R)的对称性的对称性

16、. .为此为此, ,先用数学归纳法证明先用数学归纳法证明: :若若R R是对称的是对称的, , 则对任何正整数则对任何正整数n, Rn, Rn n也是对称的也是对称的. . 事实上事实上, ,当当n=1n=1时时,R,R =R =R 显然是对称的显然是对称的. . 13 / 68闭包的性质假设假设R Rn n是对称的是对称的, ,下证下证R Rn+1n+1 的对称性的对称性. .由于由于 R Rn+1 n+1 R Rn n R R t (t ( R Rn n) R)R) t (t ( R Rn n) R)R) R R R Rn n R Rn+1n+1 故故 R Rn+1 n+1 是对称的是对称的. .归纳法定成归纳法定成. .现在来证现在来证 t(R)t(R)的对称性的对称性. .由于由于 x,y t(R) t(R) n(x,yn( R Rn n) ) n(y,xn( R Rn n) ) y,x t(R)t(R) 因此因此t(R)t(R)是对称的是对称的. . 注注: :由于对称闭包运算不保持传递性由于对称闭包运算不保持传递性, ,故在运算顺序故在运算顺序 上它应放在传递闭包之前上它应