Dilworth 定理

Diwanul · 2023-01-12 17:15:03 · 个人记录

Dilworth

定理

偏序集能划分成的最少的全序集个数等于最大反链的大小。

名词解释

偏序

在集合 S 中定义的二元关系 \le，如果它满足以下三个性质：

1. 自反性：\forall x\in S 有 x\le x。
2. 反对称性：\forall x,y\in S，若 x\le y,y\le x，则有 x=y。
3. 传递性：\forall x,y,z\in S，若 x\le y,y\le z，则有 x\le z。

则称 \le 为 S 中的一个偏序关系，(S,\le) 为一个偏序集。

全序集

对于定义在集合 S 上的偏序关系 \le，若集合 T 满足 T\subseteq S，且 \forall x,y\in T 有 x\le y 或者 y\le x 成立，则称 (T,\le) 为一个全序集。

换句话说，全序集就是不包含两个不可比元素的集合。

反链

反链的定义恰恰与全序集相反。

对于定义在集合 S 上的偏序关系 \le，若集合 T 满足 T\subseteq S，且 \forall x,y\in T 有 x\le y 和 y\le x 都不成立，则称 (T,\le) 为一个全序集。

换句话说，反链就是元素两两不可比的集合。

证明

不会，略。以后补。

应用情形

一般多元组集合

考虑最简单的二元组，那么得到的结论就是：导弹拦截可以用最长上升子序列求解。

图论模型

考虑定义 u\le v 当且仅当 u 可以到达 v。对于一个 DAG，发现 \le 是定义在点集 V 上的偏序关系，那么就有最小路径覆盖等于图上最长反链。在某些题目中，这个定理可以将网络流改为贪心，例如网络流 24 题中的魔术球。

这里附上魔术球的做题记录：

首先，答案必然递增。那么可以二分。如何判断是否可行？发现是最小路径覆盖。同一原理的另一种做法是不二分，每次加入一个点，然后继续跑一次网络流（不清空），第一次遇到容器不够的情况时退出。理论复杂度前者优，实际上后者常数很小。另一种思路是贪心，贪心地加入，能加就加，不能加就开新容器。正确性可以证明，利用 Dilworth 定理之类的东西。感性理解的话可以看作某个程度上的模拟网络流。