[科普中國(guó)]-哈斯圖

簡(jiǎn)介

哈斯圖得名于Helmut Hasse（1898年–1979年）；依據(jù)Birkhoff (1948)，這么叫是因?yàn)镠asse有效的利用了它們。但是Hasse不是第一個(gè)使用它們的人，它們?cè)缇统霈F(xiàn)在如Vogt (1895)中。盡管哈斯圖被設(shè)計(jì)為手工繪制偏序集合的技術(shù)，最近已經(jīng)使用圖繪制技術(shù)自動(dòng)來(lái)生成它們了。1

術(shù)語(yǔ)“哈斯圖”還可以稱呼作為抽象有向無(wú)環(huán)圖的傳遞簡(jiǎn)約，獨(dú)立于這個(gè)圖的任何繪制形式。但是這里不采用這種用法。

圖中的每個(gè)結(jié)點(diǎn)表示集合A中的一個(gè)元素，結(jié)點(diǎn)的位置按它們?cè)谄蛑械拇涡驈牡紫蛏吓帕小＜磳?duì)任意a，b屬于A，若a≤b且a≠b,則a排在b的下邊。如果a≤b且a≠b，且不存在c∈A滿足a≤c且c≤b，則在a和b之間連一條線。這樣畫出的圖叫哈斯圖，又稱偏序集合圖。

作圖法（1）以“圓圈”表示元素；

（2）若x≤y,則y畫在x的上層；

（3）若y覆蓋x,則連線；

（4）不可比的元素可畫在同一層。

例題：畫出下列各關(guān)系的哈斯圖

1）P={1,2,3,4},的哈斯圖。

2）A={2,3,6,12,24,36},的哈斯圖。

3）A={1,2,3,5,6,10,15,30},的哈斯圖。

解如圖：哈斯圖L-12

例子{ x, y, z }的冪集按包含偏序排序，有哈斯圖:

所有60的除數(shù)的集合A = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 }，按整除性排序，有哈斯圖:

集合{ 1, 2, 3, 4 }的所有15個(gè)劃分，按精細(xì)度（就是更細(xì)劃分小于更粗劃分）排序，有哈斯圖:

好的哈斯圖盡管哈斯圖是簡(jiǎn)單的處理有限偏序集的直觀工具，繪制出好的哈斯圖是非常困難的。原因是對(duì)于給定偏序集有任意多種可能的繪圖方式。簡(jiǎn)單的技術(shù)就是開始于這個(gè)次序的最小元并逐步增加上更大的元素，這經(jīng)常產(chǎn)生非常窘迫的結(jié)果：很容易丟失了這個(gè)次序的對(duì)稱性和內(nèi)部結(jié)構(gòu)。

下面的例子展示這個(gè)問題?？紤]集合S = {a, b, c, d}的冪集，就是說(shuō)S的所有自己的集合，按照子集包含來(lái)排序。下面是這個(gè)偏序的三個(gè)不同哈斯圖:

通過(guò)使得在這個(gè)冪集中每個(gè)集合的y坐標(biāo)成比例于集合的勢(shì)，最左圖示展示了這個(gè)冪集是等級(jí)偏序集。中間圖示有相同的等級(jí)結(jié)構(gòu)，但使得某些邊比其他邊長(zhǎng)，它把這個(gè)冪集的結(jié)構(gòu)強(qiáng)調(diào)為兩個(gè)三維立方體的聯(lián)合：在兩個(gè)立方體中下面的那個(gè)中的頂點(diǎn)表示不包含S的某個(gè)特定元素比如d的集合，而上面立方體的頂點(diǎn)表示包含d的集合。最右圖示展示了這個(gè)結(jié)構(gòu)的某種內(nèi)部對(duì)稱性。