一种构造Hasse图的高效算法

王善坤

(大连理工大学城市学院网络信息中心，辽宁大连 116600)

一种构造Hasse图的高效算法

王善坤

(大连理工大学城市学院网络信息中心，辽宁大连 116600)

目前在国内外的文献上，关于Hasse图的构造方法都是基于纯粹的数学矩阵变换方法，而非计算机算法，其缺点是不论最好还是最坏情况，其时间复杂度都是0(n3)，进而无法为特殊情况作出优化。为此给出一种构造Hasse图的通用高效算法。该方法从计算机算法的角度对矩阵中单个元素进行计算，当矩阵中所需计算的元素较少时，算法的时间复杂度会相应的降低，在最好的情况下，时间复杂度将接近0(n2)，而在最坏的情况下，时间复杂度仍保持在0(n3)。

Hasse图;偏序集;偏序关系;算法;覆盖关系

偏序关系可以用偏序图来表示，而Hasse图可以极大的简化偏序图，使偏序关系一目了然，并且依据Hasse图可以快速求解偏序关系的相关性质。国内外的文献上面，构造Hasse图的方法都是基于纯粹的数学矩阵变换，而不是计算机算法。本文在前人研究基础上，将矩阵变换与计算机算法相结合，给出一种高效通用的Hasse图构造算法。

1 基本概念

定义1 集合A上的关系R称为A的偏序关系，条件是R具有关系的自反性、反对称性和传递性。换句话说，R满足下列条件［1］。

(ⅰ)a R a对所有a∈A成立(即R是自反的);

(ⅱ) 对所有 a，b∈A，如果 a R b且 b R a，则a=b(即R是反对称的);

(ⅲ) 对所有 a，b，c∈A，如果 a R b 且 b R c，则a R c(即R是传递的)。集合A和偏序关系R合称为偏序集，记做＜A，R＞。

定义2 在偏序集 ＜A，R＞中，若x，y∈A，＜x，y＞∈ R，x ≠y，且没有其他元素 z满足 ＜ x，z＞∈R，＜z，y＞∈R，则称元素 y覆盖元素 x，并且记COV(A)={ ＜x，y ＞ |x，y∈A，y 覆盖 x}［2］。

定义3 在偏序集＜A，R＞中，若x，y∈A，＜x，y＞∈R，x ≠y，把 y放在 x上方，若 y覆盖 x，则用线段连接 x和 y。得到的图称为 ＜A，R＞的Hasse 图［3］。

Hasse图举例:

设 S={1，2，3}，则 P(S)={Ø，{1}，{2}，{3}，{1，2}，{2，3}，{1，3}，S}这时，＜P(S)，≤ ＞是一个偏序集，其中≤表示集合包含关系。偏序集 ＜P(S)，≤ ＞ 的 Hasse 图如图1［4］。

图1 ＜P(S)，≤ ＞的Hasse图

2 算法设计

算法要完成的功能即画出给定偏序集＜A，R＞的Hasse图。

2.1 实现方法

先根据偏序集＜A，R＞的关系构造出其对应的关系矩阵。设其关系矩阵为P，构造P的副本Q，即构造矩阵Q，且使Q=P，对P中任一元素Pi，j重复以下过程:

(1)将P与Q主对角线元素全部置零;

(2)若 Pi，j=0，直接跳过该元素，不做任何处理;

(3)若 Pi，j≠ 0，则扫描 P 中第 j行所有元素，对第 j行所有不为 0 的元素 Pj，k，执行 Qi，k=Qi，k－Qi，k* Pj，k。对 Q 中任一元素 Qi，j，若 Qi，j≠0，将点j放置于点i上方，连接点i与点j，构图完成。

2.2 算法对应的画图过程

(1)构造偏序集＜A，R＞的有向图;

(2)在有向图中，如果偏序集＜A，R＞中a覆盖b，则将顶点a放在顶点b之上;

(3)从有向图中删除所有环(因为关系是自反的，每个顶点上都有环，不必显示环，此过程对应算法中的第1步);

(4)删除传递性所蕴涵的所有有向边。例如，如果 aRb，bRc，则 aRc，因此省略从 a到 c的边(此过程对应算法中的第3步);

(5)省略有向边的箭头符号。

3 算法正确性证明

对给定的偏序集＜A，R＞，由离散数学知识，可以知道

4 算法关键点解释

该算法的关键点在于构造P的副本Q，并用在P中的运算结果来修正矩阵Q。可以将P看成是“只读的”输入数据，将修正后的Q看成是输出数据。

有同仁提出，是否可以将修正结果直接反映到 P 上，即使用 Pi，k=Pi，k－ Pi，k* Pj，k来替代 Qi，k=Qi，k－ Qi，k* Pj，k，其实这是不可以的，因为直接在P上做修正会破坏原始数据，进而破坏程序的正确性。

设偏序集＜A，R＞所对应的Hasse图如图2。

图2 偏序集＜A，R＞的Hasse图

5 算法实现

6 算法特点及时间复杂度分析

目前同仁给出的构造Hasse图的算法都是基于矩阵的整体变换［5］，这类算法的特点是不论最好情况还是最坏情况，时间复杂度都为O(n3)。而本论文所给出算法的最大特点是没有对矩阵做整体变换(如求逆、求转置等操作)，而是根据偏序集的关系矩阵中元素的值来决定是否处理与该元素相关的一些元素。可以看出，当R的关系矩阵中值为“1”的元素较少时，算法时间复杂度近似于O(n2)，在最坏情况下，时间复杂度为O(n3)。

7 算法实验及结果

例如，已知偏序集 ＜A，R ＞，其中 A={1，2，3，…，10}，R={ ＜1，1 ＞，＜2，2 ＞，＜3，3＞，＜4，4 ＞，＜5，5＞，＜6，6＞，＜7，7 ＞，＜8，8 ＞，＜9，9 ＞，＜10，10＞，＜1，5＞，＜1，6＞，＜2，3＞，＜2，10＞，＜3，4＞，＜5，7＞，＜5，10＞，＜6，9＞，＜7，8＞，＜9，10＞，＜2，4＞，＜1，10＞，＜1，9＞，＜6，8＞，＜5，8＞，＜1，8＞，＜1，7＞}。

根据给定的算法自动生成COV(B)的关系矩阵，进而很快求得:COV(B)={＜1，5＞，＜1，6＞，＜2，3＞，＜2，10＞，＜3，4＞，＜5，7＞，＜5，10＞，＜6，9＞，＜7，8＞，＜9，10＞}，再按作图规则，偏序集＜A，R＞的Hasse图如图3。

图3 偏序集＜A，R＞的Hasse图

本文的作者还对该算法进行了多例的验证，验证了该算法在整体性能不变的前提下，在某些情况下，运算效率确实高于已有算法，节约了运行时间，因篇幅原因，这里不再复述了。

［1］KENNETH H R.Discrete mathematics and its applications［M］.5 th ed.北京:机械工业出版社，2003.

［2］朱一清.离散数学［M］.北京:电子工业出版社，1998.

［3］BRUALDI R A.Introductory com binatorics［M］.3rd ed.北京:机械工业出版社，2003.

［4］MALIK D S.离散数学结构:理论与应用［M］.邱仲，译.北京:高等教育出版社，2005.

［5］丁树良.求偏序关系Hasse图的算法［J］.江西师范大学学报:自然科学版，2005，29(2):150 －152.

An Efficient Algorithm to Construct Hasse Diagram

WANG Shan－kun
(Network Information Center，Cityinstitute，Dalian University of Technology，DaLian Liaoning 116600，China)

In domestic and foreign literature，the way to construct Hasse Diagram is researched only based on pure mathematic conversion of Matrix not computer algorithm.However，no matter in which case，the best or the worst，the time complexity of the algorithms is always constant，which is 0(n3)，so some special case is difficult to be optimized.In this paper we provide a general high efficient way to construct Hasse Diagram from the computer perspective，which some elements in matrix is processed in computer.When the elements to be worked on in matrix become less，the time complexity of calculation will decrease，which in the best case，the time complexity almost is equal to 0(n2)，while in the worst case，the time complexity still remains around 0(n3)

Hasse Diagram;partially ordered set;partial ordering relation;algorithm;covering relation.

TP301.6

A

1009－315X(2012)01－0043－03

2011－10－18;最后

2011－11－15

王善坤(1960－)，男，辽宁大连人，讲师，主要从事数据库应用、计算机网络、嵌入式应用研究。

(责任编辑 邹永红)