整数集上的哈斯图的求法

2019-11-30 13:09王清晖
数学学习与研究 2019年19期

王清晖

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

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

【基金项目】西南林业大学教育科学研究项目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.