哈斯图
哈斯图（英语：Hasse 发音为/ˈhæsə/, 德语: /ˈhasə/）、在数学分支序理论中，是用来表示有限偏序集的一种数学图表，它是一种图形形式的对偏序集的传递简约。具体的说，对于偏序集合(S, ≤)，把S的每个元素表示为平面上的顶点，然后若元素y覆盖x（就是说，x < y并且没有z使得 x < z < y），则绘制从x到y向上的线段或弧线。这些弧线可以相互交叉但不能触及任何非其端点的顶点。带有标注的顶点的这种图唯一确定这个集合的偏序。
哈斯图得名于德国数学家赫尔穆特·哈斯；依据Birkhoff (1948)，这么叫是因为哈斯有效的利用了它们。但是哈斯不是第一个使用它们的人，它们早就出现在如Vogt (1895)中。尽管哈斯图被设计为手工绘制偏序集合的技术，最近已经使用图绘制技术自动来生成它们了。[1]
术语“哈斯图”还可以称呼作为抽象有向无环图的传递简约，独立于这个图的任何绘制形式，但是这里不采用这种用法。
例子
[编辑]
- 集合{ 1, 2, 3, 4 }的所有15个划分，按精细度（就是更细划分小于更粗划分）排序，有哈斯图:
一个“良好”的哈斯图
[编辑]尽管哈斯图是简单的处理有限偏序集的直观工具，绘制出好的哈斯图是非常困难的。原因是对于给定偏序集有任意多种可能的绘图方式。简单的技术就是开始于这个次序的最小元并逐步增加上更大的元素，这经常产生非常窘迫的结果：很容易丢失了这个次序的对称性和内部结构。
下面的例子展示这个问题。考虑集合S = {a, b, c, d}的幂集，就是说S的所有自己的集合，按照子集包含来排序。下面是这个偏序的三个不同哈斯图:
通过使得在这个幂集中每个集合的y坐标成比例于集合的势，最左图示展示了这个幂集是等级偏序集。中间图示有相同的等级结构，但使得某些边比其他边长，它把这个幂集的结构强调为两个三维立方体的联合：在两个立方体中下面的那个中的顶点表示不包含S的某个特定元素比如d的集合，而上面立方体的顶点表示包含d的集合。最右图示展示了这个结构的某种内部对称性。
注释
[编辑]- ^ E.g., see Di Battista & Tamassia (1988) and Freese (2004).
引用
[编辑]- 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.
