狄尔沃斯定理(Dilworth's theorem)亦称偏序集分解定理，其定义是：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。对偶形式也成立：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目。
我自己的理解是：对于一个偏序集来说，最大反链的元素个数等于划分成全序集最小个数。
以洛谷P1020为例，求解一套导弹拦截系统最多能拦截导弹的数量，这个其实就是一个简单的LIS；而求解需要多少个导弹拦截系统，就使用Dilworth定理，所有发射的导弹高度构成一个偏序集，导弹链接系统的数量就是全序集的个数，每一个导弹拦截系统下一次拦截高度都不能高于前一次拦截的高度，所以，其反链就是最长不严格上升子序列。
狄尔沃斯定理(Dilworth's theorem)亦称偏序集分解定理，其定义是：对于任意有限偏序集，其最大反链中...
威尔逊定理、欧拉定理、孙子定理、费马小定理
1 1、切线定理 2、切线长定理 3、切割线定理 4割线定理 5、垂弦定理 6...
1 1、切割线定理 2、切线定理 3、相交弦定理 4、弦切角定理 4、射影定理 5...
勾股定理 （1）叙述并证明勾股定理。 （2）叙述并证明勾股定理的逆定理。 【解答】 勾股定理的文字表述如下：直角三...
2.2 广义动量定理的由来 2.2.1 广义动量定理与动量定理 广义动量定理是对动量定理的扩展，以下为动量定理的推...
圆幂定理，包含了相交弦定理，切割线定理，以及割线定理三种情形。但三种情形十分类似，因此统称圆幂定理。 相交弦定理 ...
毕达哥拉斯定理： 余弦定理： 毕达哥拉斯定理为余弦定理的特殊情况（当γ为90°的时候）。
圆幂定理 定理1(相交弦定理) 如下图，的两弦交圆内于，那么 定理2(割线定理) 如下图，的两弦的延长线(或反向延...
文中所用的统计学定理的简要参考： Bernstein和Cramer定理 Basu定理
本文标题：Dilworth定理
本文链接：https://www.haomeiwen.com/subject/tldlyhtx.html
网友评论