网站首页
编程语言
数据库
系统相关
其他分享
编程问答
斯定理
2024-05-29
2024_5_29 狄尔沃斯定理(偏序集)
偏序集中的反链是其元素两两不可比的子集,而链是其元素两两可比的子集。链分解是将偏序集中的元素划分为若干无交的链。狄尔沃斯定理指出,有限偏序集合中,包含元素最多反链的元素数等于包含链数最少的链分解的链数,这个量被定义为该偏序集的宽度。对于任意有限偏序集,其最大反链中元素