Chlience

【算法】从偏序到Dilworth定理
一些定义偏序集定义集合 $A$ ,如果 $A$ 上的一个二元关系 $\leq$ 满足以下三个条件,我们就称 $\l...
扫描右侧二维码阅读全文
27
2018/12

【算法】从偏序到Dilworth定理

一些定义

偏序集

定义集合 $A$ ,如果 $A$ 上的一个二元关系 $\leq$ 满足以下三个条件,我们就称 $\leq$ 是 $A$ 上的一个偏序关系, $(A,\leq)$ 为一个偏序集:

  1. 自反性: $\forall a\in A, a \leq a$
  2. 反对称性: $\forall a,b\in A,a\leq b,b\leq a\rightarrow a=b$
  3. 传递性: $\forall a,b,c\in A,a\leq b,b\leq c\rightarrow a\leq c$

全序集

设 $\leq$ 为非空集合 $A$ 上的一个偏序关系,如果 $\forall a,b\in A$,都有 $a\leq b$ 或者 $b\leq a$,则称 $\leq$ 为 $A$ 上的一个全序关系,$(A,\leq)$ 为一个全序集或链

通俗的话讲,$A$ 中任意两个元素都是可比的
类似的,偏序集中的两个元素不一定可比

反链

设 $(A,\leq)$ 为一个偏序集,有 $B\in A,\forall a,b\in B,a\not\leq b,b\not\leq a$,我们称 $B$ 为一个反链
最长反链即集合大小最大的反链

Dilworth定理

定义: 偏序集能划分成的最少的全序集个数与最大反链的元素个数相同

证明: 发现貌似没有什么简单的方法

dil1.jpg

dil2.jpg

Problem

BZOJ 1143 [CTSC2008] 祭祀

Last modification:December 27th, 2018 at 09:51 pm

Leave a Comment