偏序集及Dilworth定理

08/26/2014

很炫酷的东西QQ图片20140826103745

首先我们要了解一下什么是偏序关系:

【注:“≤”在此中的意义为“偏序关系” 而非 “小于等于”,不过不难发现“小于等于”也是一种偏序关系。

设集合X为一个非空集,关系P(≤)为集合X上的一个二元关系,

若关系P满足:

①自反性:a≤a

②反对称性:若a≤b , b≤a , 则a=b。

③传递性 :若a≤b , b≤c , 则a≤c。

那么我们称P(≤)为在集合X上的 偏序关系   ,带有偏序关系的集合我们称为 偏序集  (如X)。

在偏序集中,若存在 a≤b 或者b≤a,那么我们称a与b是可比的。

在偏序集中的元素a,若对于所有与a可比的元素均有a≤b,则称a为偏序集中的极小元

 

举几个偏序关系的栗子:

①小于等于显然是偏序关系!

②整除关系显然也是偏序关系!

③集合间的子集关系是偏序关系!(`·ω·丿)

 

若偏序集X中的一个子集X1满足X1内所有元素都相互可比,那么我们称X1是X中的一条

反之,若子集X2中的所有元素都相互不可比,我们称X2是X的一条反链

 

定理①:对于偏序集(X,≤),若 r 为其最长链的长度,则集合X的最小反链划分为 r 。

其对偶定理即为 Dilworth定理

(定理②) 对于偏序集(X,≤),若 r 为其最长反链的长度,则集合X的最小链划分为 r 。

我们仅需证明定理①成立,对偶定理即成立。

定理①的证明:

 

首先证明r的必要性:

对于最长链中,任意的两个元素都是可比的,因此最长链的任意两个元素都不可以同时存在于一条反链中,因此r条反链是必要的。

其次证明r的充分性:

将集合X中所有的极小元组成集合A,每次剔除集合A,如此反复处理下去,必然每次剔除的集合与上次剔除的集合均有元素满足偏序关系。而当X被剔除至空集后,所有被剔除的集合即为最小链划分,我们设被剔除的集合的个数为k ,由于每个集合之间均有偏序关系的元素,而最长链的长度为r,因此k<=r。

至此,定理①证明完毕。

 

通过这些定理的转化,我们便可以解决或者证明一些奇♂怪的问题啦。

举个例子:

炒鸡经典的入门级DP 导弹拦截  的第二问:“集合X能最少划分为几组不上升子序列?”

按照朴素题意的算法,我们需要求最小路径覆盖。

但是不难看出,这是求一个偏序关系“x先于y出现,且x大于y”的最少链划分,

所以根据定理,我们可以发现这就是求“x先于y出现,且x大于y”的最长反链长度,

即为最长上升子序列的的长度。

因此我们可以以nlgn的复杂度求出答案。

 

更多例题:SPOJ 3196. Divisibility Relation