离散数学—4.3关系的性质.pptVIP

4.3 关系的性质;自反性与反自反性;对称性与反对称性;传递性 ;关系性质的充要条件;自反性证明;对称性证明;反对称性证明;传递性证明;关系性质判别;实例;运算与性质的关系;闭包定义;闭包的构造方法;定理4.7的证明;任取x,y和y,z x,y?R∪R2∪R3∪…. ? y,z?R∪R2∪R3∪…. ? x,z?R∪R2∪R3∪…. 于是，由R∪R2∪R3∪….的传递性得 t(R) ?R∪R2∪R3∪… 对n 进行归纳证明 Rn ?t(R). n=1时显然为真. 假设n=k时为真，那么对于任意x,y x,y?Rk+1? x,y?Rk°R ??t (x,t?Rk ?t,y?R) ??t (x,t?t(R)?t,y?t(R)) ?x,y?t(R) （t(R)传递） 于是， R∪R2∪R3∪… ? t(R) ;矩阵表示 设关系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 的转置矩阵. 注意：在上述等式中矩阵的元素相加时使用逻辑加.  ;图表示 设关系R, r(R), s(R), t(R)的关系图分别记为G, Gr, Gs, Gt , 则Gr, Gs, Gt 的顶点集与G 的顶点集相等. 除了G 的边以外, 以下述方法添加新的边： 考察G 的每个顶点, 如果没有环就加上一个环. 最终得到的是Gr. 考察G 的每一条边, 如果有一条 xi 到 xj 的单向边, i≠j, 则在G中加一条 xj 到 xi 的反方向边. 最终得到Gs. 考察G 的每个顶点 xi, 找从 xi 出发的每一条路径，如果从 xi 到路径中的任何结点 xj 没有边，就加上这条边. 当检查完所有的顶点后就得到图Gt . ;实例;传递闭包的计算——Warshall算法;Warshall算法的依据;Warshall算法及其效率