《离散数学-4.3关系的性质.ppt》由会员分享，可在线阅读，更多相关《离散数学-4.3关系的性质.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4.3 关系的性质关系的性质关系性质的定义和判别关系性质的定义和判别自反性与反自反性自反性与反自反性对称性与反对称性对称性与反对称性传递性传递性4.3.2关系的闭包关系的闭包闭包定义闭包定义闭包计算闭包计算 Warshall算法算法 1自反性与反自反性自反性与反自反性定义定义4.14设设R为为A上的关系上的关系,(1)若若 x(xA R),则称则称R在在A上是上是自反自反的的.(2)若若 x(xA R),则称则称R在在A上是上是反自反反自反的的.自反：自反：A上的全域关系上的全域关系EA,恒等关系恒等关系IA,小于等于关系小于等于关系LA,整除关系整除关系DA反自反：实数集上的小于关系、幂集上
2、的真包含关系反自反：实数集上的小于关系、幂集上的真包含关系.R2自反自反,R3反自反反自反,R1既不自反也不反自反既不自反也不反自反.例例1A=a,b,c,R1,R2,R3是是A上的关系上的关系,其中其中R1=,R2=,R3=2对称性与反对称性对称性与反对称性例例2设设Aa,b,c,R1,R2,R3和和R4都是都是A上的关系上的关系,其中其中R1,，R2,R3,，R4,定义定义4.15设设R为为A上的关系上的关系,(1)若若 x y(x,yARR),则称则称R为为A上上对称对称的关系的关系.(2)若若 x y(x,yARRx=y),则称则称R 为为A上的上的反对称反对称关系关系.实例实例对称：
3、对称：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系反对称：恒等关系反对称：恒等关系IA，空关系是空关系是A上的反对称关系上的反对称关系R1对称、反对称对称、反对称.R2对称，不反对称对称，不反对称.R3反对称，不对称反对称，不对称.R4不对称、也不反对称不对称、也不反对称3传递性传递性 例例3设设Aa,b,c,R1,R2,R3是是A上的关系上的关系,其中其中R1,R2,R3定义定义4.16设设R为为A上的关系上的关系,若若 x y z(x,y,zARRR),则称则称R是是A上的上的传递传递关系关系.实例：实例：A上的全域关系上的全域关系EA,恒等关系恒等关系IA 和空关
4、系和空关系,小小于等于关系于等于关系,小于关系小于关系,整除关系整除关系,包含关系包含关系,真包含关系真包含关系R1和和R3是是A上的传递关系上的传递关系,R2不是不是A上的传递关系上的传递关系.4关系性质的充要条件关系性质的充要条件设设R 为为A 上的关系上的关系,则则(1)R 在在A 上自反当且仅当上自反当且仅当IA R(2)R 在在A 上反自反当且仅当上反自反当且仅当RIA=(3)R 在在A 上对称当且仅当上对称当且仅当R=R 1(4)R 在在A 上反对称当且仅当上反对称当且仅当RR 1 IA(5)R 在在A 上传递当且仅当上传递当且仅当R R R5自反性证明自反性证明证明模式证明模式证
5、明证明R 在在A 上自反上自反任取任取x,x A.R前提前提推理过程推理过程结论结论例例4证明若证明若IA R，则则 R 在在A 上自反上自反.证证任取任取x,x A IA R 因此因此R 在在A 上是自反的上是自反的.6对称性证明对称性证明证明模式证明模式证明证明R 在在A 上对称上对称任取任取 R.R前提前提推理过程推理过程结论结论例例5证明若证明若R=R 1,则则R 在在A上对称上对称.证证任取任取 R R 1 R 因此因此R 在在A 上是对称的上是对称的.7反对称性证明反对称性证明证明模式证明模式证明证明R 在在A 上反对称上反对称任取任取 R R.x=y 前提前提推理过程推理过程结论
6、结论例例6证明若证明若RR 1 IA,则则R 在在A 上反对称上反对称.证证任取任取 R R R R 1 RR 1 IA x=y因此因此R 在在A 上是反对称的上是反对称的.8传递性证明传递性证明证明模式证明模式证明证明R 在在A上传递上传递任取任取，R R.R 前提前提推理过程推理过程结论结论例例7证明若证明若R R R,则则R 在在A 上传递上传递.证证任取任取，R R R R R 因此因此R 在在A 上是传递的上是传递的.9关系性质判别关系性质判别自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性表达式表达式IA RRIA=R=R 1RR 1 IAR R R关系关系矩阵
7、矩阵主对角主对角线元素线元素全是全是1主对角线主对角线元素全是元素全是0矩阵是对称矩阵是对称矩阵矩阵若若rij1,且且ij,则则rji0对对M2中中1所所在位置在位置,M中相应位置中相应位置都是都是1关系图关系图每个顶每个顶点都有点都有环环每个顶点每个顶点都没有环都没有环如果两个顶如果两个顶点之间有边点之间有边,一定是一对一定是一对方向相反的方向相反的边边(无单边无单边)如果两点之如果两点之间有边间有边,一定一定是一条有向是一条有向边边(无双向边无双向边)如果顶点如果顶点xi到到xj有边有边,xj到到xk有边有边,则则从从xi到到xk也也有边有边10实例实例例例8判断下图中关系的性质判断下图中
8、关系的性质,并说明理由并说明理由(3)自反，不是反自反；反对称，不是对称；不传递自反，不是反自反；反对称，不是对称；不传递.(1)(2)(3)(1)不自反也不反自反；对称不自反也不反自反；对称,不反对称；不传递不反对称；不传递.(2)反自反反自反,不是自反；反对称不是自反；反对称,不是对称；传递不是对称；传递.11运算与性质的关系运算与性质的关系自反性自反性反自反性反自反性对对称性称性反反对对称性称性传递传递性性R1 1R1R2R1R2R1 R2R1 R212闭包定义闭包定义定义定义4.17设设R是非空集合是非空集合A上的关系上的关系,R 的的自反自反(对称对称或或传传递递)闭包闭包是是A上的
9、关系上的关系R,使得使得R 满足以下条件：满足以下条件：(1)R 是自反的（对称的或传递的）是自反的（对称的或传递的）(2)R R(3)对对A上任何包含上任何包含R 的自反（对称或传递）关系的自反（对称或传递）关系R 有有 RR.一般将一般将R 的自反闭包记作的自反闭包记作r(R),对称闭包记作对称闭包记作s(R),传递传递闭包记作闭包记作t(R).13闭包的构造方法闭包的构造方法集合表示集合表示定理定理4.7设设R为为A上的关系上的关系,则有则有(1)r(R)=RR0(2)s(R)=RR 1(3)t(R)=RR2R3说明：说明：对于有穷集合对于有穷集合A(|A|=n)上的关系上的关系,(3)
10、中的并最多不超过中的并最多不超过Rn.若若R 是自反的，则是自反的，则r(R)=R;若若R 是对称的，则是对称的，则s(R)=R;若若R 是传递的，则是传递的，则t(R)=R.14定理定理4.7的证明的证明只证只证 (1)和和(3)证证 r(R)=RR0只需证明只需证明RR0满足闭包定义满足闭包定义.RR0包含了包含了R由由IA RR0可知可知RR0在在A上是自反的上是自反的.下面证明下面证明RR0是包含是包含R 的最小的自反关系的最小的自反关系.假设假设R 是包含是包含R 的自反关系，那么的自反关系，那么IA R,R R，因此有因此有 RR0=IA R R 15任取任取和和 RR2R3.RR
11、2R3.RR2R3.于是，由于是，由RR2R3.的传递性得的传递性得t(R)RR2R3对对n 进行归纳证明进行归纳证明Rn t(R).n=1时显然为真时显然为真.假设假设n=k时为真，那么对于任意时为真，那么对于任意 Rk+1 Rk R t(Rk R)t(t(R)t(R)t(R)（t(R)传递）传递）于是，于是，RR2R3 t(R)定理定理4.7的证明（续）的证明（续）16矩阵表示矩阵表示设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关系矩阵分别为M,Mr,Ms 和和Mt,则则Mr=M+E Ms=M+MMt=M+M2+M3+其中其中E 是和是和M 同阶的单位矩阵同阶的单位矩阵,
12、M是是M 的转置矩阵的转置矩阵.注意：在上述等式中矩阵的元素相加时使用逻辑加注意：在上述等式中矩阵的元素相加时使用逻辑加.闭包的构造方法（续）闭包的构造方法（续）17图表示图表示设关系设关系R,r(R),s(R),t(R)的关系图分别记为的关系图分别记为G,Gr,Gs,Gt,则则Gr,Gs,Gt 的顶点集与的顶点集与G 的顶点集相等的顶点集相等.除了除了G 的边以的边以外外,以下述方法添加新的边：以下述方法添加新的边：考察考察G 的每个顶点的每个顶点,如果没有环就加上一个环如果没有环就加上一个环.最终得到最终得到的是的是Gr.考察考察G 的每一条边的每一条边,如果有一条如果有一条xi 到到xj
13、 的单向边的单向边,ij,则则在在G中加一条中加一条xj 到到xi 的反方向边的反方向边.最终得到最终得到Gs.考察考察G 的每个顶点的每个顶点xi,找从找从xi 出发的每一条路径，如果出发的每一条路径，如果从从xi 到路径中的任何结点到路径中的任何结点xj 没有边，就加上这条边没有边，就加上这条边.当当检查完所有的顶点后就得到图检查完所有的顶点后就得到图Gt.闭包的构造方法（续）闭包的构造方法（续）18实例实例例例1设设A=a,b,c,d,R=,R和和r(R),s(R),t(R)的关系图如下图所示的关系图如下图所示.Rr(R)s(R)t(R)19传递闭包的计算传递闭包的计算Warshall算
14、法算法算法思路：算法思路：考虑考虑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 为止为止.20Warsh
15、all算法的依据算法的依据从从Mk i,j 计算计算Mk+1i,j:i,j V.顶点集顶点集V1=1,2,k,V2=k+2,n,V=V1 k+1 V2，Mk+1i,j=1存在从存在从i 到到j 中间只经过中间只经过V1 k+1中点的路径中点的路径这些路径分为两类：这些路径分为两类：第第1类：只经过类：只经过V1中点中点第第2类：经过类：经过k+1点点存在第存在第1类路径：类路径：Mki,j=1存在第存在第2类路径：类路径：Mki,k+1=1 Mkk+1,j=121Warshall算法及其效率算法及其效率算法算法4.1Warshall算法算法输入：输入：M（R 的关系矩阵）的关系矩阵）输出：输出：Mt（t(R)的关系矩阵）的关系矩阵）1.MtM2.fork1tondo3.fori1tondo4.forj1tondo5.Mti,jMti,j+Mti,k Mtk,j 时间复杂度时间复杂度 T(n)=O(n3)22