查看“︁哈斯圖”︁的源代码

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

哈斯圖得名於[[德國]]數學家[[赫爾穆特·哈斯]]；依據{{harvtxt|Birkhoff|1948}}，這麼叫是因為哈斯有效的利用了它們。但是哈斯不是第一個使用它們的人，它們早就出現在如{{harvtxt|Vogt|1895}}中。儘管哈斯圖被設計為手工繪製偏序集合的技術，最近已經使用[[圖繪製]]技術自動來生成它們了。<ref>E.g., see {{harvtxt|Di Battista|Tamassia|1988}} and {{harvtxt|Freese|2004}}.</ref>

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

==例子==

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

:[[File:Hasse diagram of powerset of 3.svg|none|300px|]]

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

:[[File:Lattice of the divisibility of 60.svg|none|300px]]

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

:[[File:Lattice of partitions of an order 4 set.svg|none|300px]]

== 一个“良好”的哈斯圖 ==

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

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

:{| style="background:transparent"
| [[File:Hypercubeorder.svg|215px|]] ||   || [[File:Hypercubecubes.svg|315px|]] ||   || [[File:Hypercubestar.svg|229px|]]
|}

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

==註釋==
{{reflist|2}}

==引用==
{{refbegin|2}}
*{{citation|first1=K. A.|last1=Baker|first2=P.|last2=Fishburn|author2-link=Peter C. Fishburn|first3=F. S.|last3=Roberts|author3-link=Fred S. Roberts|title=Partial orders of dimension 2|journal=Networks|volume=2|pages=11–28|issue=1|doi=10.1002/net.3230020103|year=1971}}.
*{{citation|last1=Bertolazzi|first1=R|last2=Di Battista|first2=G.|last3=Mannino|first3=C.|last4=Tamassia|first4=R.|author4-link=Roberto Tamassia|year=1993|contribution=Optimal upward planarity testing of single-source digraphs|title=[[European Symposium on Algorithms|Proc. 1st European Symposium on Algorithms (ESA '93)]]|volume=726|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|pages=37-48|doi=10.1007/3-540-57273-2_42}}.
*{{citation|first=Garrett|last=Birkhoff|authorlink=Garrett Birkhoff|title=Lattice Theory|edition=Revised|publisher=[[American Mathematical Society]]|year=1948}}.
*{{citation|first=Hubert|last=Chan|contribution=A parameterized algorithm for upward planarity testing|title=Proc. 12th European Symposium on Algorithms (ESA '04)|year=2004|volume=3221|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|pages=157–168|url=http://www.springerlink.com/content/pbxglecx113c6axl/}}{{Dead link|date=2020年2月 |bot=InternetArchiveBot |fix-attempted=yes }}.
*{{citation|first1=G.|last1=Di Battista|first2=R.|last2=Tamassia|author2-link=Roberto Tamassia|title=Algorithms for plane representation of acyclic digraphs|journal=Theoretical Computer Science|volume=61|year=1988|pages=175–178|doi=10.1016/0304-3975(88)90123-5}}.
*{{citation|first=Ralph|last=Freese|contribution=Automated lattice drawing|title=Concept Lattices|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=2961|pages=589–590|year=2004}}. An extended preprint is available online: [http://www.math.hawaii.edu/~ralph/Preprints/latdrawing.pdf]{{Webarchive|url=http://arquivo.pt/wayback/20160314184411/http://www.math.hawaii.edu/~ralph/Preprints/latdrawing.pdf |date=2016-03-14 }}.
*{{citation|first1=Ashim|last1=Garg|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|title=Upward planarity testing|journal=Order|volume=12|pages=109–133|year=1995a|doi=10.1007/BF01108622|issue=2}}.
*{{citation|first1=Ashim|last1=Garg|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|year=1995b|contribution=On the computational complexity of upward and rectilinear planarity testing|title=[[International Symposium on Graph Drawing|Graph Drawing (Proc. GD '94)]]|volume=894|series=LectureNotes in Computer Science|publisher=Springer-Verlag|pages=286–297|doi=10.1007/3-540-58950-3_384}}.
*{{citation|first1=Michael|last1=Jünger|first2=Sebastian|last2=Leipert|contribution=Level planar embedding in linear time|title=[[International Symposium on Graph Drawing|Graph Drawing (Proc. GD '99)]]|year=1999|pages=72–81|doi=10.1007/3-540-46648-7_7}}.
*{{citation|first=Henri Gustav|last=Vogt|publisher=Nony|year=1895|page=91|title=Leçons sur la résolution algébrique des équations}}.
{{refend}}

==外部連結==
{{Commons category|Hasse diagrams}}
*[https://web.archive.org/web/20090417023642/http://www.win.tue.nl/ida/demo/c1s1ja.html Hasse diagrams of divisors]
*[http://www.math.northwestern.edu/~mlerma/courses/cs310-04w/notes/dm-relations.pdf How to draw hasse diagrams of binary relations]{{Wayback|url=http://www.math.northwestern.edu/~mlerma/courses/cs310-04w/notes/dm-relations.pdf |date=20090912101209 }}
*[http://mathworld.wolfram.com/HasseDiagram.html "Hasse Diagram" on MathWorld]{{Wayback|url=http://mathworld.wolfram.com/HasseDiagram.html |date=20181024135457 }}

[[Category:序理論]]
[[Category:圖表]]