离散数学关系的闭包

《离散数学关系的闭包》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.4关系的闭包闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质1一、闭包定义定义设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R,使得R满足以下条件：（1）R是自反的（对称的或传递的）（2）RR（3）对A上任何包含R的自反（对称或传递）关系R有RR.一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).2由闭包的定义可知，R的自反（对称，传递）闭包是含有R并且具有自反（对称，传递）性质的“最小”的关系。如果R已是自反的二元关系，显

2、然有：R=r(R)。同样，当R是对称的二元关系时R=s(R)；当R是传递的二元关系时，R=t(R)，且反之亦然。3二、关系的闭包运算（1）已知一个集合中的二元关系R，则r(R),s(R),t(R)是唯一的，它是包含R的最小的自反（对称，传递）关系；（2）若R是自反（对称，传递）的，则r(R),s(R),t(R)就是R本身。（3）若R不是自反（对称，传递）的，则可以补上最少序偶，使之变为自反、对称、传递关系，从而得到r(R),s(R),t(R)；4例：设Ａ={a,b,c},R={,,<

3、c,a>}，求r(R),s(R),t(R)。解：r(R)=s(R)=t(R)={,,,,,,,,}例：设Ａ={a,b},R={}，则r(R)={},s(R)={},t(R)={}=R5设R是A上的二元关系，x∈A，将所有(x,x)R的有序对加到R上去，使其扩充成自反的二元关系，扩充后的自反关系就是R的自反闭包r(R

4、)。例如，A={a,b,c,d},R={(a,a),(b,d),(c,c)}。R的自反闭包r(R)={(a,a),(b,d),(c,c),(b,b),(d,d)}。于是可得：定理:R是A上的二元关系，则R的自反闭包r(R)=R∪IA。1.构造R的自反闭包的方法。三、闭包的构造方法62.构造R的对称闭包的方法。每当(a,b)∈R，而(b,a)R时，将有序对(b,a)加到R上去，使其扩充成对称的二元关系，扩充后的对称关系就是R的对称闭包s(R)。例如，A={a,b,c,d,e},R={(a,a),(a,b

5、),(b,a),(b,c),(d,e)}。R的对称闭包s(R)={(a,a),(a,b),(b,a),(b,c),(c,b),(d,e),(e,d)}。定理:R是A上二元关系，是其逆关系，则R的对称闭包s(R)=R∪。由逆关系的定义可知：73.构造R的传递闭包的方法。设R是A上的二元关系，每当(a,b)∈R和(b,c)∈R而(a,c)R时，将有序对(a,c)加到R上使其扩充成R1，并称R1为R的传递扩张，R1如果是传递关系，则R1是R的传递闭包；如果R1不是传递关系，继续求R1的的传递扩张R2，如果R

6、2是传递关系时，则R2是R的传递闭包；如果R2不是传递关系时，继续求R2的的传递扩张R3…，如果A是有限集，R经过有限次扩张后，定能得到R的传递闭包。扩张后的传递关系就是R的传递闭包t(R)。定理:设R为A上的关系,则有t(R)=R∪R2∪R3∪…说明：对于有穷集合A(

7、A

8、=n)上的关系,上式中的并最多不超过Rn.8思考：设A={a,b,c,d},R={,,,},求r(R),s(R),t(R).解:r(R)=R∪R0={,,,

9、b>,,,,},s(R)=R∪R1={,,,,,},t(R)=R∪R2∪R3∪R4R2={,,,}R3={,,,}R4={,,,}=R2于是t(R)=R∪R2∪R3={,,,,,,,,}.9闭包的

10、构造方法（续）设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则Mr=M+EMs=M+M’Mt=M+M2+M3+…E是和M同阶的单位矩阵,M’是M的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加.10闭包的构造方法（续）设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新边：考察G的每个顶点,如果没有环就