偏序与Dilworth定理

[[TOC]]

前言

先从一个具体的问题开始:

一个导弹拦截系统打出的每一发炮弹都不能高于前一发。已知来袭导弹的高度序列为 $a_1,a_2,\cdots,a_n$,最少需要多少套系统才能拦截全部导弹?

一套系统能拦下的导弹高度形成一条不上升子序列,于是问题就变成:把整个序列切分成最少条不上升子序列,这个"最少切分数"是多少。

答案是:它等于序列的最长上升子序列的长度。

直觉上,"最少切分"和"最长某某"似乎是两个完全不相干的问题,但它们的答案居然相等。这个看似巧合的结论背后,是组合数学里一条漂亮的定理:Dilworth 定理。这一章我们先建立"偏序、链、反链"的概念,再证明这条定理,最后回到 OJ 上的应用。

偏序

定义 集合 $P$ 上的一个二元关系 $\preceq$ 叫做偏序关系,如果对任意 $x,y,z \in P$:

1. 自反性:$x \preceq x$
2. 反对称性:若 $x \preceq y$ 且 $y \preceq x$,则 $x = y$
3. 传递性:若 $x \preceq y$ 且 $y \preceq z$,则 $x \preceq z$

$(P,\preceq)$ 就叫做一个偏序集。我们记 $x \prec y$ 表示 $x \preceq y$ 且 $x \neq y$。

两个元素 $x,y$ 如果既没有 $x \preceq y$,也没有 $y \preceq x$,就称 $x$ 与 $y$ 不可比。

链与反链

定义 设 $(P,\preceq)$ 是偏序集。

• 链:集合 $C \subseteq P$,其中任意两个元素都可比。即 $C$ 中的元素可以从小到大排成一列。
• 反链:集合 $A \subseteq P$,其中任意两个元素都不可比。

例如在排列偏序中,一条链就是一个递增子序列,一条反链就是一个递减子序列。

链划分:把 $P$ 分成若干条互不相交的链,使得每个元素恰好属于一条链。

本章要回答的核心问题是:

把一个偏序集划分成链,最少需要多少条链?

一个具体情形:把序列切成最少的递增子序列

在进入一般定理之前,先完整解决排列上的特例。它本身就是一道 OJ 题(导弹拦截的第二问),而且解法可以直接写代码。

问题:给定排列 $a_1,a_2,\cdots,a_n$,把它切分成最少条递增子序列,求最少条数。

贪心:耐心排序

从前往后处理每个数 $x = a_i$,把它放入某一"队"里。每一队必须保持递增,我们只关心每队的队尾(最后一个元素)。

贪心规则:

• 若存在队尾小于 $x$ 的队,则把 $x$ 放入其中队尾最大的那一队;
• 否则新开一队,队尾为 $x$。

贪心的证明

设贪心最终开了 $m$ 队,最长递减子序列的长度为 $LDS$。

方向一:$m \leqslant LDS$。

贪心有一个不变量:各队的队尾从左到右严格递减。

• 新开一队时,新队尾 $x$ 小于所有队尾(否则就存在队尾 $< x$ 的队了),放在最右边,递减性保持。
• 放入某队时,设 $x$ 放入第 $k$ 队,则第 $k-1$ 队的队尾 $\geqslant x$(否则队尾更大的队 $k-1$ 也满足条件,$x$ 不会放第 $k$ 队),且 $x >$ 第 $k$ 队旧队尾,所以替换队尾后递减性保持。

现在建立指针链:每个元素 $x$ 放入第 $k$ 队时($k \geqslant 2$),记录它入队那一刻第 $k-1$ 队的队尾 $y$。由上面知道 $y \geqslant x$(排列中元素两两不同,即 $y > x$),并且 $y$ 是"过去"的元素,在时间上早于 $x$。

从最后一队的队尾出发,沿着指针链往回走:每走一步,值严格变小、时间严格变早。于是得到一条长度恰好为 $m$ 的递减子序列。所以 $LDS \geqslant m$,即 $m \leqslant LDS$。

方向二:$m \geqslant LDS$。

取一条最长递减子序列 $d_1 > d_2 > \cdots > d_{LDS}$。其中任意两个元素 $d_i,d_j$($i<j$)都构成逆序对,所以不可能出现在同一个递增子序列里,也就是不可能同一队。

于是一条递减子序列里的 $LDS$ 个元素分布在至少 $LDS$ 个不同的队中。任何切分方案(包括贪心)的队数都 $\geqslant LDS$,所以 $m \geqslant LDS$。

两个方向合起来:

也就是说,贪心开出的队数就是答案,而且最少递增子序列切分数 = 最长递减子序列长度。

代码实现

用二分维护队尾数组。队尾严格递减,插入时在队尾数组里找第一个队尾 $< x$ 的位置,没有就新开一队:

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

// 把排列切成最少条递增子序列,答案 = 最长递减子序列长度
int main(){
    int n;
    scanf("%d",&n);
    vector<int> tails; // 各队的队尾,严格递减
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        // 找第一个队尾 < x 的队(递减数组上用 greater 的 upper_bound)
        auto it = upper_bound(tails.begin(), tails.end(), x, greater<int>());
        if(it == tails.end())      // 没有队尾 < x 的队,新开一队
            tails.push_back(x);
        else
            *it = x;               // 放入该队,更新队尾
    }
    printf("%d\n", (int)tails.size());
    return 0;
}

时间复杂度 $O(n \log n)$。

Dilworth 定理

序列上的特例证明完了。现在把结论推广到任意有限偏序集。

定理(Dilworth) 设 $(P,\preceq)$ 是有限偏序集,则

特例与它完全一致:链 = 递增子序列,反链 = 递减子序列。

需要的图论工具

Dilworth 的证明要借助二分图里的两条引理。我们先定义相关概念。

二分图:顶点分成左右两部分 $X$ 和 $Y$,每条边连接一个 $X$ 顶点和一个 $Y$ 顶点。

• 匹配:一组两两没有公共端点的边。匹配的大小 = 边的条数,记最大匹配为 $\nu$。
• 顶点覆盖:一个顶点集合,使得每条边至少有一个端点在这个集合里。最小顶点覆盖的大小记为 $\tau$。
• 交替路:依次经过"非匹配边、匹配边、非匹配边、匹配边、……"的路。
• 增广路:两端都是未匹配点的交替路。

引理 1(增广路) 设 $M$ 是一个匹配。若存在一条关于 $M$ 的增广路,则把这条路上每条边的"是否属于 $M$"全部翻转,得到的新匹配大小是 $|M| + 1$。

证明:增广路的两个端点原来都未匹配,翻转后它们被匹配;路径内部每个点原来有恰好一条匹配边与之相连,翻转后仍然恰好一条。整条路上非匹配边比匹配边恰好多 $1$ 条(第一条和最后一条都是非匹配边),所以匹配大小增加 $1$。

因此:最大匹配一定没有增广路,否则还能变大。

引理 2(König 定理) 在二分图里,最大匹配的大小 = 最小顶点覆盖的大小,即 $\nu = \tau$。

证明:任何顶点覆盖的大小都 $\geqslant$ 任何匹配的大小,因为匹配的每条边至少要占用一个不同的覆盖顶点,所以 $\tau \geqslant \nu$。

下面证明 $\tau \leqslant \nu$。设 $M$ 是最大匹配。令 $X_0$ 是 $X$ 中所有未匹配的点,从 $X_0$ 出发走交替路,能到达的 $X$ 侧顶点集合记为 $S$(显然 $X_0 \subseteq S$),能到达的 $Y$ 侧顶点集合记为 $T$。

先观察三个性质:

1. $T$ 中的点都被匹配,而且匹配对象在 $S$ 里:设 $t \in T$,交替路最后一条边是 $S$ 到 $T$ 的非匹配边。若 $t$ 未匹配,这条交替路就是增广路,矛盾。所以 $t$ 被匹配;交替路可以沿这条匹配边继续走到 $t$ 的匹配对象 $x$,故 $x \in S$。
2. 不存在从 $S$ 到 $Y \setminus T$ 的边:设 $s \in S$,边 $(s,y)$。若它是非匹配边,交替路延伸到 $y$,于是 $y \in T$,矛盾;若它是匹配边,则到达 $s$ 的交替路的最后一条边就是 $(y,s)$,于是 $y \in T$,也矛盾。
3. $X \setminus S$ 中的点都被匹配:未匹配的点都在 $X_0 \subseteq S$ 里。

于是 $C = (X \setminus S) \cup T$ 是一个顶点覆盖:与 $X \setminus S$ 相连的边被 $X \setminus S$ 覆盖,其余边由性质 2 知都连着 $T$。

最后算 $C$ 的大小:由性质 1,$T$ 与 $S \setminus X_0$ 通过匹配边一一对应,所以 $|S| = |T| + |X_0|$。而每条匹配边恰好对应一个被匹配的 $X$ 顶点,$|M| = |X| - |X_0|$。于是

即 $\tau \leqslant |M| = \nu$。结合 $\tau \geqslant \nu$ 得 $\tau = \nu$。

Dilworth 定理的证明

设 $n = |P|$。构造一个二分图 $G$:

• 左部是 $P$ 的一份拷贝:$P^- = \{ x^- \mid x \in P \}$;
• 右部是 $P$ 的另一份拷贝:$P^+ = \{ x^+ \mid x \in P \}$;
• 连边 $x^- y^+ \iff x \prec y$。

关键对应一:匹配与链划分。

大小为 $m$ 的匹配 $\iff$ 把 $P$ 划分成 $n - m$ 条链。

• $( \implies )$ 初始把每个元素看作一条单点链,共 $n$ 条。对匹配中每条边 $(x^-,y^+)$,把 $y$ 接到 $x$ 的正上方(因为 $x \prec y$,连接合法)。匹配的左端点两两不同、右端点两两不同,所以每个元素"接到它正上方的人"和"它接的人"都至多一个;且沿着拼接方向元素严格变大,不可能绕出环。每连一条边,链数减一,最终 $n - m$ 条链。
• $( \impliedby )$ 若 $P$ 划分成 $c$ 条链,取每条链里所有相邻元素对,一共 $n - c$ 对。不同链的元素对端点互不相交,且每对都满足 $x \prec y$,所以它们构成大小为 $n - c$ 的匹配。

于是:

关键对应二:顶点覆盖与反链。

设 $C$ 是 $G$ 的一个顶点覆盖,$|C| = s$。令

即两份拷贝都未被覆盖的那些元素。

• $|I| \geqslant n - s$:被覆盖的 $n - |I|$ 个元素每个至少贡献一个被覆盖的拷贝。
• $I$ 是反链:若 $x,y \in I$ 且 $x \prec y$,则边 $(x^-, y^+)$ 的两个端点都未被覆盖,矛盾。

所以 $P$ 中存在大小至少为 $n - s$ 的反链。取 $C$ 为最小顶点覆盖,得

合龙:由 König 定理 $\nu = \tau$,于是

最后一个不等式就是一开始的下界。因此两者相等,Dilworth 定理得证。

Mirsky 定理(对偶)

把"链"与"反链"的角色互换,还有一条对偶的定理:

定理(Mirsky) 把 $P$ 划分成反链的最少条数 = $P$ 中最长链的大小。

这条定理的证明很简单:定义 $h(x)$ 为"以 $x$ 结尾的最长链的长度",把所有 $h$ 值相同的元素放在一起。

• 每一层都是反链:若同一层里 $x \prec y$,则 $h(y) \geqslant h(x) + 1$,矛盾。
• 层数恰好等于最长链的大小 $h_{\max}$。

所以 $h_{\max}$ 层反链覆盖了 $P$;而每条链最多包含每条反链中的一个元素,任何反链划分的条数都 $\geqslant h_{\max}$。得证。

应用

导弹拦截

拦截系统打出的高度序列是一条不上升子序列。定义偏序

则链 = 不上升子序列,反链 = 严格上升子序列。由 Dilworth:

第一问"一套系统最多拦多少"就是最长不上升子序列,一个 O($n \log n$) 模板同时解决两问。

逆序图染色

有一个从排列构造的图:当 $i < j$ 且 $a_i > a_j$ 时,节点 $i$ 与 $j$ 之间有一条边。求给这个图染色,使相邻点颜色不同,最少需要多少种颜色。

• 同色的点之间不能有边,也就是同色的点两两不构成逆序对,按下标排开后值严格递增:每种颜色恰好对应一个递增子序列。
• 于是最少颜色数 = 把排列切成最少条递增子序列的条数 = 最长递减子序列长度。

这正是一开始特例的结论。n 可以到 $10^6$,用上面的 $O(n \log n)$ 贪心即可。

练习题目

• [ roj 1260: 拦截导弹(两问)]
• [ roj 1322: 拦截导弹问题]

参考

• Dilworth’s theorem - Wikipedia
• Kőnig’s theorem (graph theory) - Wikipedia