一種構造Hasse圖的高效算法

王善坤

(大連理工大學城市學院網絡信息中心，遼寧大連 116600)

一種構造Hasse圖的高效算法

王善坤

(大連理工大學城市學院網絡信息中心，遼寧大連 116600)

目前在國內外的文獻上，關于Hasse圖的構造方法都是基于純粹的數學矩陣變換方法，而非計算機算法，其缺點是不論最好還是最壞情況，其時間復雜度都是0(n3)，進而無法為特殊情況作出優化。為此給出一種構造Hasse圖的通用高效算法。該方法從計算機算法的角度對矩陣中單個元素進行計算，當矩陣中所需計算的元素較少時，算法的時間復雜度會相應的降低，在最好的情況下，時間復雜度將接近0(n2)，而在最壞的情況下，時間復雜度仍保持在0(n3)。

Hasse圖;偏序集;偏序關系;算法;覆蓋關系

偏序關系可以用偏序圖來表示，而Hasse圖可以極大的簡化偏序圖，使偏序關系一目了然，并且依據Hasse圖可以快速求解偏序關系的相關性質。國內外的文獻上面，構造Hasse圖的方法都是基于純粹的數學矩陣變換，而不是計算機算法。本文在前人研究基礎上，將矩陣變換與計算機算法相結合，給出一種高效通用的Hasse圖構造算法。

1 基本概念

定義1 集合A上的關系R稱為A的偏序關系，條件是R具有關系的自反性、反對稱性和傳遞性。換句話說，R滿足下列條件［1］。

(ⅰ)a R a對所有a∈A成立(即R是自反的);

(ⅱ) 對所有 a，b∈A，如果 a R b且 b R a，則a=b(即R是反對稱的);

(ⅲ) 對所有 a，b，c∈A，如果 a R b 且 b R c，則a R c(即R是傳遞的)。集合A和偏序關系R合稱為偏序集，記做＜A，R＞。

定義2 在偏序集 ＜A，R＞中，若x，y∈A，＜x，y＞∈ R，x ≠y，且沒有其他元素 z滿足 ＜ x，z＞∈R，＜z，y＞∈R，則稱元素 y覆蓋元素 x，并且記COV(A)={ ＜x，y ＞ |x，y∈A，y 覆蓋 x}［2］。

定義3 在偏序集＜A，R＞中，若x，y∈A，＜x，y＞∈R，x ≠y，把 y放在 x上方，若 y覆蓋 x，則用線段連接 x和 y。得到的圖稱為 ＜A，R＞的Hasse 圖［3］。

Hasse圖舉例:

設 S={1，2，3}，則 P(S)={?，{1}，{2}，{3}，{1，2}，{2，3}，{1，3}，S}這時，＜P(S)，≤ ＞是一個偏序集，其中≤表示集合包含關系。偏序集 ＜P(S)，≤ ＞ 的 Hasse 圖如圖1［4］。

圖1 ＜P(S)，≤ ＞的Hasse圖

2 算法設計

算法要完成的功能即畫出給定偏序集＜A，R＞的Hasse圖。

2.1 實現方法

先根據偏序集＜A，R＞的關系構造出其對應的關系矩陣。設其關系矩陣為P，構造P的副本Q，即構造矩陣Q，且使Q=P，對P中任一元素Pi，j重復以下過程:

(1)將P與Q主對角線元素全部置零;

(2)若 Pi，j=0，直接跳過該元素，不做任何處理;

(3)若 Pi，j≠ 0，則掃描 P 中第 j行所有元素，對第 j行所有不為 0 的元素 Pj，k，執行 Qi，k=Qi，k－Qi，k* Pj，k。對 Q 中任一元素 Qi，j，若 Qi，j≠0，將點j放置于點i上方，連接點i與點j，構圖完成。

2.2 算法對應的畫圖過程

(1)構造偏序集＜A，R＞的有向圖;

(2)在有向圖中，如果偏序集＜A，R＞中a覆蓋b，則將頂點a放在頂點b之上;

(3)從有向圖中刪除所有環(因為關系是自反的，每個頂點上都有環，不必顯示環，此過程對應算法中的第1步);

(4)刪除傳遞性所蘊涵的所有有向邊。例如，如果 aRb，bRc，則 aRc，因此省略從 a到 c的邊(此過程對應算法中的第3步);

(5)省略有向邊的箭頭符號。

3 算法正確性證明

對給定的偏序集＜A，R＞，由離散數學知識，可以知道

4 算法關鍵點解釋

該算法的關鍵點在于構造P的副本Q，并用在P中的運算結果來修正矩陣Q。可以將P看成是“只讀的”輸入數據，將修正后的Q看成是輸出數據。

有同仁提出，是否可以將修正結果直接反映到 P 上，即使用 Pi，k=Pi，k－ Pi，k* Pj，k來替代 Qi，k=Qi，k－ Qi，k* Pj，k，其實這是不可以的，因為直接在P上做修正會破壞原始數據，進而破壞程序的正確性。

設偏序集＜A，R＞所對應的Hasse圖如圖2。

圖2 偏序集＜A，R＞的Hasse圖

5 算法實現

6 算法特點及時間復雜度分析

目前同仁給出的構造Hasse圖的算法都是基于矩陣的整體變換［5］，這類算法的特點是不論最好情況還是最壞情況，時間復雜度都為O(n3)。而本論文所給出算法的最大特點是沒有對矩陣做整體變換(如求逆、求轉置等操作)，而是根據偏序集的關系矩陣中元素的值來決定是否處理與該元素相關的一些元素。可以看出，當R的關系矩陣中值為“1”的元素較少時，算法時間復雜度近似于O(n2)，在最壞情況下，時間復雜度為O(n3)。

7 算法實驗及結果

例如，已知偏序集 ＜A，R ＞，其中 A={1，2，3，…，10}，R={ ＜1，1 ＞，＜2，2 ＞，＜3，3＞，＜4，4 ＞，＜5，5＞，＜6，6＞，＜7，7 ＞，＜8，8 ＞，＜9，9 ＞，＜10，10＞，＜1，5＞，＜1，6＞，＜2，3＞，＜2，10＞，＜3，4＞，＜5，7＞，＜5，10＞，＜6，9＞，＜7，8＞，＜9，10＞，＜2，4＞，＜1，10＞，＜1，9＞，＜6，8＞，＜5，8＞，＜1，8＞，＜1，7＞}。

根據給定的算法自動生成COV(B)的關系矩陣，進而很快求得:COV(B)={＜1，5＞，＜1，6＞，＜2，3＞，＜2，10＞，＜3，4＞，＜5，7＞，＜5，10＞，＜6，9＞，＜7，8＞，＜9，10＞}，再按作圖規則，偏序集＜A，R＞的Hasse圖如圖3。

圖3 偏序集＜A，R＞的Hasse圖

本文的作者還對該算法進行了多例的驗證，驗證了該算法在整體性能不變的前提下，在某些情況下，運算效率確實高于已有算法，節約了運行時間，因篇幅原因，這里不再復述了。

［1］KENNETH H R.Discrete mathematics and its applications［M］.5 th ed.北京:機械工業出版社，2003.

［2］朱一清.離散數學［M］.北京:電子工業出版社，1998.

［3］BRUALDI R A.Introductory com binatorics［M］.3rd ed.北京:機械工業出版社，2003.

［4］MALIK D S.離散數學結構:理論與應用［M］.邱仲，譯.北京:高等教育出版社，2005.

［5］丁樹良.求偏序關系Hasse圖的算法［J］.江西師范大學學報:自然科學版，2005，29(2):150 －152.

An Efficient Algorithm to Construct Hasse Diagram

WANG Shan－kun
(Network Information Center，Cityinstitute，Dalian University of Technology，DaLian Liaoning 116600，China)

In domestic and foreign literature，the way to construct Hasse Diagram is researched only based on pure mathematic conversion of Matrix not computer algorithm.However，no matter in which case，the best or the worst，the time complexity of the algorithms is always constant，which is 0(n3)，so some special case is difficult to be optimized.In this paper we provide a general high efficient way to construct Hasse Diagram from the computer perspective，which some elements in matrix is processed in computer.When the elements to be worked on in matrix become less，the time complexity of calculation will decrease，which in the best case，the time complexity almost is equal to 0(n2)，while in the worst case，the time complexity still remains around 0(n3)

Hasse Diagram;partially ordered set;partial ordering relation;algorithm;covering relation.

TP301.6

A

1009－315X(2012)01－0043－03

2011－10－18;最后

2011－11－15

王善坤(1960－)，男，遼寧大連人，講師，主要從事數據庫應用、計算機網絡、嵌入式應用研究。

(責任編輯 鄒永紅)