Dilworth 定理

whm_xii · 2025-11-24 13:43:45 · 算法·理论

Dilworth 定理：对于任意有限偏序集，其最大反链中元素数目等于最小链划分中链的数目。

前置知识

1. 二元关系：设 P 为非空集合，若 \preceq \ \subseteq P\times P （即 \preceq 为关于 P 的有序对集合），又有 (a,b)\in R，则称 a,b 满足关系 \preceq，记为 a\preceq b。

2. 偏序关系：设 P 为非空集合，对于任意一个二元关系 \preceq\ \subseteq S\times S，如果它满足下面的三条公理，我们称这样的二元关系为偏序关系。

   • 对所有的 x\in P，x\preceq x（自反性）
   • 如果 x\preceq y 且 y\preceq x，则 x=y（反对称性）
   • 如果 x\preceq y 且 y\preceq z，则 x\preceq z（传递性）

3. 偏序集：设 P 为非空集合，连同一个记为 \preceq 的偏序关系，这样的偏序关系和集合为偏序集，记为 (P,\preceq)。

4. 可比：设偏序集 (P,\preceq)，对于 P 中的两个元素 x,y，若 x\preceq y 或 y\preceq x，则称 x,y 是可比的。

5. 不可比：设偏序集 (P,\preceq)，对于 P 中的两个元素 x,y，若即不满足 x \preceq y ，也不满足 y\preceq x，则称 x,y 是不可比的。

6. 覆盖：设偏序集 (P,\preceq)，对于 P 中的两个元素 x,y，若 x\preceq y 且不存在 z\in P，并且 z\neq x,z\neq y，使得 x\preceq z\preceq y，则称 y 覆盖 x。

7. Hasse 图：设偏序集 (P,\preceq)，有限偏序集的Hasse 图是指顶点为 P 中元素，边为覆盖关系，并且若 x\preceq y，y 画在 x 上方（具有更高的纵坐标）的图形。不难发现，若将所有边都指向靠下的点，Hasse 图就变为了一张有向无环图。

8. 链：任意两个元素都可比的偏序集。又称为全序集。

9. 反链：任意两个元素都不可比的偏序集，又称为 Sperner 族。

10. 最小链划分：将偏序集 (P,\preceq) 划分为若干条互不相交的链，使得链的数目最小化。

    证明

记偏序集 (S,\preceq)，对集合的大小进行归纳。

当 |S|=1 时，最大反链长度为 1，链最少被划分为 1 组，结论成立。

当 |S|>1 时，此时我们取出一条最长反链，不妨记为 A=\{a_1\dots a_m\}，记 D(A)=\{x\mid\exist a\in A,x<a\}，U(A)=\{x\mid\exist a\in A,x>a\}。那么我们有 S=A\cup D(A)\cup U(A)。

1.存在最长反链 A，使得 D(A)，U(A) 均不为空，那么此时 A\cup D(A) 的最长反链也为 A，同时 |A\cup D(A)|<|S|，则 A\cup D(A) 的最小链划分中链的数目为 m，并且划分出来的每条链的最大元为 a_1\dots a_m，同理，A\cup U(A) 中划分出来的每条链的最小元 a_1\dots a_m，将其两两对应，一条链接在令一条链后面，得到 A\cup D(A) \cup U(A) 的最小链划分中链的数目也为 m。

2.若每一条最长反链 A，都有 D(A) 或 U(A) 为空，则意味着对于每一条最长反链，它都取到了每条链的最大元或者每条链的最小元，取出某一条链的最大元，记为 x，再找到最小元，使得 y\preceq x，那么 C=\{y,x\} 构成一条链， S-C 的最长反链长度为 m-1，那么它的最小链划分数目就是 m-1，再并上 C 这条链即可。

对偶形式

对于某一有限偏序集，其最长链大小等于最小反链划分中反链的数目。

证明：

记最小反链划分中反链的数目为 s，最长链大小为 t，一定有 s\ge t，我们考虑去取到这个下界。

当 |S|=1 时，显然可以做到 s=t。

当 |S|>1 时，对于当前的集合 S，我们把所有满足以下性质的点都拿出来。

容易发现的是这些点必然相互不可比，记这些点构成的集合为 T，T 为一条反链。同时 S-T 的最长链大小为 t-1，若 S-T=\empty，结论显然成立。反之，由数学归纳法，S-T 最小反链划分中反链的数目为 t-1，又有，一个集合中最小反链划分中反链的数目一定大于等于最长链的大小，所以取 S-T 中的 t-1 条反链，再并上 T 这条反链，就取到了下界。

由该定理出发，我们去探究算法竞赛中一类经典的问题，最长上升子序列问题。

最长上升子序列问题

给定一个序列 A={a_1\dots a_n}，定义集合 S=\{(i,a_i)\mid i\in \mathbb{N} \ 且\ 1\le i\le n\}。定义偏序关系 \preceq\ =\{((i,a_i),(j,a_j))\mid i\le j,a_i\le a_j\}。求偏序集 (S,\preceq) 中的最长链。

1. 一个朴素的 dp 方程为，dp_i 表示以 a_i 结尾的最长链长度是多少。转移很容易，dp_i=\max(dp_j)+1，其中 j<i，a_j<a_i，这是一个二维偏序问题，可以用树状数组在 O(n \log n) 的时间内很轻松的解决。
2. 上述的 dp 方程是在固定结尾元素，最优化链的长度。现在我们换一个方向，我们固定链的长度，最优化结尾元素，dp_i 表示长度为 i 的链，结尾元素最小是多少。不难注意到，dp_i 是单调递增的。每次更新，我们从左向右，找到最后一个小于 a_i 的位置 p，令 dp_{p+1}\leftarrow a_i 即可。

这两种 dp 都可以非常轻松的把最长链给构造出来，但是，如果我要求最小链划分，即确定所有点的集合关系，该如何构造方案呢？

构造方案

给定一个序列 A={a_1\dots a_n}，定义集合 S=\{(i,a_i)\mid i\in \mathbb{N} \ 且\ 1\le i\le n\}。定义偏序关系 \preceq\ =\{((i,a_i),(j,a_j))\mid i\le j,a_i\le a_j\}。求偏序集 (S,\preceq) 中的最小链划分。

在这个问题中，链为不严格上升子序列，反链为严格下降子序列。

最小链划分等于最长反链的大小，我们考虑在求最长反链的过程中构造方案。