整數集上的哈斯圖的求法

王清暉

【摘要】本文分析了蓋住關系的特點，并進行理論上的證明.以關系矩陣運算為基礎，給出了一個整數集上的哈斯圖的算法，該方法能簡單、方便地求出蓋住關系，從而得到哈斯圖.

【關鍵詞】蓋住關系;哈斯圖;關系矩陣

【基金項目】西南林業大學教育科學研究項目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.