偏序集中的反链是其元素两两不可比的子集,而链是其元素两两可比的子集。链分解是将偏序集中的元素划分为若干无交的链。狄尔沃斯定理指出,有限偏序集合中,包含元素最多反链的元素数等于包含链数最少的链分解的链数,这个量被定义为该偏序集的宽度。
对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真,它断言:对于任意有限偏序集,其最长链中元素的数目必等于其最小反链划分中反链的数目。
标签:斯定理,偏序,狄尔沃,元素,2024,反链,数目 From: https://www.cnblogs.com/lprdsb/p/18220579