整數(shù)集上的哈斯圖的求法

王清暉

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

【關(guān)鍵詞】蓋住關(guān)系;哈斯圖;關(guān)系矩陣

【基金項目】西南林業(yè)大學(xué)教育科學(xué)研究項目YB201651.

關(guān)系是離散數(shù)學(xué)中一個基本的概念，兩個集合的笛卡爾積的子集確定了一個二元關(guān)系，它表示了客體之間的聯(lián)系.其中很重要的一類是偏序關(guān)系，它考慮了元素間的次序關(guān)系.

哈斯圖能清楚、簡單、直觀地表示元素間的次序和層次關(guān)系，而圖可以用矩陣表達(dá)出來，矩陣是代數(shù)學(xué)中的常見工具，這就便于用代數(shù)方法研究圖，同時也便于計算機(jī)的存儲和處理.用矩陣運算來求解哈斯圖就成為本文的研究目標(biāo).求哈斯圖的一般方法就是根據(jù)偏序集，求出蓋住關(guān)系，運用蓋住關(guān)系，畫出哈斯圖，所以求出偏序關(guān)系的哈斯圖，蓋住關(guān)系的得出是一個關(guān)鍵，本文以關(guān)系矩陣為基礎(chǔ)，提出一種新的算法，得到蓋住關(guān)系的關(guān)系矩陣，從而求出哈斯圖.

一、預(yù)備知識

定義1[1] 設(shè)A是一個集合，如果A上的一個關(guān)系R，滿足自反性，反對稱性和傳遞性，則稱R是A上的一個偏序關(guān)系，并把它記為“≤”.序偶〈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] 設(shè)給定兩個有限集合X={x1，x2，…，xm}，Y={y1，y2，…，yn}，R為從X到Y(jié)的一個二元關(guān)系.則對應(yīng)于關(guān)系R有一個關(guān)系矩陣MR=[rij]m×n，其中

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

哈斯圖的作圖規(guī)則：

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

（2）如果x≤y且x≠y，則將代表y的小圓圈畫在代表x的小圓圈之上.

（3）如果〈x，y〉∈COVA，則在x與y之間用直線連接.

二、理論準(zhǔn)備

（一）偏序關(guān)系R的關(guān)系矩陣特點

（1）在關(guān)系矩陣中，所有對角線元素都是1.

（2）在關(guān)系矩陣中，以主對角線對稱的元素不能同時為1.

（3）在關(guān)系矩陣中，若〈x，y〉∈R，〈y，z〉∈R，則元素x所在的行與元素y所在行的第z列元素都是1.即〈y，z〉，〈x，z〉在關(guān)系矩陣的同一列.

證明 （1）（2）顯然成立.

（3）因為是偏序關(guān)系，所以滿足自反性、反對稱性和傳遞性，故當(dāng)〈x，y〉∈R，〈y，z〉∈R，則〈x，z〉∈R，即〈y，z〉∈R且〈x，z〉∈R，所以元素x所在的行與元素y所在行的第z列元素都是1.

（二）集合A的蓋住關(guān)系COVA的關(guān)系矩陣特點

（1）在關(guān)系矩陣中，所有對角線元素都是0.

（2）在關(guān)系矩陣中，以主對角線對稱的元素不能同時為1.

（3）在關(guān)系矩陣中，若〈x，y〉∈R，〈y，z〉∈R，則元素y所在的行第z列元素為1，則元素x所在行的第z列元素為0.

證明 （1）根據(jù)蓋住關(guān)系的定義，x∈A，〈x，x〉COVA，所以所有對角線元素都是0.

（1）顯然成立.

（2）因為蓋住關(guān)系不滿足傳遞性，則當(dāng)〈x，y〉∈COVA，〈y，z〉∈COVA，則〈x，z〉COVA，所以若〈x，y〉∈R，〈y，z〉∈R，則元素y所在的行第z列元素為1，則元素x所在行的第z列元素為0.

三、求蓋住關(guān)系的算法思路

矩陣是數(shù)學(xué)中的常用工具，它能清楚地表述出元素之間的關(guān)系.根據(jù)集合A的蓋住關(guān)系COVA的關(guān)系矩陣特點，歸納出求蓋住關(guān)系的思路如下：

（1）在偏序關(guān)系的關(guān)系矩陣上，令所有對角線元素都是0，則去除了自反性.

（2）在偏序關(guān)系中，當(dāng)〈x，y〉∈R，〈y，z〉∈R則〈x，z〉∈R，為了消除傳遞關(guān)系，〈y，z〉，〈x，z〉在關(guān)系矩陣的同一列，當(dāng)〈x，y〉∈R，用元素y所在的行的元素減去元素x所在的行的元素，作為元素x所在行的元素.要求：若相減數(shù)值為0，則元素x所在行的元素所對應(yīng)的數(shù)值為0，其他情況下所對應(yīng)的數(shù)值不變，得到COVA.

（3）根據(jù)蓋住關(guān)系的矩陣表示，就可得到所求的哈斯圖.

四、算法描述

（1）集合里的元素從小到大排序，按此順序?qū)懗鏊鶎?yīng)的偏序關(guān)系，寫出偏序關(guān)系矩陣A.

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

（3）i：=1.

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

用第k行的元素減去第i行的元素，作為第i行的元素.若相減數(shù)值為0，則第i行所對應(yīng)的數(shù)值為0，其他情況下第i行所對應(yīng)的數(shù)值不變.

（5）i：=i+1.

（6）如果i≤n，轉(zhuǎn)到步驟（4），否則停止.

五、算法實例

設(shè)集合{2，3，6，12，24}上的偏序關(guān)系為整除，集合里的元素已經(jīng)從小到大排序，寫出所對應(yīng)的偏序關(guān)系為

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〉，

則該關(guān)系所對應(yīng)的關(guān)系矩陣為

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

根據(jù)步驟（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，

則用第三行元素分別減去所對應(yīng)的第一行的元素，作為第一行的元素，得矩陣為

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，

則用第三行元素分別減去所對應(yīng)的第二行的元素，作為第二行的元素，得矩陣為

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，

則用第四行元素分別減去所對應(yīng)的第三行的元素，作為第三行的元素，得矩陣為

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

依此類推，最終得到關(guān)系矩陣為

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

則所對應(yīng)的蓋住關(guān)系為

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

則所對應(yīng)的哈斯圖為

六、結(jié)束語

本文探討了蓋住關(guān)系的關(guān)系矩陣特點，并給出了理論上的證明，根據(jù)蓋住關(guān)系的性質(zhì)，以矩陣為工具，采用本文提出的算法，從代數(shù)的角度，通過矩陣的運算得到蓋住關(guān)系矩陣.從而解決哈斯圖的求法問題，以所得到的理論為基礎(chǔ)，給出了具體的實例，驗證了算法的有效性.

【參考文獻(xiàn)】

[1]左孝凌，李為鑑，劉永才.離散數(shù)學(xué)[M].上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版社，1982.

[2]陳莉，劉曉霞.離散數(shù)學(xué)[M].北京：高等教育出版社，2002.

[3]潘美芹，丁志軍.一個快速求解哈斯圖的算法[J].山東科技大學(xué)學(xué)報（自然科學(xué)版），2003（3）：88-89.