【数学】偏序集及其分解定理和应用

设$X$是个非空集合，$X$上有一个二元关系$R$满足自反性、反对称性和传递性，我们就称其为偏序关系。三个性质分别指的是：
1、自反性，指$\forall a,(a,a)\in R$；
2、反对称性，指$(a,b)\in R\wedge (b,a)\in R\Rightarrow a=b$；
3、传递性，指$(a,b)\in R\wedge (b,c)\in R\Rightarrow (a,c)\in R$。
通常一个偏序关系，我们记为$(X,\le )$。偏序集有很多例子，例如正整数$Z$连同它上面的整除关系就是个偏序集，一个集合的所有子集组成的集合连同被包含关系也成为一个偏序集。

给定一个偏序集$(X,\le )$，若对任意$x,y$，有$x\le y\vee y\le x$，则称$\le$是一个全序关系，偏序集$(X,\le )$也称为一个全序集，也称为一条链。一个偏序集$(X,\le )$的子偏序集$(X^{\prime },\le )$如果是全序集，我们也可以称它是偏序集$(X,\le )$的一条链，或者严格来讲，全序子集。如果偏序子集$(X^{\prime },\le )$中的元素两两不可比较，也就是说，对任意$x,y$，$x\le y$与$y\le x$都不成立，则称其为一条反链。

给定一个偏序集$(X,\le )$，其最长链的长度，称为偏序集$(X,\le )$的高度；其最长反链的长度，称为偏序集$(X,\le )$的宽度。

接下来介绍极大元、极小元、最大元、最小元的概念。
偏序集$(X,\le )$，如果有一个元素$x$使得对于任意$a$，若$x\le a$则有$x=a$，则称$x$是这个偏序集的一个极大元。
如果有一个元素$x$使得对于任意$a$，若$a\le x$则有$x=a$，则称$x$是这个偏序集的一个极小元。
如果有一个元素$x$使得对于任意$a$，都有$a\le x$，则称$x$是这个偏序集的最大元。
如果有一个元素$x$使得对于任意$a$，都有$x\le a$，则称$x$是这个偏序集的最小元。

我们可以看出，极大元的意思就是，没有比它更大的了；最大元的意思则是，它比别的所有元素都大。这两个概念是不一样的，因为一个偏序集可能有多个极大元，它们之间两两不能比较。但显而易见的是，最大元一定是极大元。反之不然，一个偏序集可能有极大元，但是没有最大元。一个偏序集如果有最大元的话，则最大元一定是唯一的。对于最小元也是一样。

接下来介绍最最重要的两个分解定理。

定理1：一个偏序集$(X,\le )$的高度为$n$，则存在划分$X={\bigcup }_{i=1}^n{A}_i$使得每个$A_i$都是反链。
证明：数学归纳法。当$n=1$时，说明任意两个元素都不可比较，则$X$本身就是个反链，结论成立；设结论对于$n$也成立。当高度为$n+1$时，首先$X$不可能划分为$n$个反链，否则的话，由鸽巢原理，长度为$n+1$的链必然有两个元素同属于一个反链，这与反链的定义是矛盾的。取$X$的所有极大元组成一个集合$A_1$，则$A_1\ne \varnothing$（链的最大元就是个极大元）。我们考虑$X-A_1$中的链，如果其有长度为$n+1$的链，则其极大元必然也是$X$的极大元，否则$X$的高度就应该大于等于$n+2$，矛盾。所以$X-A_1$的高度是$n$，由归纳假设，其可以分解为$n$个反链，连同$A_1$就是$n+1$个反链，结论成立。这个证明有点BFS拓扑排序的味道，先找入度为$0$的顶点，然后删掉，继续找入度为$0$的顶点，依次下去。找反链的步骤也是这样，先找极大元，然后将其删掉，再继续找极大元。

定理2（Dilworth定理）：设有限偏序集$(X,\le )$的宽度为$m$，则存在划分$X={\bigcup }_{i=1}^m{A}_i$使得每个$A_i$都是链。
证明以后补。

我们来看应用：
对于一个数组$(x_1,x_2,...,x_n)$，我们考虑将其分解为若干个下降子序列的并，这该如何做呢。
为了方便叙述，我们举一个例子，设数组为$A=(4,2,4,5,3,7)$，连同下标在一起，数组为$A=(4_1,2_2,4_3,5_4,3_5,7_6)$。定义序关系为，$a_i\le b_j$当且仅当$a\le b$并且$i\le j$。按照这个序关系的定义，一个数比另一个数小，当且仅当第一个数出现在第二个数左边，并且数值也更小。按照这个序关系，$A$中的最长链就是$(2_2,4_3,5_4,7_6)$，其实也就是$A$中的最长上升子序列。由分解定理，$A$存在四条反链。我们考虑一下这里的反链是个什么意思。对于$A$的某个反链而言，其中两个元素$a_i$和$b_j$不可比较，就意味着它们的数值大小关系和它们的下标大小关系”不对应“，换句话说，如果将它们按照下标由小到大排，那么数值就是由大到小的，也就是说，一个反链就对应了一个（严格）下降子序列。要求反链的话，就要求极大元。这里我们要求四轮极大元。
第一轮，在$(4_1,2_2,4_3,5_4,3_5,7_6)$中，$7_6$是极大元，别的都不是；
第二轮，在$(4_1,2_2,4_3,5_4,3_5)$中，$3_5$和$5_4$都是极大元，别的都不是；
第三轮，在$(4_1,2_2,4_3)$中，$4_3$是极大元，别的都不是；
第四轮，剩下的两个数$(4_1,2_2)$都是极大元。
每轮的极大元都是一个反链，所以得到的四个反链就是$(7_6),(5_4,3_5),(4_3),(4_1,2_2)$。我们发现，其实就是将$A$拆成了四个下降子序列。由分解定理，这是$A$能拆的最多的下降子序列个数了。
反过来想就是这样的，如果一道题目问，一个数组$A$能分拆成的最多严格下降子序列的个数是多少，那么答案就是$A$的最长（不严格）上升子序列的长度。

可以注意到，上述算法就是每次取极大元。接下来考虑求$A$的四个反链的更简单的算法。算法如下：
1、设已经开了若干个反链，遇到新的数的时候，如果它比所有反链的最小值都要大于等于，那么这个数无法接到任何一个已经开的反链上去，则将它自成一个反链；
2、如果遇到的新的数可以接到某个反链后面，那么就挑最小值最小的那条反链接上去。

按照这个算法，求$A$的四个反链的做法就是这样的：
遇到$4_1$，开一个新的反链，$(4_1)$；
遇到$2_2$，可以接上去，得$(4_1,2_2)$；
遇到$4_3$，接不上去，开一个新反链，得$(4_1,2_2),(4_3)$；
遇到$5_4$，接不上去，开一个新反链，得$(4_1,2_2),(4_3),(5_4)$；
遇到$3_5$，可以接到两个数上去，我们挑最小的接上去，得$(4_1,2_2),(4_3,3_5),(5_4)$；
遇到$7_6$，接不上去，开一个新反链，得$(4_1,2_2),(4_3,3_5),(5_4),(7_6)$。
遍历完毕，正好得到四个反链。证明以后补。

接下来考虑严格偏序集的分解定理。$X$上的一个严格偏序$R$，指的是：
1、反自反性，对于任意$a$，$(a,a)\notin R$；
2、非对称性，$(a,b)\in R\Rightarrow (b,a)\notin R$（注意，反对称性和非对称性不是一个意思。反自反性允许$(a,a)\in R$，但是非对称性不允许）；
3、传递性，$(a,b)\in R,(b,c)\in R\Rightarrow (a,c)\in R$。
严格偏序集一般记为$(X,<)$。严格偏序集里也可以定义极大、极小、最大、最小元，极大元指的是没有元素比它“大”（它自己也不比它大），最大元指的是它别的元素都大（除了它自己）。于是，严格偏序集也有链和反链的概念。由于偏序集的分解定理里并没有用到自反性和对称性，所以证明可以直接套用过来用。具体就不叙述了。