序理论
感谢Meatherm在之前的讲课，才让我有机会思考这以理论
简介
序理论对二元关系的研究在图论、数学、动规等OI常见板块中都有应用，可以说，这些关于次序的思考及它们所拥有的性质都是美妙的。这种「次序」，在元素与元素之间连结了隐形的线，却又编织起严密的网，织构出由此推出的万千理论。
概念
下面以并不严谨的角度解释一些概念
二元关系
不论全序还是偏序，都注重「序」。那么简单的，我们可以试图表示出它们的 关系（真实的关系可以是复杂的，但研究 \(\le、<\) 会便于理解，所以下文可能以 \(\le、<\) 举例偏多），以体现序。
首先，我们先明确需要确定序的关系的对象，譬如我们拿出一个集合 \(P\) 中的对象 \(x、y、z\)。
还是先探讨在集合 \(P\) 上的关系 \(R\)，对于关系 \(R\) 的一些优美的性质被定义如下：
- 若 \(x\,R\,x\)，则称 \(R\) 是 自反 的（如 \(\le\)）。
- 若 \(x\,R\,x\) 不成立时，则称 \(R\) 是 反自反 的（如 \(<\)）。
- 若 \(x\,R\,y\to y\,R\,x\)，则称 \(R\) 是 对称 的（如 \(\not=、\equiv\)）。
- 若 \(x\,R\,y\) 且 \(y\,R\,x\) 要成立，那么必须满足 \(x=y\)，则称 \(R\) 是 反对称 的（如 \(\le\)）。也表述为不存在 \(x、y\) 同时满足 \(x\not= y\and xRy\and yRx\)，因为要某些关系 \(R\)（如 \(<\)）满足 \(x<y\) 且 \(y<x\) 本身就不可能；
- 若 \(x\,R\,y、y\,R\,z\to x\,R\,z\)，则称 \(R\) 是 传递 的（如 \(\le\)）。
注意：套用定义发现，一些关系既是对称也是反对称的（如 \(=\)）。
偏序关系、全序关系
非严格 偏序关系即为满足自反、反对称和传递性的关系。严格 偏序则满足反自反、反对称和传递性。而满足偏序关系的集合称 偏序集合。由一个集合 \(P\) 及其上定义的偏序关系 \(R\) 组成的偏序集 \((P,R)\) 按严格与否记作 \((P,\prec)\) 或 \((P,\preceq)\)。
当然，\(x\) 和 \(y\) 可能满足不了二元关系 \(R\)（比如 \(R\) 为整除关系 \(|\) 时，我们可以有 \(2|4\)，但 \(2、3\) 既没有 \(2|3\)，也没有 \(3|2\)）。所以我们称只有 \(x\,R\,y\) 或 \(y\,R\,x\) 时两个元素才 可比。所以我们在讨论元素间的（严格）小于关系时一定基于元素间可比。
对于 \(x\prec y\) 且不存在满足 \(x\prec z\prec y\) 的 \(z\) 时，我们又可以说 \(y\) 覆盖 了 \(x\)。
当任意两个集合元素都满足 \(x\,R\,y\) 或 \(y\,R\,x\) 时，称关系 \(R\) 满足 全序 性，这样的集合是 全序集合。
偏序集
我们现在转而探讨一个 偏序集 \((X,R)\) 中的对象 \(x、y\)。
- 若不存在 \(y\) 满足 \(y\,R\,x\)，则称 \(x\) 是其 极小元（如 \((R,>)\) 中，\(\infin\) 就是极小元）。
- 最小元：任意 \(y\) 都有 \(x\,R\,y\)，则称 \(x\) 是其最小元。
- 若不存在 \(y\) 满足 \(x\,R\,y\)，则称 \(x\) 是其 极大元（如 \((R,<)\) 中，\(\infin\) 就是极大元）。
- 最大元：任意 \(y\) 都有 \(y\,R\,x\)，则称 \(x\) 是其最大元。
注意：极大元和极小元可能不止一个，因为当其他元素与其不可比时也满足定义，最大元和最小元则可能不存在，存在则一定唯一，并且与其他任意元素可比。
- 若集合 \(X^{′}⊆X\) 满足 \(X'\) 中任意两个元素均可比，则称 \(X^′\) 是 \((X, R)\) 上的链。（没错，全序集合也称链）
- 若集合 \(X^′⊆X\) 满足 \(X^′\) 中任意两个元素均不可比，则称 \(X^′\) 是 \((X, R)\) 上的反链。
注意：部分可比部分不可比的什么都不是。只有一个元素的集合既是链又是反链。
- 若集合 \(X\) 上的链构成的集合 \(S = {S_1, S_2, · · · , S_k}\) 满足 \(∀x∈X, ∃1≤i≤k\) 使得 \(x ∈ S_i\)，则称 \(S\) 是 \((X, R)\) 上的 链覆盖。（把每个元素都至少归入了一个链）
- 若 \(S_i,S_j\) 两两不交，则称 \(S\) 是 \((X, R)\) 上的 链划分。称 \(|S|\) 是链覆盖/划分的大小。（把每个元素仅划入一个链）。自然地，最小链覆盖大小等于最小链划分大小。
其实这样的命名可以很自然地移植在DAG里，“链”这样的定义惊人地契合，而最小最大元则如同超级源汇点。我初学时有这样一种yy：譬如在DAG中，我们以节点表示元素，有向边 \((u,v)\) 表示偏序关系 \(u\preceq v\) ，或者说，满足 \(u\,R\,v\) 的话，DAG就描述了一个偏序集合（省去自环），并能很好地反映关键信息。以 \(R\) 表示整除关系（是的，整除是一种经典的偏序关系）为例：
我们可以直观地得到没有入度的点 \(2、3\) 就是极小元，而没有出度的点 \(12、64\) 则是极大元。如果添加 \(1、198\)，那么就有了最大元 \(198\) 和最小元 \(1\)。任意一条链就是“链”，构成一个全序集合，如 \(\{2,6,12\}\)。同时，绿链和橙链构成了最小链覆盖。任意两两没有连边的元素集合就能构成一条反链，如 \(\{6, 4\}\)。蓝线则是传递性作用下的“前向边”（直连 \(k\) 级孩子）。
而实际上，确实有与之相近的一种表示方法，称 哈斯图。
在哈斯图中，我们引入“引力”，默认偏序关系中“小”的在下，“大”的在上，只有满足 \(y\) 覆盖 \(x\) 时（即省去蓝边）才在 \(y\) 与 \(x\) 之间连 无向边（因为偏序关系反对称，一定单向，所以这时所有箭头都朝上了，可以忽略不画。）。
继续套用整除关系的上例，我们得到如下哈斯图：
而在哈斯图中，我们可以更简单地找到一条反链：横向的没有关联的一条线。
再来看链和反链几个显然的关系：
- 对于任意反链 \(A\) 和链 \(C\)，\(|A∩C|≤1\)，即任意链仅包含某个反链中的最多一个 元素，任意反链仅包含某个链中的最多一个元素；
- 向偏序集中加入一个元素，或从偏序集中删除一个元素，最大链、最小链划分、最大反链和最小反链划分的大小至多变化 \(1\)。
于是就有了：
如果 \((X, R)\) 上存在一个大小为 \(r\) 的链，因为其反链划分中每一条反链最多包含这条链中的一个元素，所以其反链覆盖大小不小于 \(r\)。对于大小为 \(r\) 的反链，我们能够得到类似的对偶结论：
偏序集最小反链划分大小不小于偏序集最大链大小，偏序集最小链划分大小不小于偏序集最大反链大小。
Dilworth定理
说实话，这篇文章前面那么多就是为着这个定理铺垫的，OI中似乎只用得到这么多（逃。
定义
- 偏序集的最小链划分大小等于其最大反链大小。（Dilworth 定理）
- 偏序集的最小反链划分大小等于其最大链大小。（Dilworth 定理的对偶情形）
证明
首先考虑其对偶情形。我们找到偏序集中的极小元，不难发现这些极小元构成了一个反链。删去这些极小元，偏序集中的最大链大小恰好减少 \(1\)。因此，重复 \(k\) 次我们就得到了一个等于偏序集最大链大小的最小反链划分。
对于Dilworth定理，考虑对其施以归纳法，证明 \(|X| = n\) 时的偏序集满足条件。
\(n=1\) 的情形是显然的。如果 \(|X|=n−1\) 的情形成立，不妨考虑取走 \((X, R)\) 中的某个最小元 \(c\)，则 \((X\setminus c, R)\) 的最小链划分大小等于其最大反链大小。不妨设其大小为 \(k\)，现在的最小链划分为 \(S={S_1, S_2, · · · , S_k}\)，且存在 \(m\) 条最大反链 \(T1_, T_2, · · · , T_m\)，每一个 \(T_i\) 大小都为 \(k\)。
我们发现，\(T_i\) 是在每一个 \(S_j\) 中恰好取一个元素而构成的。设 \(A_i\) 表示，\(S_i\) 中被某个 \(T_j\) 取走过的最大元素。因为链上元素两两可比，于是总是存在一个最大元素。
进一步的观察可以得知，\({A_1, A_2, · · · , A_n}\) 是一个反链。如果存在 \(i= ̸j\) 使得 \(A_iRA_j\)，那么考虑在链 \(S_j\) 取走了 \(A_j\) 的反链 \(T_l\)，一定会在链 \(S_i\) 中取走某个元素 \(e\) 使得 \(eRA_i\)，因为 \(A_i\) 是被取走过的最大元素。那么有 \(eRA_j\)，这和反链的定义矛盾。
现在考虑将这个最小元 \(c\) 放回到偏序集中。分为两种情况：
- 若 \(c\) 与任意 \(A_i\) 不可比，则 \({A_1, A_2, · · · , A_k, c}\) 是一个大小为 \(n+1\) 的反链。因此，\((X, R)\) 的最小链划分大小 \(≥ k+1\)。向 \((X\setminus c,R)\) 中加入 \(c\) 得到 \((X, R)\) 的过程中，最小链划分和最大反链大小不会增加超过 \(1\)，也即不会大于 \(k+1\)，因此二者都等于 \(k+1\)。
- 若 \(c\) 和某个 \(A_i\) 可比，则偏序集的最小链划分大小不变，为 \(k\)。因为偏序集的最小链划分大小不小于最大反链大小，同时最大反链大小不会减小，因此最大反链大小亦等于 \(k\)。
综上，我们完成了 Dilworth 定理的证明。
应用
老生常谈的，用于优化 1999年NOIP普及组 导弹拦截 的第二问：求正整数序列 \(a\) 的最小不上升子序列划分大小。
第二问可以通过求 最长上升子序列长度 解决。这里只以偏序集的角度证明一遍：一个最长不上升子序列其实就是数组下标集合中满足严格偏序关系 \(R\) ：\(x<y,a_x\ge a_y\) 的元素组成的一条链。在此偏序 \(R\) 下，一条反链集合中的元素就必然不可比，即 \(x<y\) 时必须有 \(a_x<a_y\)。所以最大反链大小就是最长上升子序列长度。
推广来说，我们通常可以构造出关系 \(R'\) 满足在 \(R\) 关系上是反链的集合在 \(R'\) 关系上就是链，这样求 \(R\) 上的最小链划分可以方便地转化为求 \(R'\) 关系上的最大链大小。