整数集上的哈斯图的求法

王清晖

【摘要】本文分析了盖住关系的特点，并进行理论上的证明.以关系矩阵运算为基础，给出了一个整数集上的哈斯图的算法，该方法能简单、方便地求出盖住关系，从而得到哈斯图.

【关键词】盖住关系;哈斯图;关系矩阵

【基金项目】西南林业大学教育科学研究项目YB201651.

关系是离散数学中一个基本的概念，两个集合的笛卡尔积的子集确定了一个二元关系，它表示了客体之间的联系.其中很重要的一类是偏序关系，它考虑了元素间的次序关系.

哈斯图能清楚、简单、直观地表示元素间的次序和层次关系，而图可以用矩阵表达出来，矩阵是代数学中的常见工具，这就便于用代数方法研究图，同时也便于计算机的存储和处理.用矩阵运算来求解哈斯图就成为本文的研究目标.求哈斯图的一般方法就是根据偏序集，求出盖住关系，运用盖住关系，画出哈斯图，所以求出偏序关系的哈斯图，盖住关系的得出是一个关键，本文以关系矩阵为基础，提出一种新的算法，得到盖住关系的关系矩阵，从而求出哈斯图.

一、预备知识

定义1[1] 设A是一个集合，如果A上的一个关系R，满足自反性，反对称性和传递性，则称R是A上的一个偏序关系，并把它记为“≤”.序偶〈A，≤〉称作偏序集.

定义2[1] 在偏序集合中〈A，≤〉，如果x，y∈A，x≤y，x≠y且没有其他元素z满足x≤y，y≤z，则称元素y盖住元素x.并且记COVA={〈x，y〉|x，y∈A;y盖住x}.

定义3[1] 设给定两个有限集合X={x1，x2，…，xm}，Y={y1，y2，…，yn}，R為从X到Y的一个二元关系.则对应于关系R有一个关系矩阵MR=[rij]m×n，其中

rij=1，〈xi，yj〉∈R，0，〈xi，yj〉R， （i=1，2，…，m;j=1，2，…，n）.

哈斯图的作图规则：

（1）用小圆圈代表元素.

（2）如果x≤y且x≠y，则将代表y的小圆圈画在代表x的小圆圈之上.

（3）如果〈x，y〉∈COVA，则在x与y之间用直线连接.

二、理论准备

（一）偏序关系R的关系矩阵特点

（1）在关系矩阵中，所有对角线元素都是1.

（2）在关系矩阵中，以主对角线对称的元素不能同时为1.

（3）在关系矩阵中，若〈x，y〉∈R，〈y，z〉∈R，则元素x所在的行与元素y所在行的第z列元素都是1.即〈y，z〉，〈x，z〉在关系矩阵的同一列.

证明 （1）（2）显然成立.

（3）因为是偏序关系，所以满足自反性、反对称性和传递性，故当〈x，y〉∈R，〈y，z〉∈R，则〈x，z〉∈R，即〈y，z〉∈R且〈x，z〉∈R，所以元素x所在的行与元素y所在行的第z列元素都是1.

（二）集合A的盖住关系COVA的关系矩阵特点

（1）在关系矩阵中，所有对角线元素都是0.

（2）在关系矩阵中，以主对角线对称的元素不能同时为1.

（3）在关系矩阵中，若〈x，y〉∈R，〈y，z〉∈R，则元素y所在的行第z列元素为1，则元素x所在行的第z列元素为0.

证明 （1）根据盖住关系的定义，x∈A，〈x，x〉COVA，所以所有对角线元素都是0.

（1）显然成立.

（2）因为盖住关系不满足传递性，则当〈x，y〉∈COVA，〈y，z〉∈COVA，则〈x，z〉COVA，所以若〈x，y〉∈R，〈y，z〉∈R，则元素y所在的行第z列元素为1，则元素x所在行的第z列元素为0.

三、求盖住关系的算法思路

矩阵是数学中的常用工具，它能清楚地表述出元素之间的关系.根据集合A的盖住关系COVA的关系矩阵特点，归纳出求盖住关系的思路如下：

（1）在偏序关系的关系矩阵上，令所有对角线元素都是0，则去除了自反性.

（2）在偏序关系中，当〈x，y〉∈R，〈y，z〉∈R则〈x，z〉∈R，为了消除传递关系，〈y，z〉，〈x，z〉在关系矩阵的同一列，当〈x，y〉∈R，用元素y所在的行的元素减去元素x所在的行的元素，作为元素x所在行的元素.要求：若相减数值为0，则元素x所在行的元素所对应的数值为0，其他情况下所对应的数值不变，得到COVA.

（3）根据盖住关系的矩阵表示，就可得到所求的哈斯图.

四、算法描述

（1）集合里的元素从小到大排序，按此顺序写出所对应的偏序关系，写出偏序关系矩阵A.

（2）a[i，i]=0，i=1，2，…，n.

（3）i：=1.

（4）如果A[i，k]=1，k=2，…，n.

用第k行的元素减去第i行的元素，作为第i行的元素.若相减数值为0，则第i行所对应的数值为0，其他情况下第i行所对应的数值不变.

（5）i：=i+1.

（6）如果i≤n，转到步骤（4），否则停止.

五、算法实例

设集合{2，3，6，12，24}上的偏序关系为整除，集合里的元素已经从小到大排序，写出所对应的偏序关系为

R=〈2，6〉，〈2，12〉，〈2，24〉，〈3，6〉，〈3，12〉，

〈3，24〉，〈6，12〉，〈6，24〉，〈12，24〉，〈2，2〉，

〈3，3〉，〈6，6〉，〈12，12〉，〈24，24〉，

则该关系所对应的关系矩阵为

A=1 0 1 1 10 1 1 1 10 0 1 1 10 0 0 1 10 0 0 0 1 .

根据步骤（2），得到

A=0 0 1 1 10 0 1 1 10 0 0 1 10 0 0 0 10 0 0 0 0.

在第一行，有

a[1，3]=1，

则用第三行元素分别减去所对应的第一行的元素，作为第一行的元素，得矩阵为

A=0 0 1 0 00 0 1 1 10 0 0 1 10 0 0 0 10 0 0 0 0 .

在第二行，有

a[2，3]=1，

则用第三行元素分别减去所对应的第二行的元素，作为第二行的元素，得矩阵为

A=0 0 1 0 00 0 1 0 00 0 0 1 10 0 0 0 10 0 0 0 0 .

在第三行，有

a[3，4]=1，

则用第四行元素分别减去所对应的第三行的元素，作为第三行的元素，得矩阵为

A=0 0 1 0 00 0 1 0 00 0 0 1 00 0 0 0 10 0 0 0 0 .

依此类推，最终得到关系矩阵为

A=0 0 1 0 00 0 1 0 00 0 0 1 00 0 0 0 10 0 0 0 0 .

则所对应的盖住关系为

COVA={〈2，6〉，〈3，6〉，〈6，12〉，〈12，24〉}.

则所对应的哈斯图为

六、结束语

本文探讨了盖住关系的关系矩阵特点，并给出了理论上的证明，根据盖住关系的性质，以矩阵为工具，采用本文提出的算法，从代数的角度，通过矩阵的运算得到盖住关系矩阵.从而解决哈斯图的求法问题，以所得到的理论为基础，给出了具体的实例，验证了算法的有效性.

【参考文献】

[1]左孝凌，李为鑑，刘永才.离散数学[M].上海：上海科学技术文献出版社，1982.

[2]陈莉，刘晓霞.离散数学[M].北京：高等教育出版社，2002.

[3]潘美芹，丁志军.一个快速求解哈斯图的算法[J].山东科技大学学报（自然科学版），2003（3）：88-89.