离散数学——Dilworth 定理

Qinyao28 · 2024-02-04 20:19:44 · 个人记录

离散数学——Dilworth 定理

2024.2.3~2.4

参考文献
Dilworth 定理

一、概念

1.序

如果对于集合 P 中的任意元素 a,b,c 和关系 \preceq，均满足自反性（a\preceq a）、反对称性（如果 a\preceq b,b\preceq a，那么 a=b）、传递性（如果 a\preceq b,b\preceq c，那么 a\preceq c），则关系 \preceq 为 偏序。此外，满足全序性（a\preceq b 或 b\preceq a，即任两个元素可比较）的关系为 全序。

2.链

一个偏序集中，满足全序关系的集合叫做 链（或全序集合、线性序集合、简单序集合），任两个元素均不满足全序关系的集合称为 反链。

有限偏序集中，元素数最多的链称为 最长链，其元素数为该偏序集的 高度；元素数最多的反链称为 最长反链，其元素数为偏序集的 宽度。

有如下性质：

• 有限非空偏序集 (S,\preceq) 的极大链（不能再添加元素进去的链）一定包含 S 的极大元素（设为 x，则不存在 y\in S,x\preceq y）和极小元素。
• 有限偏序集 S 中的所有极大元素组成的集合，或者所有极小元素组成的集合，是 S 的一条极大反链。

3.传递闭包

在集合 P 上的二元关系 R 的 传递闭包 是包含 R 的 P 上的最小的传递关系。例如，若有向图中的关系为“父子”，则传递闭包是关系“祖先和后代”。

求传递闭包时间复杂度一般为 O(n^3)，类似求最短路的 Floyed 算法枚举中转点和起始结束点。

二、对高度和宽度的限制：Dilworth 定理

1.引入

我们能轻易构造出高度大、宽度小的偏序集如 (\{1,2,\dots,n\},\le)，高度小、宽度大的偏序集如 (\{1,2,\dots,n\},=)，甚至高度大、宽度大的偏序集如 \{(1,1),(1,2),\dots,(1,n),(2,2),(2,3),\dots,(2,n)\}，其关系为当且仅当 x_i=x_j=1 且 y_i<y_j 时 (x_i,y_i)\preceq(x_j,y_j)。尽管我们能将一些较大的偏序集的高度和宽度压低，如大小为 n^2 的偏序集 \{1,2,\dots,n\}^2，其关系为当且仅当 x_i\le x_j 且 y_i=y_j 时 (x_i,y_i)\preceq(x_j,y_j)，它的高度和宽度均为 n；但我们发现任意大的偏序集的高度和宽度不能都很小。

2.定理一

有限偏序集中，（不可重）链覆盖 最小链数 = 最长反链 元素数

用归纳法证明。当偏序集大小为 0 或 1 时，定理成立。设偏序集大小小于 n 时定理成立，下证偏序集大小为 n 时定理成立。

首先，由于链覆盖中每条链最多包含最长反链中的一个元素，所以链数的下限是偏序集宽度。只需要证可以取到这个下限。

设 x 是大小为 n 的偏序集 \{S,\preceq\} 中的极大元素，偏序集 S-\{x\} 的一种最小链覆盖包含链 C_1,C_2,\dots,C_k，a_i 为链 C_i 上可能在反链中的最大元素。对于任两个元素 a_i,a_j，a_j 所在的任一条反链与 C_i 有唯一交点 a_{ik}，且 a_{ik}\preceq a_i，又因为 a_{ik} 和 a_j 不可比，所以 a_i 和 a_j 不可比（否则，如果 a_i\preceq a_j，则 a_{ik}\preceq a_i\preceq a_j 矛盾；如果 a_j\preceq a_i，则再取 a_i 所在的任一条反链与 C_j 相交即可）。所以偏序集 A'=\{a_1,a_2,\dots,a_k\} 是一条最长反链。考虑将 x 添加进去。

• 若 x 与 A' 中任一元素不可比，则 A'\cup\{x\} 是一条最长反链，让 x 单独为一条链，此时链数等于最长反链数。
• 若 x 与 A' 中某些元素可比，不妨 x\succeq a_i，设 C_i 上所有可能在反链中的点为 a_{i1},a_{i2}\dots，则 \{x,a_{i1},a_{i2},\dots\} 是一条链，设为 C，则 S-C 的最长反链可由 S 的最长反链去掉 C 中的一个元素所得，所以 S-C 的宽度为 k-1。进而，设 S-C 的一种最小链覆盖的链为 C_1',C_2',\dots,C_{k-1}'，那么 C_1',C_2',\dots,C_{k-1}',C 是 S 的一种最小链覆盖，所以 S 的宽度不可能超过 k，A' 是最长反链，链数也等于最长反链数。

3.对偶形式：定理二

有限偏序集中，（不可重）反链覆盖 最小链数 = 最长链 元素数

4.与 DAG 的联系

把 DAG 上的点集当成偏序集，点的 “可达性” 当成偏序关系，那么这个偏序集上的最小链覆盖就是 DAG 上的最小 可重 路径覆盖（要求覆盖所有点）。对 DAG 求传递闭包后，求最小可重路径覆盖等价于求最小不可重路径覆盖。

5.题目

法克；祭祀；