序理论与dilworth定理

0. 引入

你需要的前置：

1. 一颗清醒的大脑（因为这是抽象的东西）
2. 概念基础辨析
3. 集合（高一数学必修一）

1. 序理论

1.1 定义与二元关系

序理论是研究捕获数学排序的直觉概念的各种二元关系的数学分支。——百度百科

数学排序？这个我会啊，不就是排序吗…？
其实这里并不指的是单独的排序。

既然有不同的点，那么特殊在哪里？
先来一个小定义：

笛卡尔积：设$X,Y$ 两个集合，那么存在一个集合，它的元素是用$X$ 中元素为第一元素，$Y$ 中元素为第二元素组成的有序二元组，称它为集合$X,Y$的笛卡尔积集，记为$X\times Y$。
$X\times Y=\left\{ (a,b)|a\in X,b\in Y \right\}$

怎么理解？类比一下C++中的pair容器吗。

例如$X=\left\{ 1,2 \right\},Y=\left\{ a,b,c \right\}$，那么有$X\times Y=\left\{ (1,a),(1,b),(1,c),(2,a),(2,b),(2,c) \right\}$。

接下来是正式的定义：

二元关系：集合$X$ 与集合$Y$ 上的二元关系是$R=(X,Y,G(R))$，其中$G(R)$，$称为R的图$，是笛卡尔积$X×Y$ 的子集。若$(x,y) \in G(R)$ ，则称$x$ 是$R$ 关系于$y$ ，并记作$x R y$或$R(x,y)$。否则称$x$ 与$y$ 无关系$R$。但经常地我们把关系与其图等同起来，即：若$R⊆X×Y$，则$R$ 是一个关系。

什么？看不懂？没关系我也看不懂www。举个例子吧，例如在$\mathbb{N}_{+}$ 自然数集合上的小于等于关系就是一个二元关系，例如对于$R \Rightarrow \le$，对于$2,3$ 来说是有关系，而对于$3,2$ 来说不行，因为$3\le 2$ 不满足，所以称他们无关系。

到现在应该有一点模糊的理解了吧，那么对于那个图$G$ 怎么说呢？我理解的就是满足$R$ 关系的集合（事实也是这样的，并且这个集合还是类似于一个pair），比如说上面的$(2,3)$ 他就属于$G(R)$，而$(3,2)$ 不属于因为它不满足我们上面提到的 “$R$ ” 关系。

1.2 二元关系的性质

一般来说我们研究关系会研究有没有一些特殊性质。我们对于集合$S$ 上的二元关系$R$ （就是$R⊆S\times S$）定义以下性质：

1. 自反性：$(\forall a\in S),(a,a)\in R$，例如$a\le a,(a\in \mathbb{N}_{+})$。
2. 反自反性：$(a,a) \notin R,(\forall a \in S)$ ，例如$a<a,(a\in \mathbb{N}_+)$就不成立。
3. 对称性：$(a,b)\in R \Leftrightarrow (b,a) \in R,(a,b \in S)$，等于关系。
4. 反对称性：$(a,b),(b,a) \in R,(a,b \in S) \Rightarrow a=b$
5. 传递性：$(a,b)\in R,(b,c) \in R \Rightarrow (a,c) \in R,(a,b,c \in S)$，例如小于等于。

1.3 偏序关系，偏序集与哈斯图

对于二元关系$R\subseteq X\times X$，如果$R$ 有自反性，反对称性，传递性，那么$R$ 就是偏序关系。

而偏序集就是 集合$S$ 与$S$ 上的偏序关系$R$ 构成的，记为$(S,R)$。

例如$S$ 中的元素$x,y$ ，若$(x,y)$ 或$(y,x)$ 在$R$ 关系下成立，那么我们称$x,y$ 可比，反之则不可比。

但是太抽象了，我们需要一个更清晰明了的图。

覆盖元素：对于元素$x$，如果$x<y$ 不存在$z$ 使得有$x<z<y$ 那么我们称$y$ 就是$x$ 的覆盖元素（注意这里的小于号其实是一种关系，不是真的小于！），在哈斯图中连出$x\rightarrow y$ 的有向边，这种关系生成的图叫做哈斯图。

借用Tofu大佬的图：

例如集合$\left\{ 1,2,3,4,6,7，8，9 \right\}$ 上的关系$\left\{ (a,b)|a\text{整除}b \right\}$。左侧图即为：

实际中我们不标注方向，所以一般来说我们将较大的元放在上面，隐式的表达有向。

不难发现这其实是一个DAG(有向无环图)。

对于右面那个图是另外一个东西，我们设定的关系是“属于关系”，可以自己对比以下。

2. Dilworth定理

2.1 定义

我们这里阐述以下链和反链的定义：

设$C$ 是偏序集的一个子集，如果$C$ 中元素互相可比，那么称$C$ 是链。反之互相不可比，那么就是反链。

例如oiwiki的图：下面的关系还是我们的属于关系：

例如$\left\{ \varnothing_,\left\{ 1\right\},\left\{ 1,2\right\} \right\}$，就是一条链，而$\left\{ \left\{ 1\right\},\left\{ 0,2\right\} \right\}$ 就是反链。不难发现这里最长反链长度就是3，我们称最长反链长度为 偏序集$S$ 的宽度。

那么diliworth定理呢？

对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真。

例如下面的整除关系图（tofu大佬orz）：

不难发现最长反链只能是2，而刚好只需要2条链就能覆盖。

证明？自行了解www。

2.2 例题

P1020——导弹拦截

想当年我做这个题的时候我还根本就不知道DilWorth定理是什么。感慨万千

设高度序列为$P=\left\{ x_1,x_2,...,x_n \right\}$，集合$S=\left\{ (i,x_{i)}| i\in N \text{且} 1\le i\le N \right\}$。

那么偏序关系为$R=\left\{ ((i,x_i),(j,p_{j))}| i\le j,x_{i}\ge x_j \right\}$。

这时候$(S,R)$ 构成一个偏序集，具体含义就是$i\le j,x_{i}\ge x_j$ 那么就说明拦截了第$i$ 个导弹后还可以拦截 第$j$ 个导弹。

对于第一问，就是求最长链的长度，对于第二问，最少拦截系统个数？

最少系统个数其实就是要求每一个系统所管束的链最长，这不就是求最小链覆盖吗。

2.3 DAG，二分图转化

dilworth的理解另一个形式，链覆盖与二分图匹配的对应关系。

在一个二分图匹配中，非匹配点一定是链的起点，所以链覆盖集的个数就是非匹配节点的个数，而匹配越大，非匹配点越少。那么就有一个及其强有力的结论：

$$|\text{链覆盖集}|=|V|-|\text{最大匹配}|$$

那怎么用？我们拿一个我想不出来的例题来说：

P12148 【MX-X11-T2】「蓬莱人形 Round 1」所以我放弃了音乐

我们看图，我们把能够访问到的棋子之间从上往下连有向边：

我们对于任意一行，都只能往下取连边不能往左往右连边。

“对于任意……都有唯一……” 这是一个很好的性质，我们可以将它抽象成二分图，这是因为二分图匹配后的每一个匹配点都有唯一一个点与之匹配。

但是我们观察这个，我们变变形：

很像二分图，但其实是k-分图，但是我们可以转成二分图的样式，我们看看题目求什么，要求最小的操作次数…这不就是最小链覆盖吗。

于是就做完了，时间复杂度$O(n)$。实现带$\log$。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=2e6+15;
struct Node{
    int x,y;
}nd[MN];
int n,maxx;
map<pir,int> um;
map<pir,bool> vis;
set<int,greater<int>> s[MN];

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>nd[i].x>>nd[i].y;
        um[pir(nd[i].x,nd[i].y)]=i;
        s[nd[i].x].insert(nd[i].y);
        maxx=max(maxx,nd[i].x);
    }
    int ans=n;
    for(int i=1;i<maxx;i++){
        for(auto p:s[i]){
            if(um[pir(i+1,p+1)]&&!vis[pir(i+1,p+1)]){
                ans--;
                vis[pir(i+1,p+1)]=1;
            }
            else if(um[pir(i+1,p)]&&!vis[pir(i+1,p)]){
                ans--;
                vis[pir(i+1,p)]=1;
            }
            else if(um[pir(i+1,p-1)]&&!vis[pir(i+1,p-1)]){
                ans--;
                vis[pir(i+1,p-1)]=1;
            }
        }
    }
    cout<<ans;
    return 0;
}

回头过来思考这个题，其实这个DAG已经说明满足偏序关系了，关系就是$u\rightarrow v$谁否能够到达。而我们就是要在这个关系上求解最小链覆盖。