juju527's blog

因为失去，所以明白

Dilworth定理

发布于 2021-07-06 | 分类于 组合数学 、 学习笔记 | 2分钟 | 396字数 | 浏览量：

偏序

偏序集合是指配备了部分排序关系的集合，集合内不一定所有元素都能相互比较

一个偏序集合 SS 应配备一个二元关系 ≤\leq 满足

  • 自反性 ∀a∈S,a≤a\forall a\in S,a\leq a
  • 反对称性 ∀a,b∈S\forall a,b\in S，若 a≤b,b≤aa\leq b,b\leq a，则 a=ba=b
  • 传递性 ∀a,b,c∈S\forall a,b,c\in S，若 a≤b,b≤ca\leq b,b\leq c，则 a≤ca\leq c

我们将 ≤\leq 称为 SS 上的偏序关系，这里的 ≤\leq 不一定是一般意义上的小于等于

可比与不可比

对于一个偏序集合 SS 的偏序关系 ≤\leq，若 a,b∈Sa,b\in S 满足 a≤ba\leq b 或 b≤ab\leq a 则称 a,ba,b 两者可比，否则不可比

具体的例子来说

对于一个二元偏序集合，我们可以定义 (ai,bi)≤(aj,bj)(a_i,b_i)\leq (a_j,b_j) 当且仅当 a_i\leq a_j\and b_i\leq b_j

那么两元素不可比当且仅当 a_i\leq a_j\and b_i>b_j 或者交换 i,ji,j

全序集与反链

对于一个偏序集合 SS，若其满足其中所有元素均可比，则称其为一个全序集/链

对于一个偏序集合 SS，若其满足其中所有元素均不可比，则称其为一个反链

Dilworth定理

偏序集最小链覆盖等于最大反链

证明无，爬了

# 组合数学 # 学习笔记
NOI2021 游记 上一篇
左偏树学习笔记 下一篇
0%