跳转到内容

哈斯图

维基百科,自由的百科全书

哈斯图英语:Hasse 发音为/ˈhæsə/, 德语: /ˈhasə/)、在数学分支序理论中,是用来表示有限偏序集的一种数学图表,它是一种图形形式的对偏序集的传递简约。具体的说,对于偏序集合(S, ≤),把S的每个元素表示为平面上的顶点,然后若元素y覆盖x(就是说,x < y并且没有z使得 x < z < y),则绘制从xy向上的线段或弧线。这些弧线可以相互交叉但不能触及任何非其端点的顶点。带有标注的顶点的这种图唯一确定这个集合的偏序。

哈斯图得名于德国数学家赫尔穆特·哈斯;依据Birkhoff (1948),这么叫是因为哈斯有效的利用了它们。但是哈斯不是第一个使用它们的人,它们早就出现在如Vogt (1895)中。尽管哈斯图被设计为手工绘制偏序集合的技术,最近已经使用图绘制技术自动来生成它们了。[1]

术语“哈斯图”还可以称呼作为抽象有向无环图的传递简约,独立于这个图的任何绘制形式,但是这里不采用这种用法。

例子

  • 所有60的除数的集合A = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 },按整除性排序,有哈斯图:
  • 集合{ 1, 2, 3, 4 }的所有15个划分,按精细度(就是更细划分小于更粗划分)排序,有哈斯图:

一个“良好”的哈斯图

尽管哈斯图是简单的处理有限偏序集的直观工具,绘制出好的哈斯图是非常困难的。原因是对于给定偏序集有任意多种可能的绘图方式。简单的技术就是开始于这个次序的最小元并逐步增加上更大的元素,这经常产生非常窘迫的结果:很容易丢失了这个次序的对称性和内部结构。

下面的例子展示这个问题。考虑集合S = {a, b, c, d}的幂集,就是说S的所有自己的集合,按照子集包含来排序。下面是这个偏序的三个不同哈斯图:

       

通过使得在这个幂集中每个集合的y坐标成比例于集合的,最左图示展示了这个幂集是等级偏序集。中间图示有相同的等级结构,但使得某些边比其他边长,它把这个幂集的结构强调为两个三维立方体的联合:在两个立方体中下面的那个中的顶点表示不包含S的某个特定元素比如d的集合,而上面立方体的顶点表示包含d的集合。最右图示展示了这个结构的某种内部对称性。

注释

引用

外部链接