定理1> 令(X,≤)是一个有限偏序集,并令r是其最大链的大小,则X可以被划分成r个但不能再少的反链.
其对偶定理称为Dilworth定理：
定理2> 令(X,≤)是一个有限偏序集，并令m是反链的最大的大小,则X可以被划分成m个但不能再少的链.最后：链的最少划分数=反链的最长长度
用二分图方法求最小路径覆盖，即可
本文共 226 字，大约阅读时间需要 1 分钟。
定理1> 令(X,≤)是一个有限偏序集,并令r是其最大链的大小,则X可以被划分成r个但不能再少的反链.
其对偶定理称为Dilworth定理：
定理2> 令(X,≤)是一个有限偏序集，并令m是反链的最大的大小,则X可以被划分成m个但不能再少的链.最后：链的最少划分数=反链的最长长度
用二分图方法求最小路径覆盖，即可
转载于:https://www.cnblogs.com/zhaozhe/archive/2011/08/10/2133774.html