二元关系传递性与反传递性的判定-论文.pdf

《二元关系传递性与反传递性的判定-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2Ol4年青海师范大学学报(自然科学版)2O14第2期JournalofQinghaiNormalUniversity(NaturalScience)NO．2二元关系传递性与反传递性的判定董丽欣(青海师范大学计算机学院，青海西宁810008)摘要：本文给出了关系运算法、关系图法、关系矩阵法、关系复合矩阵法判定二元关系的传递性和反传递性，分析了传递性和反传递性之间的联系，并建立了判定传递性和反传递性的算法，最后利用c语言编程实现．关键词：关系；性质；判定中圈分类号：O158文献标识码：A文章编号：1001—7542(2014)02—0004—041引言关系在

2、离散数学中占有极其重要的地位．定义在集合A上的关系可以具有自反性、反自反性、对称性、反对称性、传递性和反传递性等性质．在关系的这六种性质中，传递性和反传递性是最难判定的．文献[1—2]中介绍了判定前五种性质的方法．本文重点研究关系的反传递性的判定方法，深入分析传递性和反传递性关系矩阵的特征，进而给出了判定传递性和反传递性的算法，并利用C语言编程实现．2关系的传递性和反传递性的定义定义1设R为集合A上的二元关系，则(i)若对于任意z，Y，zEA，如果(，)ER且(，2)ER，那么(z，)ER，则称R在A上是传递的；(ii)若对于任意z，Y，zEA，如果(z，

3、)ER且(，z)ER，那么(z，z)R，则称R在A上是反传递的．3传递性与反传递性的判定方法根据定义可以判定关系的传递性和反传递性，但往往比较麻烦，E5-]中给出了其他判定传递性的方法．3．1传递性的判定方法(1)关系运算法定理1嘲设R是A上的二元关系，则有R在A上是传递的甘R。RR．(2)关系图法传递关系的关系图具有的特点是：任取三节点，，，若从z到Y有边，从Y到2有边，则从到2一定有边．(3)关系矩阵法传递关系的关系矩阵M具有的特点是：m—1且m=1，必有m=1，i，J，点一1，2，⋯，．(4)关系的复合矩阵法R。R的关系矩阵记为M，由关系的复合运算和

4、矩阵的逻辑乘定义，有：MR。MR，其中。为矩阵的逻辑乘运算．传递关系的复合矩阵具有的特点是：中1所在位置，M中相应位置都是1．定义2[矩阵A：(口)，B一(6)，若口≤6，i，J一1，2，⋯，咒，则称A不超过B，记作A≤B．传递关系的复合矩阵具有的特点也可表述为：M≤MR．收藕日期：2014—04—23作者简介：董丽欣(1982-)，女，汉族，河北邯郸人，讲师．研究方向：复杂网络及其应用第2期董丽欣：二元关系传递性与反传递性的判定53．2反传递性的判定方法由反传递性的定义，我们可得到以下判定反传递性的方法．(1)关系运算法定理2设R是A上的二元关系，则有R

5、在A上是反传递的甘R。RnR一．(2)关系图法反传递关系的关系图具有的特点是：任取三节点，，，若从到Y有边，从Y到有边，则从到一定没有边．(3)关系矩阵法反传递关系的关系矩阵MR具有的特点是：m。=1且m：1，必有=0，i，J，k一1，2，⋯，竹．(4)关系的复合矩阵法反传递关系的复合矩阵具有的特点是：’中1所在位置，中相应位置都是0．反传递关系的复合矩阵具有的特点也可表述为：和M中对应元素的乘积都是0．4传递性和反传递性之间的联系关系传递性和反传递性之间的联系可以借助文氏图形象化的表示，如图1：图1传递性和反传递性之间的联系(i)关系复合矩阵中元素全为0

6、，则该关系既是传递的又是反传递的；(ii)关系复合矩阵中1所在位置，关系矩阵MR中相应位置元素都是1，则该关系是传递的；(iii)关系复合矩阵中1所在位置，关系矩阵中相应位置元素都是0，则该关系是反传递的；(Vi)关系复合矩阵中1所在位置，关系矩阵M_R中相应位置元素一部分是1，一部分是O，则该关系既不是传递的又不是反传递的．5算法描述及C程序实现5．1算法描述利用关系的复合矩阵法建立判定传递性和反传递性的算法，通过主函数调用判定传递与反传递子函数来实现，其主函数算法步骤描述如下：(i)输入集合A的元素个数；(ii)输入关系矩阵MR的各个元素；(iii)调

7、用判定传递与反传递子函数．判定传递与反传递子函数算法流程图如图2所示：青海师范大学学报(自然科学版)2014血图2判定传递与反传递子函数算法流程图5．2C程序实现#include#defineM10voidmain(){intaEM]EM]，i，j，n；voidcdx(intaiM-]l-M-]，intn)；printf(”请输入关系矩阵的阶数n(n<一M)：＼n”)；scanf(”％d”，8Ln)；printf(”输入关系矩阵的元素值(O或1)：＼n”)；for(i=0；i

8、6d”，&aEi；Ej3)；cdx(a．n)：voidedx(in