在了解Dilworth’s theorem 之前，我们先了解一下偏序集（partiallly ordered set）的概念

partially ordered set

正式定义

一个偏序集 （通常简写为 poset） 由一个集合 P 和一个二元关系 “≤” 组成，这个关系满足以下三个性质：

自反性：对于任何元素 a ∈ P，都有 a ≤ a。

解释：任何元素自己和自己都是有关系的。这很自然，就像数字5总是等于5一样。

反对称性：如果 a ≤ b 且 b ≤ a，那么必须有 a = b。

解释：不可能有两个不同的元素互相“小于等于”对方。如果它们互相“≤”，那它们只能是同一个元素。这防止了循环比较中的歧义。

传递性：如果 a ≤ b 且 b ≤ c，那么一定有 a ≤ c。

解释：次序关系可以传递。如果A是B的上司，B是C的上司，那么A一定是C的上司。

这个“≤”关系不一定是我们熟悉的数字中的“小于等于”，它可以是任何满足上述三条规则的关系。

关键点

其实如果感觉定义不太好理解可以想象他是一个“可以比较但不必全能比较”的次序

例子

集合S = {2,3,4}，我们先考虑他子集形成的集合
P(S) = {∅,{2},{3},{4},{2,3},{2,4},{3,4},{2,3,4}};
这里的排序关系中的“<=”其实就是集合里面的属于关系，但P(S)里面的元素 可以用属于链接的时候他们便是可比的，否则就是不可比较的

Dilworth’s theorem

正式定义

狄尔沃斯定理亦称偏序集分解定理，是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目，由偏序集P按如下方式产生的图G称为偏序集的可比图：G的节点集由P的元素组成，而e为G中的边，仅当e的两端点在P中是可比较的，有限全序集的可比图为完全图

关键点

我们先理清几个概念：
链: 偏序集的一个子集，其中元素可以比较
反链： 偏序集的一个子集，其中元素不可比较
Dilworth’s theorem 告诉我们覆盖全部集合的链的个数等于反链的大小

例子

假设大学里有一些课程，并且存在选修依赖关系（学B前必须先学A，即 A ≤ B）。有些课程则没有先后顺序（比如《音乐鉴赏》和《足球理论》，它们不可比）。

反链：一堆没有任何先后顺序要求的课程（比如一堆同一级别的公共选修课）。这个集合能有多大？假设最多有 5 门这样的课。

链：一条学习路径，比如《高等数学I》→《高等数学II》→《常微分方程》。

Dilworth定理告诉我们，你至少需要 5 条不同的学习路径（链），才能覆盖所有的课程。因为那5门互不依赖的课（反链）绝对不能出现在同一条路径上，必须被分开到5条路径中去。

了解后想去练手可以尝试一下洛谷的导弹拦截（https://www.luogu.com.cn/problem/P1020）