偏序集
对于一个偏序集 \(D\) ，我们有一些定义
- 比较:定义 \(D\) 中的两个元素 \(X,Y\) ，如果 $\forall i, X_i <= Y_i $ ，则称 \(X,Y\) 两个元素可比，且 \(X\) 小于等于 \(Y\) 。
- 链：对于一个 \(D\) 的子集 \(C\) , 若 \(C\) 中的任意元素都可比，那么 \(C\) 构成了一个链。
- 反链：对于一个 \(D\) 的子集 \(C\) ，若 \(C\) 中的员孙都不可比，那么 \(C\) 构成了一个反链。
- 链覆盖（链划分）：把 \(D\) 划分成互不相交的若干个链
- 反链覆盖（反链划分）：把 \(D\) 划分成互不相交的若干个反链
- 最长链:选出一个链使得 \(|C|\) 最大
- 最长反链:选出一个反链使得 \(|C|\) 最大
参考博客——Dilworth 定理
标签：偏序,定理,划分,子集,Dilworth,反链 From： https://www.cnblogs.com/sky-light/p/17132998.html