论文部分内容阅读
【摘要】本文分析了盖住关系的特点，并进行理论上的证明.以关系矩阵运算为基础，给出了一个整数集上的哈斯图的算法，该方法能简单、方便地求出盖住关系，从而得到哈斯图.
【关键词】盖住关系;哈斯图;关系矩阵
【基金项目】西南林业大学教育科学研究项目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.
【关键词】盖住关系;哈斯图;关系矩阵
【基金项目】西南林业大学教育科学研究项目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.