离散数学-Week6

离散数学-第6周小结

发表于 2025/10/20 更新于 2025/10/20

作者 Metahumanz

34 分钟阅读

离散数学-Week6

关系的性质

关系性质的定义和判别

自反性与反自反性

定义4.14 设R为A上的关系：

若∀x(x∈A → <x,x>∈R)，则称R在A上是自反的
若∀x(x∈A → <x,x>∉R)，则称R在A上是反自反的

实例：

自反关系：A上的全域关系E_A、恒等关系I_A、小于等于关系L_A、整除关系D_A
反自反关系：实数集上的小于关系、幂集上的真包含关系

例1：A = {a, b, c}, R₁, R₂, R₃是A上的关系

R₁ = {<a,a>,<b,b>}
R₂ = {<a,a>,<b,b>,<c,c>,<a,b>}
R₃ = {<a,c>}

R₂自反，R₃反自反，R₁既不自反也不反自反

对称性与反对称性

定义4.15 设R为A上的关系：

若∀x∀y(x,y∈A ∧ <x,y>∈R → <y,x>∈R)，则称R为A上对称的关系
若∀x∀y(x,y∈A ∧ <x,y>∈R ∧ <y,x>∈R → x=y)，则称R为A上反对称的关系

实例：

对称关系：A上的全域关系E_A、恒等关系I_A和空关系∅
反对称关系：恒等关系I_A、空关系∅

例2：设A＝{a,b,c}, R₁, R₂, R₃和R₄都是A上的关系

R₁＝{<a,a>,<b,b>}
R₂＝{<a,a>,<a,b>,<b,a>}
R₃＝{<a,b>,<a,c>}
R₄＝{<a,b>,<b,a>,<a,c>}

R₁对称、反对称；R₂对称，不反对称；R₃反对称，不对称；R₄不对称、也不反对称

传递性

定义4.16 设R为A上的关系，若
∀x∀y∀z(x,y,z∈A ∧ <x,y>∈R ∧ <y,z>∈R → <x,z>∈R)
则称R是A上的传递关系

实例：A上的全域关系E_A、恒等关系I_A和空关系∅、小于等于关系、小于关系、整除关系、包含关系、真包含关系

例3：设A＝{a, b, c}, R₁, R₂, R₃是A上的关系

R₁＝{<a,a>,<b,b>}
R₂＝{<a,b>,<b,c>}
R₃＝{<a,c>}

R₁和R₃是A上的传递关系，R₂不是A上的传递关系

关系性质的充要条件

设R为A上的关系，则：

自反性：R在A上自反 ⇔ I_A ⊆ R
反自反性：R在A上反自反 ⇔ R ∩ I_A = ∅
对称性：R在A上对称 ⇔ R = R⁻¹
反对称性：R在A上反对称 ⇔ R ∩ R⁻¹ ⊆ I_A
传递性：R在A上传递 ⇔ R ∘ R ⊆ R

证明方法

自反性证明

证明模式：证明R在A上自反

任取x, x∈A ⇒ … ⇒ <x,x>∈R 前提推理过程结论

例4：证明若I_A ⊆ R，则R在A上自反
证明：
任取x,
x∈A ⇒ <x,x> ∈ I_A ⇒ <x,x> ∈ R
因此R在A上是自反的

对称性证明

证明模式：证明R在A上对称

任取<x,y>, <x,y>∈R ⇒ … ⇒ <y,x>∈R 前提推理过程结论

例5：证明若R = R⁻¹，则R在A上对称

证明：
任取<x,y>,
<x,y>∈R ⇒ <y,x>∈R⁻¹ ⇒ <y,x>∈R
因此R在A上是对称的

反对称性证明

证明模式：证明R在A上反对称

任取<x,y>, <x,y>∈R ∧ <y,x>∈R ⇒ … ⇒ x=y 前提推理过程结论

例6：证明若R ∩ R⁻¹ ⊆ I_A，则R在A上反对称

证明：
任取<x,y>,
<x,y>∈R ∧ <y,x>∈R ⇒ <x,y>∈R ∧ <x,y>∈R⁻¹
⇒ <x,y>∈R ∩ R⁻¹ ⇒ <x,y>∈I_A ⇒ x=y
因此R在A上是反对称的

传递性证明

证明模式：证明R在A上传递

任取<x,y>,<y,z>, <x,y>∈R ∧ <y,z>∈R ⇒ … ⇒ <x,z>∈R 前提推理过程结论

例7：证明若R ∘ R ⊆ R，则R在A上传递

证明：
任取<x,y>,<y,z>,
<x,y>∈R ∧ <y,z>∈R ⇒ <x,z>∈R ∘ R ⇒ <x,z>∈R
因此R在A上是传递的

关系性质判别与闭包

关系性质判别表

性质	表达式	关系矩阵	关系图
自反性	$I_A \subseteq R$	主对角线元素全是 1	每个顶点都有环
反自反性	$R \cap I_A = \varnothing$	主对角线元素全是 0	每个顶点都没有环
对称性	$R = R^{-1}$	矩阵是对称矩阵	如果两个顶点之间有边，一定是一对方向相反的边（无单向边）
反对称性	$R \cap R^{-1} \subseteq I_A$	若 $r_{ij} = 1$ 且 $i \ne j$，则 $r_{ji} = 0$	如果两点之间有边，一定是一条有向边（无双向边）
传递性	$R \circ R \subseteq R$	对 $M^2$ 中为 1 的位置，$M$ 中相应位置也都是 1	如果顶点 $x_i$ 到 $x_j$ 有边，$x_j$ 到 $x_k$ 有边，则 $x_i$ 到 $x_k$ 也有边

关系的性质和运算之间的联系

设 $R_1$、$R_2$ 是集合 $A$ 上的关系。下表表示在进行相应运算后，新关系是否保持原有性质（✓ 表示保持，× 表示不一定保持）：

性质	$R_1^{-1}$	$R_1 \cap R_2$	$R_1 \cup R_2$	$R_1 - R_2$	$R_1 \circ R_2$
自反性	✓	✓	✓	×	✓
反自反性	✓	✓	✓	✓	×
对称性	✓	✓	✓	✓	×
反对称性	✓	✓	✓	✓	×
传递性	✓	✓	×	×	×

关系的闭包

闭包定义

定义4.17 设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R′，使得R′满足以下条件：

R′是自反的（对称的或传递的）
R ⊆ R′
对A上任何包含R的自反（对称或传递）关系R″有 R′ ⊆ R″

一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。

闭包的构造方法

集合表示

定理4.7 设R为A上的关系，则有：

r(R) = R ∪ R⁰
s(R) = R ∪ R⁻¹
t(R) = R ∪ R² ∪ R³ ∪ ⋯

说明：

对于有穷集合A ( A = n) 上的关系，(3)中的并最多不超过Rⁿ
若R是自反的，则r(R) = R；若R是对称的，则s(R) = R；若R是传递的，则t(R) = R

定理4.7的证明

证(1) r(R) = R ∪ R⁰ 只需证明R ∪ R⁰满足闭包定义：

R ∪ R⁰包含了R
由I_A ⊆ R ∪ R⁰可知R ∪ R⁰在A上是自反的（因为R在A上自反当且仅当I_A ⊆ R）
下面证明R ∪ R⁰是包含R的最小的自反关系：
假设R′是包含R的自反关系，那么I_A ⊆ R′，R ⊆ R′，因此有R ∪ R⁰ = I_A ∪ R ⊆ R′

证(3) t(R) = R ∪ R² ∪ R³ ∪ ⋯
任取<x,y>和<y,z>：

<x,y> ∈ R ∪ R² ∪ R³ ∪ ⋯ ∧ <y,z> ∈ R ∪ R² ∪ R³ ∪ ⋯
⇒ <x,z> ∈ R ∪ R² ∪ R³ ∪ ⋯

于是，由R ∪ R² ∪ R³ ∪ ⋯的传递性得t(R) ⊆ R ∪ R² ∪ R³ ∪ ⋯

对n进行归纳证明Rⁿ ⊆ t(R)：

n = 1时显然为真
假设n = k时为真，那么对于任意<x,y>：
- <x,y> ∈ Rᵏ⁺¹ ⇒ <x,y> ∈ Rᵏ ∘ R ⇒ ∃t(<x,t> ∈ Rᵏ ∧ <t,y> ∈ R)
- ⇒ ∃t(<x,t> ∈ t(R) ∧ <t,y> ∈ t(R)) ⇒ <x,y> ∈ t(R) （t(R)传递）

于是，R ∪ R² ∪ R³ ∪ ⋯ ⊆ t(R)

矩阵表示

设关系R, r(R), s(R), t(R)的关系矩阵分别为M, M_r, M_s和M_t，则：

M_r = M + E
M_s = M + M′
M_t = M + M² + M³ + ⋯

其中E是和M同阶的单位矩阵，M′是M的转置矩阵。

注意：在上述等式中矩阵的元素相加时使用逻辑加。

图表示

设关系R, r(R), s(R), t(R)的关系图分别记为G, G_r, G_s, G_t，则G_r, G_s, G_t的顶点集与G的顶点集相等。除了G的边以外，以下述方法添加新的边：

自反闭包G_r：考察G的每个顶点，如果没有环就加上一个环
对称闭包G_s：考察G的每一条边，如果有一条x_i到x_j的单向边，i ≠ j，则在G中加一条x_j到x_i的反方向边
传递闭包G_t：考察G的每个顶点x_i，找从x_i出发的每一条路径，如果从x_i到路径中的任何结点x_j没有边，就加上这条边。当检查完所有的顶点后就得到图G_t

例1 设A = {a,b,c,d}, R = {<a,b>,<a,c>,<b,c>,<c,d>,<d,c>}，R和r(R), s(R), t(R)的关系图如下图所示。

传递闭包的计算——Warshall算法

算法思路

考虑n+1个矩阵的序列M₀, M₁, …, Mₙ，将矩阵Mₖ的i行j列的元素记作Mₖ[i,j]。

对于k = 0,1,…,n, Mₖ[i,j] = 1当且仅当在R的关系图中存在一条从x_i到x_j的路径，并且这条路径除端点外中间只经过{x₁, x₂, …, xₖ}中的顶点。

不难证明M₀就是R的关系矩阵，而Mₙ就对应了R的传递闭包。

Warshall算法

从M₀开始，顺序计算M₁, M₂, …, 直到Mₙ为止。

Warshall算法的依据

从Mₖ[i,j]计算Mₖ₊₁[i,j]：i,j ∈ V

顶点集V₁ = {1,2,…,k}, V₂ = {k+2,…,n}, V = V₁ ∪ {k+1} ∪ V₂

Mₖ₊₁[i,j] = 1 ⇔ 存在从i到j中间只经过V₁ ∪ {k+1}中点的路径

这些路径分为两类：

第1类：只经过V₁中点 ⇒ Mₖ[i,j] = 1
第2类：经过k+1点 ⇒ Mₖ[i,k+1] = 1 ∧ Mₖ[k+1,j] = 1

假设Mₖ已经计算完毕，如何计算Mₖ₊₁呢？这需要对于每组i,j确定Mₖ₊₁[i,j]是否为1。Mₖ₊₁[i,j] = 1当且仅当在R的关系图中存在一条从x_i到x_j并且中间只经过{x₁, x₂, …, xₖ₊₁}的路径，可以将这种路径分成两类：第一类是只经过{x₁, x₂, …, xₖ}的路径，这时M[i,j] = 1；第二类是经过xₖ₊₁的路径。因为回路可以从路径中删除，因此只需考虑经过一次的路径，这条路径可以分成两段，从x_i到xₖ，再从xₖ₊₁到x_j，因此有Mₖ[i,k+1] = 1和Mₖ[k+1,j] = 1。对于第二类路径的判别可以利用下面的条件：

Mₖ₊₁[i,j] = 1 ⇔ Mₖ[i,k+1] = 1 ∧ Mₖ[k+1,j] = 1

算法4.1 Warshall算法

输入：M（R的关系矩阵）
输出：M_t（t(R)的关系矩阵）

M_t ← M
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
M_t[i,j] ← M_t[i,j] + M_t[i,k] · M_t[k,j]

时间复杂度：T(n) = O(n³)

这个算法通过三重循环来更新关系矩阵，最终得到传递闭包的矩阵表示。

等价关系与偏序关系

等价关系

等价关系的定义与实例

定义4.18 设R为非空集合A上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一个等价关系，若<x,y>∈R，称x等价于y，记作x～y。

等价关系应用
在生活中经常遇到需要对集合中的元素进行分类的问题。例如：开学注册时，由于人数众多，为了避免拥挤，需要将所有新生分成三个类别，然后将这三个类别的学生分成不同时间段来完成注册。

其中一种方案是，将学号分成三段，每一段分配一个时间段。这种情况下，我们可以定义一个关系R，<a,b> ∈ R当且仅当a和b的学号在同一段。此关系R具备了自反、对称和传递的性质。

例1 设A = {1, 2, …, 8}，如下定义A上的关系R：

R={<x,y>∣x,y∈A∧x≡y(mod3)}R = \{<x,y> \mid x,y ∈ A ∧ x ≡ y \pmod{3}\}R={<x,y>∣x,y∈A∧x≡y(mod3)}

其中x ≡ y (mod 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。

不难验证R为A上的等价关系，因为：

∀x ∈ A，有x ≡ x (mod 3)
∀x,y ∈ A，若x ≡ y (mod 3)，则有y ≡ x (mod 3)
∀x,y,z ∈ A，若x ≡ y (mod 3)，y ≡ z (mod 3)，则有x ≡ z (mod 3)

设A = {1, 2, …, 7}，R = {<x,y> \mid x,y ∈ A ∧ x ≡ y (mod 3)}

R的关系图由若干个独立子图构成，每个独立子图都是完全关系图。

等价类和商集

等价类

定义4.19 设R为非空集合A上的等价关系，∀x ∈ A，令

[x]R={y∣y∈A∧xRy}[x]_R = \{ y \mid y ∈ A ∧ xRy \}[x]R={y∣y∈A∧xRy}

称[x]_R为x关于R的等价类，简称为x的等价类，简记为[x]。

实例 A = {1, 2, …, 8}上模3等价关系的等价类：

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

等价类的性质

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

∀x ∈ A，[x]是A的非空子集
∀x,y ∈ A，如果xRy，则[x] = [y]
∀x,y ∈ A，如果x ̸Ry，则[x]与[y]不交
$\bigcup_{x ∈ A} [x] = A$，即所有等价类的并集就是A

证明：
(1) 由等价类定义可知，∀x ∈ A有[x] ⊆ A。由自反性有xRx，因此x ∈ [x]，即[x]非空。
(2) 任取z，则有：

z∈[x]⇒<x,z>∈R⇒<z,x>∈Rz ∈ [x] ⇒ <x,z> ∈ R ⇒ <z,x> ∈ Rz∈[x]⇒<x,z>∈R⇒<z,x>∈R<z,x>∈R∧<x,y>∈R⇒<z,y>∈R⇒<y,z>∈R<z,x> ∈ R ∧ <x,y> ∈ R ⇒ <z,y> ∈ R ⇒ <y,z> ∈ R<z,x>∈R∧<x,y>∈R⇒<z,y>∈R⇒<y,z>∈R

从而证明了z ∈ [y]。综上所述必有[x] ⊆ [y]。同理可证[y] ⊆ [x]。这就得到了[x] = [y]。

(3) 假设[x] ∩ [y] ≠ ∅，则存在z ∈ [x] ∩ [y]，从而有z ∈ [x] ∧ z ∈ [y]，即<x,z> ∈ R ∧ <y,z> ∈ R成立。根据R的对称性和传递性必有<x,y> ∈ R，与x ̸Ry矛盾。

(4) 先证$\bigcup_{x ∈ A} [x] ⊆ A$。任取y，

y∈⋃x∈A[x]⇒∃x(x∈A∧y∈[x])⇒y∈[x]∧[x]⊆A⇒y∈Ay ∈ \bigcup_{x ∈ A} [x] ⇒ ∃x(x ∈ A ∧ y ∈ [x]) ⇒ y ∈ [x] ∧ [x] ⊆ A ⇒ y ∈ Ay∈x∈A⋃[x]⇒∃x(x∈A∧y∈[x])⇒y∈[x]∧[x]⊆A⇒y∈A

从而有$\bigcup_{x ∈ A} [x] ⊆ A$。

再证$A ⊆ \bigcup_{x ∈ A} [x]$。任取y，

y∈A⇒y∈[y]∧y∈A⇒y∈⋃x∈A[x]y ∈ A ⇒ y ∈ [y] ∧ y ∈ A ⇒ y ∈ \bigcup_{x ∈ A} [x]y∈A⇒y∈[y]∧y∈A⇒y∈x∈A⋃[x]

从而有$A ⊆ \bigcup_{x ∈ A} [x]$成立。综上所述得$\bigcup_{x ∈ A} [x] = A$。

商集

定义4.20 设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集，记作A/R，

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

例2
令A = {1, 2, …, 8}，A关于模3等价关系R的商集为

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

A关于恒等关系和全域关系的商集为：

A/I_A = { {1}, {2}, …, {8} }
A/E_A = { {1,2,…,8} }

集合的划分

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

∅ ∉ π
∀x∀y(x,y ∈ π ∧ x ≠ y → x ∩ y = ∅)
∪π = A

则称π是A的一个划分，称π中的元素为A的划分块。

例3 设A = {a,b,c,d}，给定π₁, π₂, π₃, π₄, π₅, π₆如下：

π₁ = { {a,b,c},{d} }
π₂ = { {a,b},{c},{d} }
π₃ = { {a},{a,b,c,d} }
π₄ = { {a,b},{c} }
π₅ = {∅,{a,b},{c,d} }
π₆ = { {a,{a}},{b,c,d} }

则π₁和π₂是A的划分，其他都不是A的划分。

重要结论：

商集A/R就是A的一个划分
不同的商集对应于不同的划分
任给A的一个划分π，如下定义A上的关系R：

R={<x,y>∣x,y∈A∧x与y在π的同一划分块中}R = \{<x,y> \mid x,y ∈ A ∧ x与y在π的同一划分块中\}R={<x,y>∣x,y∈A∧x与y在π的同一划分块中}

则R为A上的等价关系，且该等价关系确定的商集就是π

例4 给出A = {1,2,3}上所有的等价关系
求解思路：先做出A的所有划分，然后根据划分写出对应的等价关系。 A上的等价关系与划分之间的对应：

π₄对应于全域关系E_A
π₅对应于恒等关系I_A
π₁, π₂和π₃分别对应于等价关系R₁, R₂和R₃，其中：
- R₁ = {<2,3>,<3,2>} ∪ I_A
- R₂ = {<1,3>,<3,1>} ∪ I_A
- R₃ = {<1,2>,<2,1>} ∪ I_A

例5 设A = {1,2,3,4}，在A×A上定义二元关系R：
«x,y>,<u,v>>∈R⇔x+y=u+v«x,y>,<u,v» ∈ R ⇔ x+y = u+v«x,y>,<u,v>>∈R⇔x+y=u+v

求R导出的划分。

解 A×A = {<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}

根据有序对<x,y>的x+y=2,3,4,5,6,7,8将A×A划分：

(A×A)/R={ {<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<2,3>,<3,2>,<4,1>},{<2,4>,<3,3>,<4,2>},{<3,4>,<4,3>},{<4,4>} }

偏序关系

定义4.22 非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作≼。设≼为偏序关系，如果<x,y> ∈ ≼，则记作x ≼ y，读作x”小于或等于”y。
注意：这里的”小于等于”不是指数的大小，而是指在偏序关系中的顺序性。x”小于等于”y的含义是：依照这个序，x排在y的前边或者x就是y。根据不同偏序的定义，对序有着不同的解释。例如：

整除关系是偏序关系≼，3 ≼ 6的含义是3整除6
大于等于关系也是偏序关系，针对这个关系写5 ≼ 4是说在大于等于关系中5排在4的前边，也就是说5比4大

实例：

集合A上的恒等关系I_A是A上的偏序关系
小于或等于关系、整除关系和包含关系也是相应集合上的偏序关系

偏序集与哈斯图

偏序集

定义4.27 集合A和A上的偏序关系≼一起叫做偏序集，记作<A,≼>。

实例：

整数集和数的小于等于关系构成偏序集<Z,≤>
幂集P(A)和包含关系构成偏序集<P(A),R⊆>

哈斯图

利用偏序自反、反对称、传递性简化的关系图。

特点：

每个结点没有环
两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前
具有覆盖关系的两个结点之间连边

哈斯图实例

例6

<{1,2,3,4,5,6,7,8,9}, R整除>
<P({a,b,c}), R⊆>

例7 已知偏序集<A,R>的哈斯图如下图所示，试求出集合A和关系R的表达式。

A = {a,b,c,d,e,f}
R = {<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>} ∪ I_A

偏序集的特定元素

定义4.28 设<A,≼>为偏序集，B ⊆ A，y ∈ B。

若∀x(x ∈ B → y ≼ x)成立，则称y为B的最小元
若∀x(x ∈ B → x ≼ y)成立，则称y为B的最大元
若∀x(x ∈ B ∧ x ≼ y → x = y)成立，则称y为B的极小元
若∀x(x ∈ B ∧ y ≼ x → x = y)成立，则称y为B的极大元

性质：

对于有穷集，极小元和极大元必存在，可能存在多个
最小元和最大元不一定存在，如果存在一定惟一
最小元一定是极小元；最大元一定是极大元
孤立结点既是极小元，也是极大元

定义4.29 设<A,≼>为偏序集，B ⊆ A，y ∈ A。

若∀x(x ∈ B → x ≼ y)成立，则称y为B的上界
若∀x(x ∈ B → y ≼ x)成立，则称y为B的下界
令C = {y y为B的上界}，则称C的最小元为B的最小上界或上确界
令D = {y y为B的下界}，则称D的最大元为B的最大下界或下确界

性质：

下界、上界、下确界、上确界不一定存在
下界、上界存在不一定惟一
下确界、上确界如果存在，则惟一
集合的最小元就是它的下确界，最大元就是它的上确界；反之不对

例8 设偏序集<A,≼>如下图所示，求A的极小元、最小元、极大元、最大元。设B = {b,c,d}，求B的下界、上界、下确界、上确界。

解：

极小元：a,b,c
极大元：a,f
没有最小元与最大元
B的下界和最大下界不存在
上界有d和f，最小上界为d

偏序集的特殊子集

定义4.30 设<A,≼>为偏序集，B ⊆ A。

如果∀x,y ∈ B，x与y都是可比的，则称B是A中的一条链，B中的元素个数称为链的长度
如果∀x,y ∈ B，x ≠ y，x与y都是不可比的，则称B是A中的一条反链，B中的元素个数称为反链的长度

实例：在偏序集<{1,2,…,9},

>中，{1,2,4,8}是长为4的链，{1,4}是长为2的链，{2,3}是长为2的反链。对于单元集{2}，它的长度是1，既是链也是反链。

分解为反链

定理4.9 设<A,≼>为偏序集，如果A中最长的链长度为n，则该偏序集可以分解为n条不相交的反链。

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

输入：偏序集A
输出：A中的反链B₁, B₂, …

text

1. i ← 1

B_i ← A的所有极大元的集合（显然B_i是一条反链）
令A ← A - B_i
if A ≠ ∅
i ← i + 1
转2

举例
考虑一个工厂，有一系列的任务需要完成，而这些任务之间存在依赖关系，即某些任务必须在其他任务之后完成。这可以视为一个偏序集，其中元素是任务，偏序关系是任务之间的依赖关系。

例如，假设我们有以下五个任务：

制造零件A
制造零件B
组装零件A和B组装产品X
包装产品X
运输产品X

偏序关系如下：

制造零件A和制造零件B可以同时进行，但都必须在组装产品X之前完成
组装产品X必须在包装产品X之前完成
包装产品X必须在运输产品X之前完成

在这种情况下，反链可以帮助我们确定哪些任务可以同时进行。例如，制造零件A和制造零件B是不可比的，因为它们没有直接的依赖关系，所以它们可以被看作是一个反链，意味着这两个任务可以同时开始。通过找到所有可能的反链，我们可以优化任务的调度，确保以最有效的方式进行任务，同时满足所有的依赖关系。

拓扑排序

把偏序集扩张成一个全序集，称为拓扑排序。

算法4.3 拓扑排序

输入：偏序集A
输出：A中元素的排序