当前位置：首页 > news >正文

Dilworth定理

news 2025/9/4 9:22:32

偏序关系

设 $R$ 是集合 $A$ 的一个二元关系，若 $R$ 满足：
1.自反性: $∀x∈A\forall x \in A$ ，有 $x R x$
2.反对称性： $∀x,y∈A\forall x,y \in A$ ，若 $x R y, y R x$ ，则 $x = y$
3.传递性： $∀x,y,z∈A\forall x,y,z\in A$ ，若 $x R y, y R z$ ，则 $x R z$

则称 $R$ 为 $A$ 上的偏序关系，通常记作 $⪯\preceq$

偏序集

偏序集合（Partially ordered set，Poset）是数学中，特别是序理论中，指配备了偏序关系的集合

链

设若干元素构成一个集合，那么这个集合是链当且仅当这个集合的所有元素两两可比

反链

对一个集合，它是反链当且仅当这个集合里的元素两两不可比

极大元

设偏序集 $A$ ， $x∈Ax\in A$ ， $∄y∈A,x≠y,s.t.x⪯y\not\exists y\in A,x\neq y, s.t.\ x\preceq y$ ,则 $x$ 为极大元

Dilworth定理

设 $P$ 是一个有限的偏序集，则
$min⁡{m∣∃链C1,C2,⋯,Cm,P=∪i=1mCi}=max⁡{∣A∣:A是反链}\min\left\{m|\exists 链C_1,C_2,\cdots,C_m,P = \cup_{i=1}^{m}C_i\right\}=\max\left\{\left|A\right|:A是反链\right\}$

偏序集能划分成的最少的链的个数与最大反链的元素个数相等

证明：
首先证明 $max⁡{∣A∣}≤min⁡{m}\max\left\{\left|A\right|\right\}\le \min\left\{m\right\}$
假设 $max⁡{∣A∣}>min⁡{m}\max\left\{\left|A\right|\right\}> \min\left\{m\right\}$
存在 $∃x,y∈A,s.t.x,y∈Ci\exists x,y \in A,s.t.\ x,y\in C_i$
说明 $x, y$ 是可比的，与反链定义矛盾

同时我们也可以得出 $∣Ci∩A∣=1\left|C_i\cap A\right| = 1$

接着我们对 $∣P∣\left|P\right|$ 进行归纳，来证明可以取等
当 $∣P∣=0,1\left|P\right| = 0,1$ 时，显然成立
假设 $∣P∣=k\left|P\right| = k$ 时成立
当 $∣P∣=k+1\left|P\right| = k + 1$ 时
设最大反链长度是 $m$
最长的链是 $C={x1,x2,⋯,xp}C=\left\{x_1,x_2,\cdots, x_p\right\}$ ，满足 $x1⪯x2⪯⋯⪯xpx_1 \preceq x_2\preceq \cdots \preceq x_p$
换句话说我们不能再往 $C$ 中增加元素，也可以得出 $x_p$ 是极大元

接下来分类讨论
当 $P\CP\backslash C$ 的每一条反链都的元素个数 $≤m−1\le m-1$
由于 $∣P\C∣<k\left|P\backslash C\right| <k$ ，由归纳 $P\CP\backslash C$ 可以划分为 $m - 1$ 个链，即 $P\C=∪i=1mCiP\backslash C = \cup_{i=1}^{m}C_i$
那么 $P$ 可以划分为 $C\cup \cup_{i=1}^{m}C_i$ ，结论成立

当 $P\CP\backslash C$ 中存在反链 $\left\{a_1,a_2,\cdots,a_m\right\}$ 时

令
$P−={x∈P∣∃i,x⪯ai}P+={x∈P∣∃i,ai⪯x}P^{-} = \left\{x\in P\mid \exists i ,x \preceq a_i\right\}\\ P^{+} = \left\{x\in P\mid \exists i ,a_i\preceq x\right\}\\$

我们可以得出
1. $P^{-} \cup P^{+}$ （否则存在元素与反链中的元素不可比，则这条反链不是最大的，矛盾）
2. $P−∩P+=AP^{-}\cap P^{+} = A$ （因为 $ai⪯aia_i \preceq a_i$ ,所以 $ai∈P−,ai∈P+a_i \in P^{-},a_i \in P^{+}$ ）
3. $xp∉P−x_p \notin P^{-}$ (反则 $x_p$ 不是极大元)

$A$ 是 $P^{-}$ 的一条最大反链，由归纳 $P^{-}$ 可以划分为 $m$ 条链 $C1−1,C2−,⋯,Cm−C_1^{-1},C_2^{-},\cdots, C_m^{-}$
由于 $∣A∩Ci−∣=1\left|A\cap C_i^{-}\right| = 1$ ，不妨假设 $ai∈Ci−a_i \in C_i^{-}$
我们可以得出， $a_i$ 是 $C_i^{-}$ 的最大元
（否则,不妨假设 $x∈Ci−x\in C_i^{-}$ 满足 $ai⪯xa_i \preceq x$ ，由于 $\in P^{-}$ ， $∃aj,s.t.x⪯aj(ai≠aj)\exists a_j,s.t.\ x\preceq a_j(a_i\neq a_j)$ ,进而 $ai⪯x⪯aja_i \preceq x \preceq a_j$ ,与反链定义矛盾）

同理 $P^{+}$ 也可以划分为 $C1+,C2+,⋯,Cm+C_1^{+},C_2^{+},\cdots,C_m^{+}$ ， $a_i$ 是 $C_i^+$ 的极小元
令 $Ci=Ci−∪Ci+C_i = C_i^{-} \cup C_i^+$ ,则 $P$ 可以划分为 $C1,C2,⋯,CmC_1, C_2,\cdots, C_m$ 这 $m$ 条链
得证

洛谷P1020

最长不上升子序列
设 $[a_1,a_2,\cdots, a_n]$
定义偏序关系 $ai⪯aj⇔i≤j且ai≥aja_i \preceq a_j \Leftrightarrow i\le j 且 a_i \ge a_j$ （容易验证满足偏序关系）

这个偏序关系就对应了最长不上升序列
最长不上升序列就是在求最长的链
划分最长不上升序列的个数最少为最长上升子序列长度

#include<cstdio>
#include<algorithm>
#include<functional>const int N = 1e5 + 5;int dp1[N];
int dp2[N];int main() {bool flag = false;int t, idx, ans1 = 1, ans2 = 1;while (~scanf("%d", &t)) {if (!flag) {flag = true;dp1[1] = dp2[1] = t;continue;}if (dp1[ans1] >= t) {++ans1;dp1[ans1] = t;}else {int idx = std::upper_bound(dp1 + 1, dp1 + 1 + ans1, t, std::greater<int>()) - dp1;dp1[idx] = t;}if (t > dp2[ans2]) {++ans2;dp2[ans2] = t;}else {int idx = std::lower_bound(dp2 + 1, dp2 + 1 + ans2, t) - dp2;dp2[idx] = t;}}printf("%d\n%d\n", ans1, ans2);return 0;
}

https://www.cnblogs.com/itlqs/p/6636222.html
https://cmwqf.github.io/2019/12/17/%E6%B5%85%E8%B0%88Dilworth%E5%AE%9A%E7%90%86/
https://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class14.pdf

查看全文

http://www.lryc.cn/news/14756.html