一種構(gòu)造Hasse圖的高效算法

王善坤

(大連理工大學(xué)城市學(xué)院網(wǎng)絡(luò)信息中心，遼寧大連 116600)

一種構(gòu)造Hasse圖的高效算法

王善坤

(大連理工大學(xué)城市學(xué)院網(wǎng)絡(luò)信息中心，遼寧大連 116600)

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

Hasse圖;偏序集;偏序關(guān)系;算法;覆蓋關(guān)系

偏序關(guān)系可以用偏序圖來表示，而Hasse圖可以極大的簡化偏序圖，使偏序關(guān)系一目了然，并且依據(jù)Hasse圖可以快速求解偏序關(guān)系的相關(guān)性質(zhì)。國內(nèi)外的文獻(xiàn)上面，構(gòu)造Hasse圖的方法都是基于純粹的數(shù)學(xué)矩陣變換，而不是計(jì)算機(jī)算法。本文在前人研究基礎(chǔ)上，將矩陣變換與計(jì)算機(jī)算法相結(jié)合，給出一種高效通用的Hasse圖構(gòu)造算法。

1 基本概念

定義1 集合A上的關(guān)系R稱為A的偏序關(guān)系，條件是R具有關(guān)系的自反性、反對稱性和傳遞性。換句話說，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和偏序關(guān)系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圖舉例:

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

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

2 算法設(shè)計(jì)

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

2.1 實(shí)現(xiàn)方法

先根據(jù)偏序集＜A，R＞的關(guān)系構(gòu)造出其對應(yīng)的關(guān)系矩陣。設(shè)其關(guān)系矩陣為P，構(gòu)造P的副本Q，即構(gòu)造矩陣Q，且使Q=P，對P中任一元素Pi，j重復(fù)以下過程:

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

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

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

2.2 算法對應(yīng)的畫圖過程

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

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

(3)從有向圖中刪除所有環(huán)(因?yàn)殛P(guān)系是自反的，每個(gè)頂點(diǎn)上都有環(huán)，不必顯示環(huán)，此過程對應(yīng)算法中的第1步);

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

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

3 算法正確性證明

對給定的偏序集＜A，R＞，由離散數(shù)學(xué)知識，可以知道

4 算法關(guān)鍵點(diǎn)解釋

該算法的關(guān)鍵點(diǎn)在于構(gòu)造P的副本Q，并用在P中的運(yùn)算結(jié)果來修正矩陣Q。可以將P看成是“只讀的”輸入數(shù)據(jù)，將修正后的Q看成是輸出數(shù)據(jù)。

有同仁提出，是否可以將修正結(jié)果直接反映到 P 上，即使用 Pi，k=Pi，k－ Pi，k* Pj，k來替代 Qi，k=Qi，k－ Qi，k* Pj，k，其實(shí)這是不可以的，因?yàn)橹苯釉赑上做修正會破壞原始數(shù)據(jù)，進(jìn)而破壞程序的正確性。

設(shè)偏序集＜A，R＞所對應(yīng)的Hasse圖如圖2。

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

5 算法實(shí)現(xiàn)

6 算法特點(diǎn)及時(shí)間復(fù)雜度分析

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

7 算法實(shí)驗(yàn)及結(jié)果

例如，已知偏序集 ＜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＞}。

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

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

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

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

［2］朱一清.離散數(shù)學(xué)［M］.北京:電子工業(yè)出版社，1998.

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

［4］MALIK D S.離散數(shù)學(xué)結(jié)構(gòu):理論與應(yīng)用［M］.邱仲，譯.北京:高等教育出版社，2005.

［5］丁樹良.求偏序關(guān)系Hasse圖的算法［J］.江西師范大學(xué)學(xué)報(bào):自然科學(xué)版，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－)，男，遼寧大連人，講師，主要從事數(shù)據(jù)庫應(yīng)用、計(jì)算機(jī)網(wǎng)絡(luò)、嵌入式應(yīng)用研究。

(責(zé)任編輯 鄒永紅)