aiwiki.page
中文
数学 / 离散数学与逻辑 / hasse-diagram

哈斯图

哈斯图仅绘出偏序集中的覆盖关系,并将较大元素置于较小元素上方,以此表示偏序结构。

17 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
偏序组合数学抽象代数二元关系幂集子集空集布尔代数哈斯图

哈斯图是偏序集的一种图形表示:以顶点表示元素,以向上的连线表示直接的序关系。由传递性可推得的关系不予画出,每个元素与自身之间的自反关系也予以省略。对于有限偏序集,沿图中向上的路径即可还原完整的序关系。哈斯图以德国数学家赫尔穆特·哈斯的名字命名,广泛应用于序理论、组合数学和抽象代数。

定义

偏序集由集合 PP 及其上的一个满足自反性、反对称性和传递性的二元关系 ≤\leq 构成。当 x≤yx\leq y 且 x≠yx\neq y 时,记作 x<yx<y。

若满足

x<yand there is no z∈P such that x<z<y.x<y \quad\text{and there is no }z\in P\text{ such that }x<z<y.

则称元素 yy 覆盖元素 xx,记作 x⋖yx\lessdot y。

因此,覆盖表示序关系中直接相邻的一步,不一定表示数值大小上相邻的一步。

绘制哈斯图时遵循三项约定:

  • 用一个顶点表示 PP 中的每个元素。
  • 当且仅当 yy 覆盖 xx 时,在 xx 与 yy 之间画一条连线。
  • 如果 yy 覆盖 xx,则将 yy 置于 xx 上方。

连线通常采用直线段,也可以采用向上的曲线。由于向上的方向已经表示序关系的增大,因此不必添加箭头。

对于有限偏序集,

x≤y⟺x=y or there is an upward path from x to y.x\leq y \quad\Longleftrightarrow\quad x=y\text{ or there is an upward path from }x\text{ to }y.

这里的“向上”至关重要:一条交替向上、向下行进的路径,并不能说明其两个端点之间存在序关系。

如何读图

顶点的竖直位置用于体现绘图约定,但仅凭高度并不能判断元素是否可比。一个顶点可能位于另一个顶点上方,却没有向上的路径连接两者。

从有限哈斯图中可以读出若干重要的序理论特征:

  • 极小元是指没有任何元素严格小于它的元素;它没有向下的覆盖连线。
  • 极大元是指没有任何元素严格大于它的元素;它没有向上的覆盖连线。
  • 最小元小于或等于所有元素。
  • 最大元大于或等于所有元素。

极小元与最小元不可混为一谈。一个偏序集可以有多个极小元,但至多只有一个最小元。极大元与最大元也有相应的区别。

链是其中元素两两可比的子集。反链是其中不同元素两两不可比的子集。在通常的向上绘图约定下,同一水平线上的顶点必然不可比,但反链不一定要画在同一水平线上。

除非在交叉处明确标出顶点,否则线条相交并不表示那里存在额外的元素或连接。

示例

有限全序

对于按通常数值大小排序的集合 {1,2,3,4}\{1,2,3,4\},其哈斯图是一条竖直的链:

4
|
3
|
2
|
1

只有相邻元素之间才有连线。虽然 1<31<3 且 1<41<4,但这些关系已可由向上的路径推得,因此不另画边。

按包含关系排序的子集

考虑 {a,b}\{a,b\} 的幂集,按子集包含关系排序:

    {a,b}
     / \
   {a} {b}
     \ /
      ∅

最下方的顶点是空集,最上方的顶点是 {a,b}\{a,b\}。集合 {a}\{a\} 与 {b}\{b\} 不可比。

更一般地,对于有限集的各个子集,当且仅当 BB 是由 AA 添加一个元素得到时,BB 覆盖 AA。因此,可以自然地按照子集的基数将它们分层排列。这一序结构构成一个有限布尔代数。

整除关系

设

P={1,2,3,6,12},P=\{1,2,3,6,12\},

并定义 a≤ba\leq b 表示 aa 整除 bb。其覆盖关系为

1⋖2,1⋖3,2⋖6,3⋖6,6⋖12.1\lessdot2,\qquad 1\lessdot3,\qquad 2\lessdot6,\qquad 3\lessdot6,\qquad 6\lessdot12.

这里,尽管按通常的数值大小有 2<32<3,但 22 与 33 在该偏序中不可比。图中表示的是整除关系,而不是数值大小关系。

覆盖关系还取决于所考虑的集合。在这个 PP 中,1212 覆盖 66。而在较小的整除偏序集 {1,12}\{1,12\} 中,1212 覆盖 11,因为该偏序集中没有介于两者之间的元素。

与有向图的联系

将每条连线都定向为向上,就得到一个有向无环图。如果存在有向环,就会与沿每条边都必须严格增大的要求矛盾。

对于有限偏序集,对每个严格关系 x<yx<y 都添加一条边 x→yx\to y,可得到一个有向图;有向覆盖图就是这个图的传递约简。传递约简会删除那些可达性已由更长的有向路径保证的边。对于有限有向无环图,传递约简是唯一的。

反过来,任何有限有向无环图都可以通过可达关系加上相等关系来定义一个偏序。不过,只有去除冗余边,并按照与该偏序一致的方式排列顶点后,这个图才是哈斯图。

仅凭底层无向图,通常无法确定偏序集。向上的定向也是哈斯图所传达的信息的一部分。

格与代数应用

格是一种偏序集,其中每一对元素 x,yx,y 都有最大下界,称为它们的交 x∧yx\wedge y,也都有最小上界,称为它们的并 x∨yx\vee y。

在哈斯图中,两个元素的公共上界,就是从这两个元素出发沿向上路径都能到达的顶点。如果它们的并存在,那么它就是这些公共上界中的最小元。交则利用公共下界对偶地定义。这些都是序理论性质,并不是对图中几何距离的度量。

对于上述子集示例,

A∧B=A∩B,A∨B=A∪B.A\wedge B=A\cap B, \qquad A\vee B=A\cup B.

对于一个固定正整数的所有正因子,若按整除关系排序,则交是最大公约数,并是最小公倍数。

其他重要用途还包括表示群论中的子群包含关系、环(数学)理论中的理想包含关系,以及集合划分之间的细化关系。这类图能够揭示中间结构,以及特定元素之间是否可比。

构造与布局

对于完整序关系已知的有限偏序集,一种直接的构造方法是检查每一对满足 x<yx<y 的元素。只有不存在满足

x<z<y.x<z<y.

的 zz 时,才将这一对元素保留为一条边。

若单次序关系判断耗时为常数,则对于 nn 个元素,直接实现这一方法的时间复杂度为 O(n3)O(n^3)。其他方法可以利用图的结构,或利用序关系的更紧凑表示。

确定覆盖关系后,布局时必须将每条边的上端点放在下端点的上方。不同的图形可以表示完全相同的偏序集:水平位置、边长和角度通常都不属于数学数据。

某些偏序集具有秩函数,沿每个覆盖关系,秩都增加一,因此可以将顶点自然地排列在不同的水平层上。并非每个有限偏序集都具有这样的秩函数。不过,任何有限偏序集都可以画成所有覆盖边均朝上的图。

避免边相交是另一个问题。哈斯图可能无法避免交叉,而且即使其底层无向图是平面图,也不一定能画出既无交叉、又符合向上序关系的图。

无限偏序集与局限

无限偏序集也存在覆盖关系,但覆盖关系不一定能确定完整的序关系。

例如,按通常大小排序的整数构成一条无限链,其中 n+1n+1 覆盖 nn。每个严格大小关系仍可用有限次覆盖步骤表示。

相比之下,按通常大小排序的有理数没有任何覆盖关系:只要 x<yx<y,就总有另一个有理数严格位于两者之间。因此,尽管这是一个全序,只画覆盖关系的图却不会包含任何边。

所以,利用有限向上路径还原序关系的常用规则,对有限偏序集总是成立,但在无限情形下需要附加条件。例如,当每个区间

[x,y]={z∈P:x≤z≤y}[x,y]=\{z\in P:x\leq z\leq y\}

都是有限集时,这一规则就成立。

即使对于有限偏序,规模较大的图也可能难以解读。哈斯图能够有效地表示直接的序结构,但其实用程度取决于规模、标注和布局。