《离散数学-4.3关系的性质.ppt》由会员分享，可在线阅读，更多相关《离散数学-4.3关系的性质.ppt（22页珍藏版）》请在三一办公上搜索。
1、1,4.3 关系的性质,关系性质的定义和判别自反性与反自反性对称性与反对称性传递性4.3.2 关系的闭包闭包定义闭包计算 Warshall算法,2,自反性与反自反性,定义4.14 设R为A上的关系,(1)若x(xAR),则称R在A上是自反的.(2)若x(xAR),则称R在A上是反自反的.自反：A上的全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系.,R2自反,R3 反自反,R1既不自反也不反自反.,例1 A=a,b,c,R1,R2,R3 是 A上的关系,其中 R1=,R2=,R3=,3,对称性与反对称性,例2 设Aa,b,c,R1,R2,
2、R3和R4都是A上的关系,其中 R1,，R2,R3,，R4,定义4.15 设R为A上的关系,(1)若xy(x,yARR),则称R为A上 对称的关系.(2)若xy(x,yARRx=y),则称R 为A上的反对称关系.实例 对称：A上的全域关系EA,恒等关系IA和空关系 反对称：恒等关系IA，空关系是A上的反对称关系,R1 对称、反对称.R2 对称，不反对称.R3 反对称，不对称.R4 不对称、也不反对称,4,传递性,例3 设Aa,b,c,R1,R2,R3是A上的关系,其中 R1,R2,R3,定义4.16 设R为A上的关系,若 xyz(x,y,zARRR),则称R是A上的传递关系.实例：A上的全域关
3、系 EA,恒等关系 IA 和空关系,小于等于关系,小于关系,整除关系,包含关系,真包含关系,R1 和 R3 是A上的传递关系,R2不是A上的传递关系.,5,关系性质的充要条件,设 R 为 A 上的关系,则(1)R 在 A 上自反当且仅当 IA R(2)R 在 A 上反自反当且仅当 RIA=(3)R 在 A 上对称当且仅当 R=R1(4)R 在 A 上反对称当且仅当 RR1IA(5)R 在 A 上传递当且仅当 RRR,6,自反性证明,证明模式 证明 R 在 A 上自反 任取 x,xA.R 前提 推理过程 结论,例4 证明若 IA R，则 R 在 A 上自反.证 任取x,xA IA R 因此 R
4、在 A 上是自反的.,7,对称性证明,证明模式 证明 R 在 A 上对称 任取 R.R 前提 推理过程 结论,例5 证明若 R=R1,则 R 在A上对称.证 任取 R R 1 R 因此 R 在 A 上是对称的.,8,反对称性证明,证明模式 证明 R 在 A 上反对称 任取 RR.x=y 前提 推理过程 结论,例6 证明若 RR1IA,则 R 在 A 上反对称.证 任取 R R R R 1 RR 1 IA x=y 因此 R 在 A 上是反对称的.,9,传递性证明,证明模式 证明 R 在 A上传递 任取，RR.R 前提 推理过程 结论,例7 证明若 RRR,则 R 在 A 上传递.证 任取，R R
5、 RR R 因此 R 在 A 上是传递的.,10,关系性质判别,11,实例,例8 判断下图中关系的性质,并说明理由,(3)自反，不是反自反；反对称，不是对称；不传递.,(1)不自反也不反自反；对称,不反对称；不传递.,(2)反自反,不是自反；反对称,不是对称；传递.,12,运算与性质的关系,13,闭包定义,定义4.17 设R是非空集合A上的关系,R 的自反(对称或传递)闭包 是A上的关系R,使得 R满足以下条件：(1)R是自反的（对称的或传递的）(2)R R(3)对A上任何包含R 的自反（对称或传递）关系R 有 RR.一般将 R 的自反闭包记作 r(R),对称闭包记作 s(R),传递闭包记作
6、t(R).,14,闭包的构造方法,集合表示定理4.7 设R为A上的关系,则有(1)r(R)=RR0(2)s(R)=RR1(3)t(R)=RR2R3说明：对于有穷集合A(|A|=n)上的关系,(3)中的并最多不超过Rn.若R 是自反的，则 r(R)=R;若 R 是对称的，则 s(R)=R;若R 是传递的，则 t(R)=R.,15,定理4.7的证明,只证(1)和(3)证 r(R)=RR0 只需证明RR0 满足闭包定义.RR0包含了R 由IARR0可知 RR0 在 A上是自反的.下面证明RR0是包含R 的最小的自反关系.假设R是包含R 的自反关系，那么IAR,RR，因此有 RR0=IAR R,16,
7、任取和 RR2R3.RR2R3.RR2R3.于是，由RR2R3.的传递性得 t(R)RR2R3 对n 进行归纳证明 Rn t(R).n=1时显然为真.假设n=k时为真，那么对于任意Rk+1 RkR t(Rk R)t(t(R)t(R)t(R)（t(R)传递）于是，RR2R3 t(R),定理4.7的证明（续）,17,矩阵表示设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms 和 Mt,则 Mr=M+E Ms=M+M Mt=M+M2+M3+其中E 是和 M 同阶的单位矩阵,M是 M 的转置矩阵.注意：在上述等式中矩阵的元素相加时使用逻辑加.,闭包的构造方法（续）,18,图表示设关系
8、R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt 的顶点集与G 的顶点集相等.除了G 的边以外,以下述方法添加新的边：考察G 的每个顶点,如果没有环就加上一个环.最终得到的是Gr.考察G 的每一条边,如果有一条 xi 到 xj 的单向边,ij,则在G中加一条 xj 到 xi 的反方向边.最终得到Gs.考察G 的每个顶点 xi,找从 xi 出发的每一条路径，如果从 xi 到路径中的任何结点 xj 没有边，就加上这条边.当检查完所有的顶点后就得到图Gt.,闭包的构造方法（续）,19,实例,例1 设A=a,b,c,d,R=,R和 r(R),s(R),t(R)的
9、关系图如下图所示.,R,r(R),s(R),t(R),20,传递闭包的计算Warshall算法,算法思路：考虑 n+1个矩阵的序列M0,M1,Mn,将矩阵 Mk 的 i 行 j 列的元素记作Mki,j.对于k=0,1,n,Mki,j=1当且仅当在R 的关系图中存在一条从 xi 到 xj 的路径，并且这条路径除端点外中间只经过x1,x2,xk中的顶点.不难证明M0就是R 的关系矩阵，而 Mn 就对应了R 的传递闭包.Warshall算法：从M0开始，顺序计算 M1,M2,直到 Mn 为止.,21,Warshall算法的依据,从 Mk i,j 计算 Mk+1i,j:i,jV.顶点集 V1=1,2,k,V2=k+2,n,V=V1k+1V2，Mk+1i,j=1 存在从i 到 j 中间只经过V1k+1中点的路径这些路径分为两类：第1类：只经过 V1中点第2类：经过 k+1点存在第1类路径：Mki,j=1存在第2类路径：Mki,k+1=1Mkk+1,j=1,22,Warshall算法及其效率,算法4.1 Warshall算法 输入：M（R 的关系矩阵）输出：Mt（t(R)的关系矩阵）1.MtM2.for k1 to n do3.for i1 to n do4.for j1 to n do5.Mti,j Mti,j+Mti,kMtk,j,时间复杂度 T(n)=O(n3),
