偏序集，哈斯图与Dilworth定理

· · 题解

本文章主要讨论偏序集的定义，如何由偏序集得到哈斯图，以及相关的 Dilworth 定理，忽略了一些关系不大的知识。

偏序集

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

下面介绍什么是偏序关系。

偏序关系

对于二元关系 R⊆S×S ，如果 R 是自反的，反对称的，传递的，那么 R 称为偏序关系。

自反性

a≤a$，$∀a∈S

反对称性

∀a$，$b∈S$，若 $a≤b$ 且 $b≤a$，则 $a=b

传递性

∀a$，$b$，$c∈P$，若 $a≤b$ 且 $b≤c$，则 $a≤c

注意： ≤ 符号是偏序关系的符号，并不是“小于等于”的意思，但“小于等于”也是一个偏序关系，一个典型偏序集的例子便是 (Z,≤)，Z 表示整数集。

对于 S 中的元素 a，b。如果 a≤b 或 b≤a，则称 a ，b 可比，反之则不可比。 请记住元素可比的概念，这在后面讨论链会再次出现。

以上是偏序集的数学定义，过于抽象，为了更好理解偏序关系，我们引入哈斯图。

哈斯图（ Hasse 图）

定义

对于元素 x，如果 x<y 且不存在 z 使得 x<z<y，那么 y 就是 x 的覆盖元素，在哈斯图中连出一条 x->y 的有向边。通过覆盖关系生成的图就是哈斯图。

例如，集合 \{ 1, 2 ,3, 4, 6, 8, 12 \} 上的关系 { (a,b) | a 整除 b } 画出的哈斯图就是

看起来哈斯图并不是有向图，这是否与上面所说的违背？

其实不然，在哈斯图中，把较大元放在较小元的上方，以此来隐式地表示有向。

性质

由于偏序关系满足反对称性，所以哈斯图中一定不能出现回路。

不难发现，哈斯图是一个有向无环图( DAG )！

一个经典的应用就是拓扑排序：从偏序构造一个相容的全序。相关内容在此不再赘述。

接下来给出一个定理。

Dilworth 定理

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

补充一下对链和反链的定义：

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

这个定义非常形象，链对应到哈斯图上就是一条从下至上的 “链”（有向路径）。

以上面的哈斯图为例，红圈就是一条链，蓝圈就是一条反链。

在这个图中，反链元素个数最多是 2 ，而且，整个图至少需要 2 条链 ( \{ 1, 2, 4, 8\} 和 \{ 3, 6, 12\} ) 来覆盖。

通过观察哈斯图，我们可以直观地发现 Dilworth 定理成立。

严格的数学证明如下：

设有限偏序集 (S,≤) , 有 |S|=n，对 n 进行归纳。

当 n=1 时，显然，链划分=宽度=1。

假设该命题对于 n≤k 时均成立，下面证明 n=k+1 时也成立：

设 A 是一条最长反链，记为 A={\{a1,a2,...,aw\}}，定义

D(A)={\{x\mid∃a∈A(x<a)}\} U(A)=\{{x\mid∃a∈A(a<x)}\}

则 S=A∪D(A)∪U(A)

  1. 存在最长反链 A 使得 D(A) 和 U(A) 均不为空。因为 A 是 S 的最长反链，所以 A 也是 A∪D(A) 的最长反链，由归纳假设： A∪D(A) 可以划分为 c_1,c_2,...,c_w 共 w 条链，其中 c_i 的极大元是 a_i。同理， A∪U(A) 也可以划分为 d_1,d_2,...,d_w 共 w 条链，其中 d_i 的极小元是 a_i。于是 S 可以划分为 c_1∪d_1,c_2∪d_2,...,c_w∪d_w 共 w 条链。
  2. 对于每一个最长反链 A 都有 D(A) 或 U(A) 为空。那么每条反链 A 要么构成全上界，要么构成全下界。在 S 中选择一个极大元 y ，再选择一个满足 x≤y 的极小元 x ， \{x , y\} 必构成一条链 C ，且 x 一定包含在全下界， y 一定包含在全上界，因此 S-C 中每个最长反链的元素个数都较 S 减去 1 ， S-C 的宽度是 w-1。应用归纳假设， S-C 可划分为 w-1 条链，再加上 C 得到 w 条链。

归纳证明完毕。

例题

P1020 [NOIP1999 普及组] 导弹拦截

多年后看到这题感慨颇丰

如何在这道题里应用偏序集有关知识？

不妨先构造出偏序集。

假设导弹高度序列为 P=\{{p_1,p_2,...,p_n}\}，记集合 S=\{(i,p_i) \mid i∈N 且 1≤i≤n\}，偏序关系 R=\{((i,p_i),(j,p_j))\mid i≤j 且 p_i≥p_j\}。(S,R) 构成一个偏序集。

具体含义就是：第 i 个导弹高度为 p_i ，第 j 个导弹高度为 p_j ，如果 i<=j 且 p_i>=p_j ，那么说明拦截了第 i 个导弹后可以拦截第 j 个导弹。（这个定义和逆序对非常类似）

画出偏序集对应的哈斯图，对于第一问，很明显，我们需要求出最长链的长度。

关键的问题是第二问：最少的拦截系统个数？

不妨把每一个拦截系统拦截的导弹看作一个集合，那么就是若干个链，题目就转化为了至少需要几条链才能覆盖哈斯图？

这正好是 Dilworth 定理！

求出最大反链即可。

一个巧妙的做法就是将偏序关系置反，再次求一次最长链。

最近发现导弹拦截是一题研究 Dilworth 定理的好题，以往题解很少给出相关证明，仅仅给出做法，借此机会发一篇文章好好讲一下，感谢阅读。