Hasse 图

哈斯图
术语名称	哈斯图
英语名称	Hasse diagram

哈斯图(Hasse diagram)是用于可视化偏序集结构的图表。 通过省略自反边和传递边，将剩余的覆盖关系，将相邻的大小元素从上向下排列并相连。

图表

对偏序集 [math]\displaystyle{ (P, \preceq) }[/math] ，记有向图 [math]\displaystyle{ (P, E) }[/math] 。

• 顶点集 [math]\displaystyle{ P }[/math] 是偏序集中的所有元素。
• 图中的有向边是所有有“覆盖”关系的两个元素构成的边。
  • 定义严格偏序关系： [math]\displaystyle{ x \prec y }[/math] 当且仅当 [math]\displaystyle{ x \preceq y \land x \neq y }[/math] 。
  • 定义“覆盖”关系： [math]\displaystyle{ (x,y)\in E }[/math] 称为 [math]\displaystyle{ y }[/math] 覆盖(cover) [math]\displaystyle{ x }[/math] ，当且仅当 [math]\displaystyle{ x \prec y \land (\lnot\exists z)(x \prec z \land z \prec y) }[/math]

Hasse 图(Hasse diagram)即为这张有向图以固定绘制方法构成的图表。 在绘制哈斯图时，通常将较大的元素置于上方，较小的元素置于下方，边的方向通过由下至上的位置关系暗示，因此尽管是有向图，通常不绘制箭头。

绘制规则

绘制哈斯图时通常遵循以下规则：

1. 若 [math]\displaystyle{ y }[/math] 覆盖 [math]\displaystyle{ x }[/math]，则将 [math]\displaystyle{ y }[/math] 置于 [math]\displaystyle{ x }[/math] 上方。
2. 边通常绘制为直线段，不画箭头（方向通过由下至上的位置关系暗示）。
3. 同一层次（高度）的元素尽量水平对齐。

性质

• 和偏序的关系
  • Hasse 图是省略了自反和传递可构造的边，因此原偏序关系可以通过 Hasse 图中覆盖关系的自反传递闭包恢复。
  • 两个不同的元素可比当且仅当在 Hasse 图中存在一条连接它们的路径。
• 图论性质
  • Hasse 图是有向无环图。
  • Hasse 图可能有多个连通分量，多个连通分量间任意元素两两不可比，对应偏序集中的连通分量。
• 特殊 Hasse 图
  • 全序集的 Hasse 图中所有边构成一条经过全部顶点的有向路径。

举例

• 集合 [math]\displaystyle{ \{1,2,3\} }[/math] 的幂集在包含关系下的 Hasse 图是一个立方体的投影

[math]\displaystyle{ \begin{array}{ccccc} && \{1,2,3\} && \\ & \diagup & | & \diagdown & \\ \{1,2\} && \{2,3\} && \{3,1\} \\ | & \times & | & \times & | \\ \{2\} & & \{1\} & & \{3\} \\ & \diagdown & | & \diagup & \\ && \varnothing && \\ \end{array} }[/math]

• 整数 12 及其正因子在整除关系下的哈斯图

[math]\displaystyle{ \begin{array}{ccc} & 12 & \\ \diagup && \diagdown \\ 4 && 6 \\ | & \diagup & | \\ 2 && 3 \\ \diagdown && \diagup \\ & 1 & \\ \end{array} }[/math]

• 小于 10 的正整数在整除关系下的哈斯图

[math]\displaystyle{ \begin{array}{ccccc} 8 && \\ | && \\ 4 && 6 && 9 \\ | & \diagup & | & \diagup && \\ 2 && 3 && 5 & 7 \\ & \diagdown & | & \diagup & \diagup && \\ && 1 &&&& \\ \end{array} }[/math]

序理论
预序、预序集	极大元、极小元	最大元、最小元
	上界、下界	上确界、下确界
方向、有向集	半格（并半格、交半格）	有界半格（有界并半格、有界交半格）
	格	有界格
偏序、偏序集	Hasse 图
	链、长度、高度	反链、宽度
	Dilworth 定理	Mirsky 定理