资源描述：
《求偏序关系Hasse图的算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第29卷第2期江西师范大学学报(自然科学版)Vol.29No.22005年3月JOURNALOFJIANGXINORMALUNIVERSITY(NATURALSCIENCE)Mar.2005文章编号:1000-5862(2005)02-0150-03求偏序关系Hasse图的算法丁树良,罗芬(江西师范大学计算机信息工程学院,江西南昌330027)摘要:给出计算偏序集的盖住关系的关系矩阵的算法如下:Procedure求哈斯图对应关系阵(MR:nn偏序关系阵)Q:=MR-Ifori:=1tonforj:
2、=1tonfork:=1tonqik:=qik-qik*qij*qjkendendend{Q=[qij]为Hasse图对应关系}.关键词:偏序关系;盖住关系;Hasse图;算法中图分类号:O213文献标识码:A1问题的提出设R是有限集A={a1,,an}上自反,反对称,传递的二元关系,即R为A上的偏序关系,或称!A,R∀为偏序集(partialorderset,poset).通常,集合A上的二元关系用关系图来表示十分直观,而用关系矩阵表示则易于计算机处理.偏序关系的关系图较复杂,但相应的Hasse(哈斯)
3、图则较简单.画偏序关系R的Hasse图的关键是寻找相应于R的盖住关系(coveringrelation).定义1在偏序集!A,R∀中,若x,y#A,!x,y∀#R,x∃y,且A中没有其他元素,u满足!x,u∀#R且[1]!u,y∀#R,则称元素y盖住x,并且称covR(A)为偏序集!A,R∀的盖住关系(coveringrelation),其中[2]covR(A)={!x,y∀
4、x#A且y#A,!x,y∀#R且y盖住x},Hasse图的作图规则是:(%)用小圆圈表元素;(&)若!x,y∀#R,且x∃y,则将代表y的小圆圈画
5、在代表x的小圆圈之上;(∋)若!x,y∀#covR(A),则在x,y之间用直线连接.根据这一画法虽可作出Hasse图,但还是一件不容易的事情.因此,对给定的偏序关系,设计一个算法寻找相应的盖住关系,则是十分必要的.这个问题的实质就是对一个偏序关系的关系矩阵设计一种算法,寻找其对应的盖住关系矩阵Mc.2盖住关系的性质引理1偏序集!A,R∀的盖住关系covR(A)是反自反,反对称及反传递的,这里所说的A上的反传递关系S是指S满足以下性质:xyw(x#A(y#A(w#A(!x,y∀#S(!y,w∀#S)!x,w∀S)
6、.证由盖住关系的定义(定义1)可得.由反传递定义,知反传递关系必为反自反关系,故引理1也可以叙述为covR(A)为反对称及反传递的.由定义1还可以得到引理2R为A上偏序关系,则!x,y∀#R-covR(A),当且仅当存在u#A,使得x∃u,y∃u且!x,u∀#R及!u,y∀#R.对引理2中的!x,y∀#R-covR(A),我们称!x,y∀是经传递导出的.收稿日期:2004-11-05基金项目:国家自然科学基金(60263005)及江西省自然科学基金资助项目(0411021).作者简介:丁树良(1949-),男,江西樟树
7、人,教授,主要从事计算机辅助教学及应用统计的研究.第2期丁树良,等:求偏序关系Hasse图的算法1513如何由MR转化为MC由引理1和引理2,知欲由A上偏序关系R的关系矩阵MR导出对应的盖住关系阵MC,必须完成以下两项任务:第一,将MR中对角元均化为0,即令QMR-I,I为阶数合适的单位阵,为明确起见,下文中都是对Q进行讨论;第二,将MR中对应于偶对!ai,aj∀#R-covR(A)的元素mij化为0.若用图论的语言来叙述上面第二项任务,则可表达为:R对应的关系图G(R)中(注意,这时每个结点自回路均已消除)仅保留相邻两
8、点的连线(弧),删除所有可达而非相邻的结点之间的连线,我们称这种删除为∗清洗+.以下讨论如何∗清洗+的问题.这可以分成两种情况讨论:第一种情况:ai与aj之间仅有长度为2的路;第二种情况:ai与aj之间有长度大于2的路.3.1ai与aj之间仅有长度为2的路我们先讨论第一种情况.这又可分为:,ai与aj之间仅有一条长度为2的路;−ai与aj不止一条长度为2的路.对于,,知Q中qij=1且存在唯一的k,k∃i且k∃j,使得qik=qkj=1,为了使qij化为0,可以用Q的第i行qi.减去第k行qk.后仍作为Q的第i行,即qi
9、:=qi.-qk.(1)由假设已知qij=qik=qkj=1.(2)执行(1)的结果实际上是qit:=qit-qkt,t=1,2,,n.(3)由(2)知qik=1,故(3)也可以写成qit:=qit-qik*qkt,t=1,2,,n.(4)然而,有可能存在h∃j,使得通过(1)[(3),或(4)
