首页 > 代码库 > dilworth定理的通俗讲解
dilworth定理的通俗讲解
度娘定义：在数学理论中的序理论与组合数学中，Dilworth定理根据序列划分的最小数量的链描述了任何有限偏序集的宽度。其名称取自数学家Robert P. Dilworth。
反链是一种偏序集，其任意两个元素不可比；而链则是一种任意两个元素可比的偏序集。Dilworth定理说明，存在一个反链A与一个将序列划分为链族P的划分，使得划分中链的数量等于集合A的基数。当存在这种情况时，对任何至多能包含来自P中每一个成员一个元素的反链，A一定是此序列中的最大反链。同样地，对于任何最少包含A中的每一个元素的一个链的划分，P也一定是序列可以划分出的最小链族。偏序集的宽度被定义为A与P的共同大小。
另一种Dilworth定理的等价表述是：在有穷偏序集中，任何反链最大元素数目等于任何将集合到链的划分中链的最小数目。一个关于无限偏序集的理论指出，在此种情况下，一个偏序集具有有限的宽度w，当且仅当它可以划分为最少w条链。
归纳性证明
令P为一有限偏序集，理论认为P为空集时显然成立。假设P最少有一个元素，令a为P中的极大值。
根据归纳法，假设存在一整数k，使得偏序集
可以被k个不相交的链
覆盖，且最少存在一个大小为k的反链
。显然，
，
。令
为
的极大值，
，
为
中大小为k的反链，令
，
为包含
的大小为k的反链。确定任意不等的索引
，那么
。令
，根据
的定义，
。因此，由
推断出
。通过交换
，可以得到
。由此得证，A为反链。
现在来讨论P。首先假设，
，
。令K为链
。那么，通过选择
，使得
不包含大小为k的反链。由于
是
中大小为k-1的反链，归纳推出
可以被k-1个不相交的链覆盖。因此，正如所需要证明的，P可以被k个不相交的链覆盖。其次，如果
，
，那么由于a是P的极大值，
为P中大小为k+1的反链。现在，P可以被k+1个链
覆盖。到此，定理全部证明结束。
下面 正文开始（如果你上面的内容看懂了，请给我讲一讲，毕竟我也只是一直来自春田花花幼儿园的蒟蒻）
对于dilworth定理，我的理解就是：
在一个序列中 最长下降子序列的个数就等于其最长不下降子序列的长度
举例：1 2 3 2 3
最长下降子序列：3 2-->长度为2
最长不下降子序列：1 2 3-->长度为3
反之也一样。
那么，你明白了吗？
反正我是明白了
dilworth定理的通俗讲解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。