离散数学-4.3关系的性质.ppt

1,4.3关系的性质,4.3.1关系性质的定义和判别自反性与反自反性对称性与反对称性传递性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既不自反也不反自反.,例1A=a,b,c,R1,R2,R3是A上的关系,其中R1=,R2=,R3=,3,对称性与反对称性,例2设Aa,b,c,R1,R2,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上的全域关系EA,恒等关系IA和空关系,小于等于关系,小于关系,整除关系,包含关系,真包含关系,R1和R3是A上的传递关系,R2不是A上的传递关系.,5,关系性质的充要条件,设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当RIA=(3)R在A上对称当且仅当R=R1(4)R在A上反对称当且仅当RR1IA(5)R在A上传递当且仅当RRR,6,自反性证明,证明模式证明R在A上自反任取x,xA.R前提推理过程结论,例4证明若IAR，则R在A上自反.证任取x,xAIAR因此R在A上是自反的.,7,对称性证明,证明模式证明R在A上对称任取R.R前提推理过程结论,例5证明若R=R1,则R在A上对称.证任取RR1R因此R在A上是对称的.,8,反对称性证明,证明模式证明R在A上反对称任取RR.x=y前提推理过程结论,例6证明若RR1IA,则R在A上反对称.证任取RRRR1RR1IAx=y因此R在A上是反对称的.,9,传递性证明,证明模式证明R在A上传递任取，RR.R前提推理过程结论,例7证明若RRR,则R在A上传递.证任取，RRRRR因此R在A上是传递的.,10,关系性质判别,11,实例,例8判断下图中关系的性质,并说明理由,(3)自反，不是反自反；反对称，不是对称；不传递.,(1)不自反也不反自反；对称,不反对称；不传递.,(2)反自反,不是自反；反对称,不是对称；传递.,12,运算与性质的关系,13,闭包定义,定义4.17设R是非空集合A上的关系,R的自反(对称或传递)闭包是A上的关系R,使得R满足以下条件：(1)R是自反的（对称的或传递的）(2)RR(3)对A上任何包含R的自反（对称或传递）关系R有RR.一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作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=IARR,16,任取和RR2R3.RR2R3.RR2R3.于是，由RR2R3.的传递性得t(R)RR2R3对n进行归纳证明Rnt(R).n=1时显然为真.假设n=k时为真，那么对于任意Rk+1RkRt(RkR)t(t(R)t(R)t(R)（t(R)传递）于是，RR2R3t(R),定理4.7的证明（续）,17,矩阵表示设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则Mr=M+EMs=M+MMt=M+M2+M3+其中E是和M同阶的单位矩阵,M是M的转置矩阵.注意：在上述等式中矩阵的元素相加时使用逻辑加.,闭包的构造方法（续）,18,图表示设关系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)的关系图如下图所示.,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算法的依据,从Mki,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,Wars