4.4 偏序与哈斯图

等价关系用对称性把同类元素聚成组。许多系统需要另一种结构：一项任务必须先于另一项任务完成，一个集合包含于另一个集合，或者一个数整除另一个数。

这些连接具有方向，但并不要求任意两个元素都能比较。一个项目中可以有两项互不依赖的任务；两个集合也可能各自含有对方没有的元素。描述这种结构需要偏序。

偏序组合三种熟悉性质

集合 $A$ 上的关系 $\preceq$ 称为偏序，如果它同时满足：

1. 自反：对每个 $a\in A$，都有 $a\preceq a$；

2. 反对称：$a\preceq b$ 且 $b\preceq a$ 会推出 $a=b$；

3. 传递：$a\preceq b$ 且 $b\preceq c$ 会推出 $a\preceq c$。

二元组

称为偏序集。

符号 $\preceq$ 是通用的次序符号。具体偏序可以使用 $\le$、$\subseteq$、整除符号 $\mid$，也可以用任务依赖关系表示。

比较等价关系与偏序的公式：

对称性允许不同但等价的元素双向连接。反对称性则表示：如果次序可以双向成立，这两个元素必须其实是同一个元素。

三个核心例子

数值次序

整数上的普通 $\le$ 是偏序：

• $a\le a$；

• $a\le b$ 且 $b\le a$ 会推出 $a=b$；

• $a\le b$ 且 $b\le c$ 会推出 $a\le c$。

任意两个整数在 $\le$ 下都可以比较，所以它还是一种特殊偏序，称为全序。

集合包含

在幂集 $\mathcal P(S)$ 上，$\subseteq$ 是偏序：

以及

但并非每一对集合都可比较。例如

此时 $X\not\subseteq Y$ 且 $Y\not\subseteq X$。

整除次序

在某个固定正整数的所有正因数上，定义

它自反，因为 $a=a\cdot1$；它在正整数上反对称；它还传递，因为

表示 $b=ak$ 且 $c=b\ell$，于是

从而 $a\mid c$。

可比与不可比

在偏序集 $(A,\preceq)$ 中，若

就称元素 $a,b$ 可比。

若两个命题都不成立，则称它们不可比。

不可比并不表示关系损坏。正是因为允许不可比，偏序才与全序不同。

设想一组软件任务：

• schema 必须先于 API 完成；

• API 必须先于 dashboard 完成；

• icons 必须先于 dashboard 完成。

由传递性，schema 先于 dashboard。但 schema 与 icons 可能不可比：双方互不依赖，可以并行进行。

还需要区分非严格次序 $\preceq$ 与对应的严格次序 $\prec$：

非严格关系包含元素与自身的关系，严格关系则不包含。

通过连接前置任务来安排一次产品发布。模拟器会传播间接依赖，标记违反反对称性的循环，并把互不依赖的任务放入并行通道。你需要修复一个可执行的次序，而不是简单把标签排成一列。

为什么哈斯图不是完整关系图

有限偏序可以画成有向图，但完整图会包含许多冗余信息：

• 自反性使每个顶点都有自环；

• 传递性为每个间接比较加入一条边；

• 所有箭头都朝同一个向上的次序方向。

哈斯图会删除这些冗余信息。

对有限偏序 $(A,\preceq)$：

1. 删除所有自环 $a\preceq a$；

2. 删除所有能由更长传递路径推出的边；

3. 把较小元素放在下方，较大元素放在上方；

4. 省略箭头，因为向上的方向已经表达次序。

剩下的边表示覆盖关系。如果

且不存在 $c$ 使

就称 $b$ 覆盖 $a$。

换句话说，$b$ 紧邻在 $a$ 上方，偏序集中没有中间元素夹在二者之间。

完整例子：$12$ 的因数上的整除

令

并用整除关系排序。

完整关系包含

等许多有序对。

但是从 $1$ 到 $4$ 的边可以由

传递得到，所以它是冗余边。同理，$1$ 到 $12$、$2$ 到 $12$、$3$ 到 $12$ 都能经过中间因数推出。

覆盖有序对为

哈斯图的文字布局如下：

          12
         /  \
        4    6
        |   / \
        2  /   3
         \/
          1

这幅图是示意布局：每条向上线段表示一次覆盖，多条向上线段组成的路径记录被传递约简删除的比较。

最小、最大、极小与极大

这四个术语看起来相近，但表达的命题不同。

元素 $\ell$ 称为最小元，如果

它位于每个元素下方。最小元如果存在，就一定唯一。

元素 $g$ 称为最大元，如果

它位于每个元素上方，并且如果存在也一定唯一。

元素 $m$ 称为极小元，如果没有不同元素严格位于它下方：

元素 $M$ 称为极大元，如果没有不同元素严格位于它上方：

一个偏序集可以有多个极小元或极大元，因为这些元素可能彼此不可比；但它至多有一个最小元和一个最大元。

在 $D$ 的整除偏序中，$1$ 是最小元，$12$ 是最大元。因此它们也分别是唯一的极小元与极大元。

再考虑

$\{a\}$ 与 $\{b\}$ 都是极小元，但二者都不是最小元，因为它们互不包含。集合 $\{a,b\}$ 是最大元，也是极大元。

阅读哈斯图时，可以这样检查：

• 极小表示“这个节点严格下方没有节点”；

• 最小表示“从这个节点向上能到达所有其他节点”；

• 极大表示“这个节点严格上方没有节点”；

• 最大表示“所有其他节点向上都能到达这个节点”。

从一张边数过多的整除网络中雕刻哈斯图。删除自环和传递边，同时保证每个比较仍能通过向上路径恢复，并识别极值元素。第二组子集挑战会展示为什么多个极小元并不构成最小元。

本章衔接

第 4 章从有序对建立了多种结构。函数要求每个输入恰好一个输出；一般关系允许任意连接；等价关系生成划分；偏序则表达层级，同时不强迫每对元素都可比较。

第 5 章将从结构转向过程。我们会描述把输入转化为输出的算法，证明算法步骤正确，并比较算法所需资源如何增长。