首页 > 代码库 > Dilworth定理

Dilworth定理

偏序集的两个定理:
定理1) 令(X,≤)是一个有限偏序集,并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理:
定理2) 令(X,≤)是一个有限偏序集,并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

即:链的最少划分数 = 反链的最长长度

1 7 8  2 3 4

反链:最长不上升子序列(如:(7,2))长度 = 2;

即:按升序划分,最少的链划分数为2,为(1,2,3,4)和(7,8)。

参看:
LIS(最长上升子序列)

Dilworth定理