哈斯圖

哈斯圖（英語：Hasse 发音为/ˈhæsə/, 德語: /ˈhasə/）、在數學分支序理論中，是用來表示有限偏序集的一種數學圖表，它是一種圖形形式的對偏序集的傳遞簡約。具體的說，對於偏序集合(S, ≤)，把S的每個元素表示為平面上的頂點，然後若元素y覆蓋x（就是說，x < y並且沒有z使得 x < z < y），則繪製從x到y向上的線段或弧線。這些弧線可以相互交叉但不能觸及任何非其端點的頂點。帶有標註的頂點的這種圖唯一確定這個集合的偏序。

哈斯圖得名於德國數學家赫爾穆特·哈斯；依據Birkhoff (1948)，這麼叫是因為哈斯有效的利用了它們。但是哈斯不是第一個使用它們的人，它們早就出現在如Vogt (1895)中。儘管哈斯圖被設計為手工繪製偏序集合的技術，最近已經使用圖繪製技術自動來生成它們了。

術語“哈斯圖”還可以稱呼作為抽象有向無環圖的傳遞簡約，獨立於這個圖的任何繪製形式，但是這裡不採用這種用法。

例子

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

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

• 集合{ 1, 2, 3, 4 }的所有15個劃分，按精細度（就是更細劃分小於更粗劃分）排序，有哈斯圖:

一个“良好”的哈斯圖

儘管哈斯圖是簡單的處理有限偏序集的直觀工具，繪製出好的哈斯圖是非常困難的。原因是對於給定偏序集有任意多種可能的繪圖方式。簡單的技術就是開始於這個次序的最小元並逐步增加上更大的元素，這經常產生非常窘迫的結果：很容易丟失了這個次序的對稱性和內部結構。

下面的例子展示這個問題。考慮集合S = {a, b, c, d}的冪集${\mathcal {P}}(S)\,$，就是說S的所有自己的集合，按照子集包含$\subseteq$來排序。下面是這個偏序的三個不同哈斯圖:

通過使得在這個冪集中每個集合的y坐標成比例於集合的勢，最左圖示展示了這個冪集是等級偏序集。中間圖示有相同的等級結構，但使得某些邊比其他邊長，它把這個冪集的結構強調為兩個三維立方體的聯合：在兩個立方體中下面的那個中的頂點表示不包含S的某個特定元素比如d的集合，而上面立方體的頂點表示包含d的集合。最右圖示展示了這個結構的某種內部對稱性。

引用

• Baker, K. A.; Fishburn, P.; Roberts, F. S., Partial orders of dimension 2, Networks, 1971, 2 (1): 11–28, doi:10.1002/net.3230020103 .
• Bertolazzi, R; Di Battista, G.; Mannino, C.; Tamassia, R., Optimal upward planarity testing of single-source digraphs, Proc. 1st European Symposium on Algorithms (ESA '93), Lecture Notes in Computer Science 726, Springer-Verlag: 37–48, 1993, doi:10.1007/3-540-57273-2_42 .
• Birkhoff, Garrett, Lattice Theory Revised, American Mathematical Society, 1948 .
• Chan, Hubert, A parameterized algorithm for upward planarity testing, Proc. 12th European Symposium on Algorithms (ESA '04), Lecture Notes in Computer Science 3221, Springer-Verlag: 157–168, 2004 .
• Di Battista, G.; Tamassia, R., Algorithms for plane representation of acyclic digraphs, Theoretical Computer Science, 1988, 61: 175–178, doi:10.1016/0304-3975(88)90123-5 .
• Freese, Ralph, Automated lattice drawing, Concept Lattices, Lecture Notes in Computer Science 2961, Springer-Verlag: 589–590, 2004 . An extended preprint is available online: [1]Portuguese Web Archive的存檔，存档日期2016-03-14.
• Garg, Ashim; Tamassia, Roberto, Upward planarity testing, Order, 1995a, 12 (2): 109–133, doi:10.1007/BF01108622 .
• Garg, Ashim; Tamassia, Roberto, On the computational complexity of upward and rectilinear planarity testing, Graph Drawing (Proc. GD '94), LectureNotes in Computer Science 894, Springer-Verlag: 286–297, 1995b, doi:10.1007/3-540-58950-3_384 .
• Jünger, Michael; Leipert, Sebastian, Level planar embedding in linear time, Graph Drawing (Proc. GD '99): 72–81, 1999, doi:10.1007/3-540-46648-7_7 .
• Vogt, Henri Gustav, Leçons sur la résolution algébrique des équations, Nony: 91, 1895 .

外部連結

• Hasse diagrams of divisors
• How to draw hasse diagrams of binary relations（页面存档备份，存于互联网档案馆）
• "Hasse Diagram" on MathWorld（页面存档备份，存于互联网档案馆）