偏序集反链分解算法

㈠ 最长不降子序列的长度等于不升子序列的数目

这么来说吧
对于一个序列 不断做最长不升序列 每次将结果中的数去掉 这个序列能做多少次 这个次数等于最长不降子序列的长度

以前VIJOS上有道叫 导弹拦截的题要用这个

㈡ 反链的离散数学

设<A>是一个偏序集合，在A的一个子集中，如果每两个元素都是有关系的，则称这个子集为链。在A的一个子集中，如果每两个元素都是无关的，则称这个子集为反链。
我们约定，若A的子集只有单个元素，则这个子集既是链又是反链。
例如A表示一个单位里所有工作人员的集合， 表示领导关系，则<A，>为一偏序集，其中部份工作人员之间有领导关系的组成一个链。还有部份工作人员没有领导关系的组成一个反链。

㈢ noip1999提高组

dilworth定理，最小链划分 = 最长反链。

随便找一本离散数学和组合数学的书都有证明

算法，粘给你吧

导弹拦截是一个经典问题：求一个序列的最长不上升子序列，以及求能最少划分成几组不上升子序列。第一问是经典动态规划，第二问直接的方法是最小路径覆盖，但是二分图匹配的复杂度较高，我们可以将其转化成求最长上升子序列，其最大值即等于不上升子序列的最小划分数。这就涉及到组合数学中偏序集的Dilworth定理。（第二问的贪心方法其实就是这个定理的证明过程）

先介绍一下偏序关系：
偏序是在集合X上的二元关系≤（这只是个抽象符号，不是“小于或等于”），它满足自反性、反对称性和传递性。即，对于X中的任意元素a,b和c，有:
自反性：a≤a;
反对称性：如果a≤b且b≤a，则有a=b;
传递性：如果a≤b且b≤c，则a≤c 。

带有偏序关系的集合称为偏序集。
令(X,≤)是一个偏序集，对于集合中的两个元素a、b，如果有a≤b或者b≤a，则称a和b是可比的，否则a和b不可比。

在X中，对于元素a，如果任意元素b，由b≤a得出b=a，则称a为极小元。
一个反链A是X的一个子集，它的任意两个元素都不能进行比较。
一个链C是X的一个子集，它的任意两个元素都可比。

下面是两个重要定理：
定理1 令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
定理2 令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
虽然这两个定理内容相似，但第一个定理证明要简单一些。此处就只证明定理1。
证明：设p为最少反链个数
(1)先证明X不能划分成小于r个反链。由于r是最大链C的大小，C中任两个元素都可比，因此C中任两个元素都不能属于同一反链。所以p>=r。
(2)设X1＝X，A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A2是X2中极小元的集合，从X2中删除A2得到X3……最终，会有一个Xk非空而X(k+1)为空。于是A1,A2,…,Ak就是X的反链的划分，同时存在链a1<=a2<=…<=ak，其中ai在Ai内。由于r是最长链大小，因此r>=k。由于X被划分成了k个反链，因此r>=k>=p。因此r=p，定理1得证。

回过头来看导弹拦截第二问。我们定义偏序关系≤：a≤b表示a出现不迟于b且a的值不小于b的值。这个偏序集的最长反链即最长上升子序列，它的不上升子序列是偏序集的链。由Dilworth定理可知，不上升子序列的最小划分数＝最长上升子序列的长度。

p.s. 这里的贪心方法是，每次选出所有的在它前面没有大于或等于它的数作为一组。其实我们每次选的是偏序集的最小元，因此我们最终得到的答案就是上面的k。由r<=p及r>=k>=p可以得到r=k=p，因此贪心正确。

㈣ 设偏序集<A，R>，其中A=｛2，3，4，.....，1000｝，R表示整除关系，那么该偏序集的所

{x|x∈A , 500＜x≤1000}

㈤ 设<A,R>为一个偏序集，其中，A={1，2，3，4，6，9，12，24},R是A上的整除关系。

先求出关系矩阵

1 1 1 1 1 1 1 1

0 1 0 1 1 0 1 1

0 0 1 0 1 1 1 1

0 0 0 1 0 0 1 0

0 0 0 0 1 0 1 1

0 0 0 0 0 1 0 1

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1

（1）R出的哈斯图如下：

(5)偏序集反链分解算法扩展阅读：

哈斯图得名于Helmut Hasse；依据Birkhoff，这么叫是因为Hasse有效的利用了它们。但是Hasse不是第一个使用它们的人，它们早就出现在如Vogt (1895)中。尽管哈斯图被设计为手工绘制偏序集合的技术，最近已经使用图绘制技术自动来生成它们了。

术语“哈斯图”还可以称呼作为抽象有向无环图的传递简约，独立于这个图的任何绘制形式。但是这里不采用这种用法。

图中的每个结点表示集合A中的一个元素，结点的位置按它们在偏序中的次序从底向上排列。即对任意a，b属于A，若a≤b且a≠b,则a排在b的下边。如果a≤b且a≠b，且不存在c∈A满足a≤c且c≤b，则在a和b之间连一条线。这样画出的图叫哈斯图，又称偏序集合图。

㈥ 偏序问题

偏序集的两个定理：
定理1> 令(X,≤)是一个有限偏序集,并令r是其最大链的大小,则X可以被划分成r个但不能再少的反链.
其对偶定理称为Dilworth定理：
定理2> 令(X,≤)是一个有限偏序集，并令m是反链的最大的大小,则X可以被划分成m个但不能再少的链.

说二元的吧,三元给你思考的空间
根据定理二,(X,Y,<=)的反链,就是X1<X2 &&Y1>Y2或者X1>X2&&Y1<Y2,他们是对称的,求出哪一个结果都可以.如果是X1<X2 &&Y1>Y2,就是求出point{X,Y}按照x单调递增,y单调递减的最长子序列.
关于如何求最长单调递减(增)子序列,可以参考我的博客(参考资料).

㈦ 用C++实现偏序集的反链分解算法。 求高手解答。

o(）＾）)o 唉，网上就你一个问这个问题的，坐等答案啊

㈧ 对于任意性和存在性问题怎样解释

根据规则对人们行为规定和限定的范围和程度的不同，分强行性规则和任意性规则。 a.强行性规则是指内容规定具有强制性质，不允许人们随便加以更改的法律规则。 b.任意性规则是指规定在一定范围内，允许人们自行选择或者协商确定为与不为、为的方式以及法律关系中的权利义务内容的法律规则。 权利性规则，大多为任意性规则，但也存在强行性规则；职权性规则和义务性规则通常属于强行性规则。存在性定理是一类定性描述。要把某种离散对象按某个确定的约束条件进行安排，如果这种特定的安排是否存在还不确定，就需要首先讨论这种特定安排的存在性问题。是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。