本节对应原书 PDF 第 119–127 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

前面几节已经讨论了关系的运算以及性质，这里主要介绍两种具有良好性质的关系——等价关系和偏序关系，它们在实际中都有着广泛的应用.

4.4.1 等价关系

定义 4.18 设 R 是集合 A 上的关系，如果 R 是自反的、对称的、传递的，则称 R 为 A 上的等价关系. 对于任何元素 x, y \in A，如果 xRy，则称 x 与 y 等价，记作 x \sim y.

A 上的恒等关系 I_A、全域关系 E_A 是等价关系，而整数集合 \mathbf{Z} 上的小于等于关系不是等价关系，因为它不是对称的. 在整数集合或者它的子集上有一种重要的等价关系，就是模 n 同余关系 \equiv，这个关系将在第 11 章给予详细的介绍. 对于任意整数 x 和 y，x \equiv y \pmod n 的含义是 x 与 y 除以 n 的余数相等.

解读：等价关系把「自反 + 对称 + 传递」三条一次要齐。少任何一条都会破坏后面的等价类理论：缺自反则元素进不了自己的类，缺对称则「等价」不可逆，缺传递则类的划分会互相粘连。

例 4.17 设 A = \{1, 2, 3, 4, 5, 6, 7\}，那么 A 上的模 3 等价关系

R = \{\langle 1, 4 \rangle, \langle 1, 7 \rangle, \langle 4, 1 \rangle, \langle 4, 7 \rangle, \langle 7, 1 \rangle, \langle 7, 4 \rangle, \langle 2, 5 \rangle, \langle 5, 2 \rangle, \langle 3, 6 \rangle, \langle 6, 3 \rangle\} \cup I_A

R 的关系图如图 4.6 所示.

原书图4.6 模 3 等价关系的关系图

4.4.2 等价类和商集

由于等价关系的存在，将集合 A 的元素划分成若干个子集，彼此等价的元素被分在同一个子集里. 上面例子的 1,4,7 除以 3 的余数都是 1，它们在同一个子集里；2 和 5 除以 3 的余数都是 2，它们也在同一个子集里；最后一个子集就是由 3 和 6 构成的子集. 这些子集称作这个等价关系产生的等价类.

定义 4.19 设 R 为集合 A 上的等价关系，x 为 A 上的元素，A 中与 x 等价的全体元素构成的子集称为 x 的等价类，记作 [x]_R. 在不会混淆的情况下，可以简记为 [x]，即

[x] = \{y \mid y \in A, xRy\}

例 4.17 中的等价类是

[1] = [4] = [7] = \{1, 4, 7\}
[2] = [5] = \{2, 5\}
[3] = [6] = \{3, 6\}

下面的定理给出了等价类的性质.

定理 4.8 设 R 是非空集合 A 上的等价关系，则

（1）\forall x \in A，[x] 是 A 的非空子集.

（2）\forall x, y \in A，如果 xRy，则 [x] = [y].

（3）\forall x, y \in A，如果 x\overline{R}y，则 [x] 与 [y] 不交.

（4）\bigcup_{x \in A} [x] = A①.

证明 （1）由等价类定义可知，\forall x \in A 有 [x] \subseteq A. 由自反性有 xRx，因此 x \in [x]，即 [x] 非空.

（2）任取 z，则有

z \in [x] \Rightarrow \langle x, z \rangle \in R \Rightarrow \langle z, x \rangle \in R
\langle z, x \rangle \in R \wedge \langle x, y \rangle \in R \Rightarrow \langle z, y \rangle \in R \Rightarrow \langle y, z \rangle \in R

从而证明了 z \in [y]. 综上所述必有 [x] \subseteq [y]. 同理可证 [y] \subseteq [x]. 这就得到了 [x] = [y].

（3）假设 [x] \cap [y] \neq \varnothing，则存在 z \in [x] \cap [y]，从而有 z \in [x] \wedge z \in [y]，即 \langle x, z \rangle \in R \wedge \langle y, z \rangle \in R 成立. 根据 R 的对称性和传递性必有 \langle x, y \rangle \in R，与 x\overline{R}y 矛盾.

（4）先证 \bigcup_{x \in A} [x] \subseteq A. 任取 y，

y \in \bigcup_{x \in A} [x] \Leftrightarrow \exists x(x \in A \wedge y \in [x]) \Rightarrow y \in [x] \wedge [x] \subseteq A \Rightarrow y \in A

从而有 \bigcup_{x \in A} [x] \subseteq A. 再证 A \subseteq \bigcup_{x \in A} [x]. 任取 y，

y \in A \Rightarrow y \in [y] \wedge y \in A \Rightarrow y \in \bigcup_{x \in A} [x]

从而有 A \subseteq \bigcup_{x \in A} [x] 成立. 综上所述得 \bigcup_{x \in A} [x] = A.

① \bigcup_{x \in A} [x] 表示 A 中元素构成的所有等价类的并集.

定义 4.20 A 上的全体等价类构成的集合称作 A 关于等价关系 R 的商集，记作 A/R，即

A/R = \{[x]_R \mid x \in A\}

例 4.17 的商集是

A/R = \{\{1, 4, 7\}, \{2, 5\}, \{3, 6\}\}

如果 A 上的等价关系是恒等关系或全域关系，那么对应的商集是

A/I_A = \{\{1\}, \{2\}, \{3\}, \cdots, \{7\}\}
A/E_A = \{\{1, 2, \cdots, 7\}\}

解读：定理 4.8 的四条合起来说的是一件事：等价类把 A 恰好切成若干互不相交的非空块，既不遗漏也不重叠。注意第 (3) 条用的是 x\overline{R}y（x 与 y 不等价），此时两类不相交。

例 4.18 设 R 是整数集 \mathbf{Z} 上的模 n 的等价关系，那么根据除以 n 的余数分别为 0, 1, 2, \cdots, n-1，将整数集合划分成 n 个等价类，即

[0] = \{nk \mid k \in \mathbf{Z}\}
[1] = \{nk + 1 \mid k \in \mathbf{Z}\}
\vdots
[n-1] = \{nk + n - 1 \mid k \in \mathbf{Z}\}

所有等价类的集合构成的商集是

\mathbf{Z}/R = \{[0], [1], \cdots, [n-1]\}

4.4.3 集合的划分

下面讨论集合的划分.

定义 4.21 设 A 为非空集合，若 A 的子集族 \pi（\pi \subseteq P(A)）满足下面条件：

（1）\varnothing \notin \pi.

（2）\forall x \forall y(x, y \in \pi \wedge x \neq y \rightarrow x \cap y = \varnothing).

（3）\bigcup_{x \in \pi} x = A①.

则称 \pi 是 A 的一个划分，称 \pi 中的元素为 A 的划分块.

日常生活中经常遇到划分的例子. 在切蛋糕时就是对蛋糕进行划分，切出的每个块不是空块，两个不同的切块没有公共部分，所有切块合到一起就是原来的蛋糕.

① \bigcup_{x \in \pi} x 表示划分 \pi 中的所有划分块的并集.

例 4.19 设 A = \{a, b, c, d\}，给定 \pi_1，\pi_2，\pi_3，\pi_4，\pi_5，\pi_6 如下：

\pi_1 = \{\{a, b, c\}, \{d\}\}
\pi_2 = \{\{a, b\}, \{c\}, \{d\}\}
\pi_3 = \{\{a\}, \{a, b, c, d\}\}
\pi_4 = \{\{a, b\}, \{c\}\}
\pi_5 = \{\varnothing, \{a, b\}, \{c, d\}\}
\pi_6 = \{\{a, \{a\}\}, \{b, c, d\}\}

则 \pi_1 和 \pi_2 是 A 的划分，其他都不是 A 的划分. 因为 \pi_3 中的两个划分块相交；\pi_4 中的划分块的并集不等于 A；\pi_5 中含有空块；\pi_6 根本不是 A 的子集族.

根据定理 4.8，等价类是 A 的非空子集，因此商集 A/R 是 A 的集合族，且满足：每个等价类不是空集，不同的等价类之间不相交，所有等价类的并集就是集合 A. 根据划分的定义，商集 A/R 就是 A 的划分，称为由等价关系 R 导出的划分.

反过来，给定集合 A 的划分 \pi，也可以根据如下规则导出 A 上的一个等价关系 R：

xRy \text{ 当且仅当 } x \text{ 与 } y \text{ 在 } \pi \text{ 的同一个划分块中}

不难验证这个关系具有自反性、对称性和传递性. 如果划分 \pi 含有 k 个划分块，即

\pi = \{A_1, A_2, \cdots, A_k\}

可以证明 \pi 导出的等价关系满足

R = (A_1 \times A_1) \cup (A_2 \times A_2) \cup \cdots \cup (A_k \times A_k)

并且 R 导出的划分就是 \pi.

通过上面的分析可以知道，集合 A 上的等价关系 R 与 A 的划分可以建立一一对应. A 上有多少个不同的等价关系，A 就有多少个不同的划分. 对于 n 元集合 A，A 上的等价关系个数是第二类斯特林数（Stirling）的和，相关的结果将在第 10 章给出.

解读：「等价关系 ↔ 划分」是本节最有价值的一句话：数等价关系就是数划分，反之亦然。所以后面数 \{1,2,3\} 上的等价关系，只要把它所有的划分画出来即可，不必逐个验证三条性质。

例 4.20 给出 A = \{1, 2, 3\} 上所有的等价关系.

解 如图 4.7 所示，先做出 A 的所有划分，从左到右分别记作 \pi_1，\pi_2，\pi_3，\pi_4，\pi_5. 这些划分与 A 上的等价关系之间的一一对应是：\pi_4 对应于全域关系 E_A，\pi_5 对应于恒等关系 I_A，\pi_1，\pi_2 和 \pi_3 分别对应于等价关系 R_1，R_2 和 R_3. 其中

R_1 = \{\langle 2, 3 \rangle, \langle 3, 2 \rangle\} \cup I_A
R_2 = \{\langle 1, 3 \rangle, \langle 3, 1 \rangle\} \cup I_A
R_3 = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle\} \cup I_A

原书图4.7 A = {1,2,3} 的所有划分

4.4.4 偏序关系

集合 A 上的另一种重要的关系是偏序关系，也称为部分序关系，顾名思义就是 A 上部分元素之间的顺序关系. 这种关系在实际应用中广泛存在. 比如，通常的数之间的大于等于关系，集合之间的包含关系等都是偏序关系. 下面给出偏序关系的定义.

定义 4.22 非空集合 A 上的自反、反对称和传递的关系称为 A 上的偏序关系，简称偏序，记作 \preccurlyeq.

例如实数集合上的大于等于关系、正整数集合上的整除关系、集合 A 上的恒等关系、集合 B 的幂集 P(B) 上的包含关系等都是偏序关系.

设 \preccurlyeq 为集合 A 上的偏序关系，如果 \langle x, y \rangle \in \preccurlyeq，记作 x \preccurlyeq y，读作「x 小于或等于 y」. 这里的「小于等于」表示的是在偏序中的先后顺序，不是指通常的数的大小. 针对不同的偏序，对于这个「小于等于」可以给出不同的解释. 例如偏序 \preccurlyeq 代表正整数集合上的整除关系，那么 x \preccurlyeq y 表示 x 整除 y，或者说 y 被 x 整除. 根据这个解释，可以写 2 \preccurlyeq 4，5 \preccurlyeq 5，\cdots. 如果 \preccurlyeq 代表实数集合上的大于等于关系，那么不能写 2 \preccurlyeq 4，只能写 4 \preccurlyeq 2. 尽管这里读成「4 小于等于 2」，只是意味着在大于等于的序上，4 排在 2 的前面，实际上的含义是 4 大于等于 2.

定义 4.23 设 R 为非空集合 A 上的偏序关系，\forall x, y \in A，如果 x \preccurlyeq y \vee y \preccurlyeq x，则称 x 与 y 可比.

例如，在正整数集合上的小于等于关系中，任何两个正整数 x 和 y 都是可比的. 而对于整除关系，在任何两个正整数中，不能保证一个整除另一个，例如 2 不能整除 3，3 也不能整除 2. 在整除关系中 2 和 3 是不可比的.

和偏序关系有着密切联系的关系是拟序关系 \prec，它和对应的偏序关系的区别在于自反性.

定义 4.24 设 R 为非空集合 A 上的关系，如果 R 是反自反的和传递的，则称 R 是 A 上的拟序关系，简称为拟序，记作 \prec.

不难证明，如果一个关系是拟序关系，那么这个关系一定是反对称的. 因为如果存在 x, y 使得 x \prec y 且 y \prec x 成立，则根据传递性，必有 x \prec x 成立，而这与反自反性矛盾.

从上面的分析可以知道偏序关系是自反的、反对称的、传递的，而拟序关系是反自反的、反对称的、传递的. 对于集合 A 上给定的偏序关系 R，R - I_A 是 A 上的拟序关系. 相反，对于给定的拟序关系 T，T \cup I_A 则是 A 上的偏序关系. A 上的偏序关系和拟序关系之间存在着——对应. 这个证明留给读者思考.

解读：偏序与拟序只差「自反性」一条，所以二者可以互相翻译：R - I_A 把每个元素的自环摘掉就成了拟序，T \cup I_A 把自环补回去就成了偏序。拟序不用额外要求反对称——反自反加传递已经蕴含了它。

下面考虑在定义了偏序关系的集合中，元素之间在序上可能存在哪些不同的情况. 任取两个元素 x 和 y，可能有下述几种情况发生：

x \prec y \text{（或 } y \prec x \text{）}, \quad x = y, \quad x \text{ 与 } y \text{ 不是可比的}

如果存在不可比的情况，那么这个偏序在集合中是部分序. 但对某些集合，任何两个元素之间都存在序关系，这就是全序关系.

定义 4.25 设 R 为非空集合 A 上的偏序关系，\forall x, y \in A，x 与 y 都是可比的，则称 R 为全序关系，简称全序（或线序）.

存在着许多全序关系，例如数集上的小于等于关系是全序关系，字典顺序是英文字符串集合上的全序关系，而整除关系不是正整数集合上的全序关系.

定义 4.26 设 R 为非空集合 A 上的偏序，x, y \in A，如果 x \prec y 且不存在 z \in A 使得 x \prec z \prec y，则称 y 覆盖 x.

不难看出，y 覆盖 x，意味着在序上 y 是紧跟在 x 后面的元素，y 和 x 之间不允许夹有其他元素. 例如 \{1, 2, 4, 6\} 集合上的整除关系，2 覆盖 1，4 和 6 覆盖 2，但 4 不覆盖 1. 对于全序关系，集合的全体元素根据覆盖的顺序可以排成一条链. 但是对于非全序的偏序关系，如果集合的元素数至少是 2，那么只能存在由真子集构成的部分链，而且这种链至少存在 2 条.

如果知道了偏序关系，不难确定集合元素之间的覆盖性质；反之，如果知道了元素之间的覆盖性质，同样也不难得到偏序关系的集合表达式. 因此，对于偏序关系 R，可以定义 R 的一个子关系——覆盖关系 T

T = \{\langle x, y \rangle \mid \langle x, y \rangle \in R \text{ 且 } y \text{ 覆盖 } x\}

如果偏序关系是 R，且由 R 确定的覆盖关系是 T，不难证明 T 的自反传递闭包 rt(T) 就等于 R.

4.4.5 偏序集与哈斯图

定义 4.27 集合 A 和 A 上的偏序关系 \preccurlyeq 一起叫做偏序集，记作 \langle A, \preccurlyeq \rangle.

下面是一些偏序集的实例：

整数集 \mathbf{Z} 和数的小于或等于关系 \leqslant 构成偏序集 \langle \mathbf{Z}, \leqslant \rangle.

正整数集和数的整除关系构成偏序集，记作 \langle \mathbf{Z}^+, | \rangle.

集合 A 的幂集 P(A) 和包含关系 R_{\subseteq} 构成偏序集 \langle P(A), R_{\subseteq} \rangle.

集合 A 与恒等关系 I_A 构成偏序集，记作 \langle A, I_A \rangle.

例 4.21 设 \langle A, R \rangle 和 \langle B, S \rangle 是偏序集，证明 \langle A \times B, T \rangle 也是偏序集，其中关系 T 的定义如下：\forall \langle x, y \rangle，\langle u, v \rangle \in A \times B，\langle x, y \rangle T \langle u, v \rangle \Leftrightarrow xRu \wedge ySv.

证明 \forall \langle x, y \rangle \in A \times B，因为 R，S 都是自反的，因此有 xRx 和 ySy，从而得到 \langle x, y \rangle T \langle x, y \rangle，这就证明了 T 在 A \times B 上是自反的.

\forall \langle x, y \rangle，\langle u, v \rangle \in A \times B，

\begin{aligned} \langle x, y \rangle T \langle u, v \rangle \wedge \langle u, v \rangle T \langle x, y \rangle \\ \Rightarrow (xRu \wedge ySv) \wedge (uRx \wedge vSy) \\ \Rightarrow (xRu \wedge uRx) \wedge (ySv \wedge vSy) \end{aligned}
\begin{aligned} &\Rightarrow x = u \wedge y = v \\ &\Rightarrow \langle x, y \rangle = \langle u, v \rangle \end{aligned}

这就证明了 T 在 A \times B 上是反对称的.

\forall \langle x, y \rangle，\langle u, v \rangle，\langle w, t \rangle \in A \times B，

\begin{aligned} \langle x, y \rangle T \langle u, v \rangle \wedge \langle u, v \rangle T \langle w, t \rangle \\ \Rightarrow xRu \wedge ySv \wedge uRw \wedge vSt \\ \Rightarrow xRu \wedge uRw \wedge ySv \wedge vSt \\ \Rightarrow xRw \wedge ySt \\ \Rightarrow \langle x, y \rangle T \langle w, t \rangle \end{aligned}

这就证明了 T 在 A \times B 上是传递的.

表示偏序集可以使用哈斯图. 它是利用偏序关系的自反、反对称、传递性进行简化的关系图. 由于覆盖关系与偏序关系的对应性，只要在图中给出覆盖关系的所有信息，就不难得到对应偏序关系的全部信息. 哈斯图就是反映覆盖关系的信息图. 在偏序集 \langle A, \preccurlyeq \rangle 的哈斯图中，A 中的每个元素是一个结点，如果 y 覆盖 x，那么 y 的位置在 x 的位置的上方，并且用一条线段连接 x 和 y. 这里的位置代表了元素之间在偏序意义的「大小」，位置在下边的元素按照偏序应该排在前边，而位置在上边的元素按照偏序应该排在后边. 如果从结点 x 到 y 有一条向上的路径，那么在原来的偏序关系中 x \prec y. 下面是一些哈斯图的例子.

解读：画哈斯图只做三件事：去掉自环（自反性保证每点都有）、去掉可由传递性推出的边（只留覆盖关系）、把 y 覆盖 x 时把 y 画在上方。所以一张哈斯图里没有箭头，边的方向由「上大下小」隐式给出。

哈斯图：{1,…,9} 上的整除关系与 P({a,b,c}) 上的包含关系

例 4.22 画出偏序集 \langle \{1, 2, 3, 4, 5, 6, 7, 8, 9\}, | \rangle 和 \langle P(\{a, b, c\}), R_{\subseteq} \rangle 的哈斯图.

解 这两个哈斯图给在图 4.8 中.

例 4.23 已知偏序集 \langle A, R \rangle 的哈斯图如图 4.9 所示，试求出集合 A 和关系 R 的表达式.

解 A = \{a, b, c, d, e, f\}

R = \{\langle b, d \rangle, \langle b, e \rangle, \langle b, f \rangle, \langle c, d \rangle, \langle c, e \rangle, \langle c, f \rangle, \langle d, f \rangle, \langle e, f \rangle\} \cup I_A

原书图4.9 例 4.23 的哈斯图

下面考虑偏序集的特殊元素或者子集.

定义 4.28 设 \langle A, \preccurlyeq \rangle 为偏序集，B \subseteq A，y \in B.

（1）若 \forall x(x \in B \rightarrow y \preccurlyeq x) 成立，则称 y 为 B 的最小元.

（2）若 \forall x(x \in B \rightarrow x \preccurlyeq y) 成立，则称 y 为 B 的最大元.

（3）若 \forall x(x \in B \wedge x \preccurlyeq y \rightarrow x = y) 成立，则称 y 为 B 的极小元.

（4）若 \forall x(x \in B \wedge y \preccurlyeq x \rightarrow x = y) 成立，则称 y 为 B 的极大元.

在图 4.8 的偏序集 \langle \{1, 2, \cdots, 9\}, | \rangle 中，最小元和极小元都是 1，没有最大元，但是有 5 个极大元，就是 5、6、7、8、9. 而偏序集 \langle P(\{a, b, c\}), R_{\subseteq} \rangle 的最大元和极大元都是 \{a, b, c\}，最小元和极小元都是 \varnothing. 而在图 4.9 的偏序集中，极小元是 a, b 和 c，极大元是 a 和 f，既没有最大元也没有最小元.

可以证明最小元、最大元、极小元、极大元具有下述性质：

（1）对于有穷集，极小元和极大元一定存在，还可能存在多个.

（2）最小元和最大元不一定存在，如果存在一定唯一.

（3）最小元一定是极小元；最大元一定是极大元.

（4）孤立结点既是极小元，也是极大元.

这里给出性质（2）的证明，其他留给读者思考.

证明 首先看到图 4.9 中的偏序集就不存在最大元和最小元. 假设偏序集存在最小元 x，y. 根据最小元定义，x 和 y 要小于或等于偏序集中所有的元素，因此必有 x \preccurlyeq y 和 y \preccurlyeq x 成立，由于偏序关系的反对称性，x = y 得证.

解读：最小元是「比 B 里所有元素都小」，因此必须在 B 中；极小元只是「B 里没有比它更小的」，可以有好几个。最大元与极大元的差别同理。

定义 4.29 设 \langle A, \preccurlyeq \rangle 为偏序集，B \subseteq A，y \in A.

（1）若 \forall x(x \in B \rightarrow x \preccurlyeq y) 成立，则称 y 为 B 的上界.

（2）若 \forall x(x \in B \rightarrow y \preccurlyeq x) 成立，则称 y 为 B 的下界.

（3）令 C = \{y \mid y \text{ 为 } B \text{ 的上界}\}，则称 C 的最小元为 B 的最小上界或上确界.

（4）令 D = \{y \mid y \text{ 为 } B \text{ 的下界}\}，则称 D 的最大元为 B 的最大下界或下确界.

对于图 4.8 中关于整除关系的偏序集，如果规定 B = \{2, 4, 5\}，C = \{2, 4\}，那么 B 没有上界和最小上界，下界和最大下界都是 1；而 C 的上界为 4 和 8，最小上界为 4；下界为 2 和 1，最大下界为 2.

可以证明下界、上界、最大下界与最小上界存在下述性质：

（1）下界、上界、最大下界、最小上界不一定存在.

（2）如果下界、上界存在，也不一定是唯一的.

（3）最大下界、最小上界如果存在，则是唯一的.

（4）子集 B 的最小元就是它的最大下界，最大元就是它的最小上界；反之不对.

下面证明性质（4），其他留给读者思考.

证明 设偏序集为 \langle A, \preccurlyeq \rangle，B \subseteq A，B 的最小元为 a. 最大下界是 b. 由于最小元要小于等于 B 中的所有元素，因此 a 是 B 的一个下界. 又由于 b 是 B 的最大下界，因此 a \preccurlyeq b. 另一方面，b 是下界，它要小于等于 B 中的所有元素，因此 b \preccurlyeq a. 综合上述就得到 a = b. 同理可证最大元也是它的最小上界.

反过来，B 的最大下界不一定是 B 的最小元，因为这个下界可能不在 B 集合中. 考虑整除关系的偏序集 \langle \{1, 2, \cdots, 9\}, | \rangle，令 B = \{2, 3\}，那么 B 的下界是 1，但是 1 不是 B 的最小元.

下面考虑偏序集的某些特殊子集.

定义 4.30 设 \langle A, \preccurlyeq \rangle 为偏序集，B \subseteq A.

（1）如果 \forall x, y \in B，x 与 y 都是可比的，则称 B 是 A 中的一条链，B 中的元素个数称为链的长度.

（2）如果 \forall x, y \in B，x \neq y，x 与 y 都是不可比的，则称 B 是 A 中的一条反链，B 中的元素个数称为反链的长度.

在偏序集 \langle \{1, 2, \cdots, 9\}, | \rangle 中，\{1, 2, 4, 8\} 是长为 4 的链，\{1, 4\} 是长为 2 的链，\{2, 3\} 是长为 2 的反链. 对于单元集 \{2\}，它的长度是 1，既是链也是反链.

偏序集中的链表达了在部分元素中存在的全序关系，而反链则反映了元素之间没有任何序的关系. 图 4.10 是一个保险索赔的流程图. 图中的矩形方框代表处理流程中的任务，圆圈代表某种分支选择. 在对流程进行逻辑分析时可以忽略流程中的循环成分，可以将循环抽象成一个单一的大结点，例如用一个结点 T 代替流程图中的任务 T_7、T_8 和后面的分支结点. 所有的结点构成一个集合，在集合的元素之间存在如下偏序关系：对于任意结点 x 和 y，x \preccurlyeq y \Leftrightarrow x = y 或者 y 必须在 x 完成后才能开始执行.

原书图4.10 保险索赔流程图

集合和偏序关系构成偏序集，这个偏序集的哈斯图如图 4.11 所示.

原书图4.11 图 4.10 偏序集的哈斯图

考虑偏序集中的链，最长链有 4 条，其中 2 条分别是 \{T_1, T_2, T_3, S_1, T_6, S_2, T, T_{10}\} 和 \{T_1, T_2, T_3, S_1, T_6, S_2, T_9, T_{10}\}，长度都是 8. 它代表了整个流程中必须顺序执行的任务最多有多少个. 如果完成每项任务的时间差距不大，这种最长的链往往反映了完成任务的最少时间. 从提高效率的角度考虑，并行执行是减少总时间的一种途径. 在一个偏序集或者子偏序集中，如果能够将任务按照不相交的链进行分解，那么这些不相交的链是可以在一定程度上并行执行的. 另一方面，如果把偏序集分解成不相交的反链，那么最长的反链长度则代表了在某个时间区间极大可并行执行的任务数. 关于偏序集的分解有下面的定理.

定理 4.9 设 \langle A, \preccurlyeq \rangle 为偏序集，如果 A 中最长的链长度为 n，则该偏序集可以分解为 n 条不相交的反链.

限于篇幅，这里省去证明，仅对定理做一点说明. 这个定理称为偏序集的分解定理，是组合数学中重要的存在性定理之一. 这种分解是所有分解方法中反链个数最少的一种分解方法，因为 A 不可能分解成 n-1 条反链. 假若只有 n-1 条反链，那么最长链的 n 个元素中必有 2 个元素被分到同一个反链，显然这与反链的定义矛盾. 有穷偏序集分解成 n 条反链的过程可以采用下面的方法去做.

算法 4.2 偏序集反链分解算法.

输入：偏序集 A.

输出：A 中的反链 B_1，B_2，\cdots.

  1. i \leftarrow 1
  1. B_i \leftarrow A 的所有极大元的集合（显然 B_i 是一条反链）
  1. 令 A \leftarrow A - B_i
  1. if A \neq \varnothing
  1. \quad i \leftarrow i + 1
  1. \quad 转 2

注意：从 A 中去掉 B_i 中的元素时，同时去掉连接这些元素与被它覆盖的元素之间的边. 行 2～3 每执行一次，最长链的长度减少 1，同时产生一条新的反链. 因为最长链长度为 n，恰好执行 n 次，算法结束，并得到 n 条反链.

如果只有一台处理器，在有限个任务的调度中需要根据偏序要求对所有的任务安排一个执行顺序. 用集合论的术语来说，就是把原来的偏序集扩张成全序集，这种方法称为拓扑排序. 具体的算法如下.

算法 4.3 拓扑排序.

输入：偏序集 A.

输出：A 中元素的排序.

  1. i \leftarrow 1
  1. 从 A 中选择一个极小元 a_i 作为最小元
  1. A \leftarrow A - \{a_i\}
  1. if A \neq \varnothing
  1. \quad i \leftarrow i + 1
  1. \quad 转 2

和算法 4.2 类似，从 A 中去掉 a_i 时，同时去掉连接 a_i 与覆盖它的元素之间的边. 不难看出，经过有限步算法结束，元素被选出的顺序就是任务的执行顺序. 显然所得到的顺序不是唯一的. 对于图 4.11 的偏序集，一种拓扑排序的结果是

T_1, T_2, T_3, T_4, S_1, T_5, T_6, S_2, T, T_9, T_{10}

解读：定理 4.9 给的是「最长链长度 = 最少反链条数」，而算法 4.2 的每一轮恰好把当前所有极大元取走，所以反链条数正好等于最长链长度，两者互相印证。算法 4.3 的拓扑排序则相反，每轮取一个极小元，得到的是链的线性扩展。