序理论

引入

序理论是利用二元关系来将「次序」这一概念严格化的数学分支，下面将介绍这一分支的基本定义。

定义

二元关系

定义

集合和集合上的一个 二元关系（binary relation）定义为元组，其中称为定义域（domain），称为陪域（codomain）， $G(R)\subseteq X\times Y=\{(x,y):x\in X,y\in Y\}$ 称为二元关系的图（graph）。成立当且仅当 $(x,y)\in G(R)$ 。

若，则称该二元关系为齐次二元关系（homogeneous relation）或内关系（endorelation）。

若没有特别说明，下文中的二元关系均为齐次二元关系。

例如 $\mathbf{N}_+$ 上的整除 $\mid$ 和小于等于 $\leq$ 均为二元关系。

我们研究二元关系时，往往会关注其是否具有一些特别的性质。对集合上的二元关系，我们定义如下特殊性质：

自反性（reflexive）： $(\forall~a \in S)~~aRa$ ，
反自反性（irreflexive，anti-reflexive）： $(\forall~a \in S)~~\lnot(aRa)$ ，
对称性（symmetric）： $(\forall~a,b \in S)~~aRb \iff bRa$ ，
反对称性（antisymmetric）： $(\forall~a,b \in S)~~(aRb \land bRa) \implies a=b$ ，
非对称性（asymmetric）： $(\forall~a,b \in S)~~aRb \implies \lnot(bRa)$ ，
传递性（transitive）： $(\forall~a,b,c \in S)~~(aRb \land bRc) \implies aRc$ ，
连接性（connected）： $(\forall~a,b \in S)~~a \neq b \implies (aRb \lor bRa)$ ，
良基性（well-founded）： $(\exists~m \in S \neq \varnothing)~~(\forall~a \in S\setminus\{m\})~~\lnot(aRm)$ （即非空集合中有极小元），
不可比的传递性（transitive of incomparability）： $(\forall~a,b,c \in S)~~(\lnot(aRb \lor bRa) \land \lnot(bRc \lor cRb)) \implies \lnot(aRc \lor cRa)$ （若 $\lnot(aRb \lor bRa)$ ，则称和是不可比的）。

同时我们定义一些特殊的二元关系：

二元关系	自反性	反自反性	对称性	反对称性	非对称性	传递性	连接性	良基性	不可比的传递性
等价关系（equivalence relation）	有		有			有
预序（preorder，quasiorder）	有					有
偏序（partial order）	有			有		有
全序（total order）	有			有		有	有
良序（well-order）	有			有		有	有	有
严格预序（strict preorder）		有				有
严格偏序（strict partial order）		有			有	有
严格弱序（strict weak order）		有			有	有			有
严格全序（strict total order）		有			有	有	有

关系间的运算

对集合和集合上的二元关系和，我们可以定义如下运算：

和的并 $R\cup S$ 满足 $G(R\cup S):=\{(x,y):xRy \lor xSy\}$ （如 $\leq$ 是和的并），
和的交 $R\cap S$ 满足 $G(R\cap S):=\{(x,y):xRy \land xSy\}$ ，
的补 $\bar{R}$ 满足 $G(\bar{R}):=\{(x,y):\lnot(xRy)\}$ ，
的对偶满足 $G(R^T):=\{(y,x):xRy\}$ .

对集合和集合上的二元关系以及集合和集合上的二元关系，我们可以定义其复合 $S\circ R$ 满足 $G(S\circ R):=\{(x,z):(\exists~y\in Y)~~xRy\land ySz\}$ .

偏序集

定义

若集合上的一个二元关系 $\preceq$ 具有 自反性、反对称性、传递性，则称是 偏序集（partially ordered set，poset）， $\preceq$ 为其上一偏序（partial order）。

若偏序 $\preceq$ 还具有 连接性，则称其为全序（total order），对应的集合称为 全序集（totally ordered set）、线性序集（linearly ordered set，loset）、简单序集（simply ordered set）。

由传递性和反对称性可以推出自反性，由传递性和自反性也可以推出反对称性。

不难发现 $\mathbf{N}$ ， $\mathbf{Z}$ ， $\mathbf{Q}$ 、 $\mathbf{R}$ 均关于 $\leq$ 构成全序集。

偏序集的可视化表示：Hasse 图

对于有限偏序集，我们可以用 Hasse 图直观地表示其上的偏序关系。

定义

对有限偏序集和其上的偏序 $\preceq$ ，定义 $x\prec y\iff (x\preceq y\land x\neq y)$ 其对应的 Hasse 图 为满足如下条件的图 $G=\langle V,E\rangle$ ：

,
$E=\{(x,y)\in S\times S: x\prec y \land ((\nexists~z\in S)~~x\prec z\prec y)\}$

如对于集合 $\{0,1,2\}$ 的幂集和集合的包含关系 $\subseteq$ ，其对应的 Hasse 图为：

由于偏序具有反对称性，所以 Hasse 图一定是有向无环图，进而我们可以根据拓扑排序对任意有限偏序集构造全序。

链与反链

定义

对偏序集和其上的偏序 $\preceq$ ，称的全序子集为链（chain）。若的子集中任意两个不同元素均不可比（即 $(\forall~a,b \in T)~~a \neq b \implies (a \npreceq b \land b \npreceq a)$ ），则称为反链（antichain）。

对偏序集和其上的偏序 $\preceq$ ，我们将偏序集的最长反链长度称为宽度（partial order width）。

如对于集合 $\{0,1,2\}$ 的幂集和集合的包含关系 $\subseteq$ ， $\{\varnothing,\{1\},\{1,2\}\}$ 为一条链， $\{\{1\},\{0,2\}\}$ 为一条反链，的宽度为 .

预序集中的特殊元素

在预序集中，我们可以定义极大（小）元、上（下）界、上（下）确界等概念，这些概念可以推广到其他序关系中。

定义

对预序集和其上的预序 $\preceq$ ，取中的元素：

若 $(\forall~a \in S\setminus\{m\})~~\lnot(m\preceq a)$ ，则称为 极大元（maximal element），
若对 $T \subseteq S$ 满足 $(\forall~t\in T)~~t\preceq m$ ，则称为的上界（upper bound），
若对 $T \subseteq S$ 满足是的上界且对的任意上界均有 $m \preceq n$ ，则称为的 上确界（supremum）。

类似可定义 极小元（minimal element）、下界（lower bound）和 下确界（infimum）。

如是 $\mathbf{N}_+$ 的极小元和下界。

可以证明：

预序集中，极大（小）元、上（下）界、上（下）确界都是不一定存在的，即使存在也不一定唯一。
若偏序集的子集存在上（下）确界，则一定唯一。

我们可将的上确界、下确界分别记为 $\sup T$ ， $\inf T$ . 若偏序集既有上界又有下界，则称是有界的。

在无限偏序集中，极大元不一定存在。可用 Zorn 引理（Zorn's Lemma）来判断无限偏序集中是否存在极大元。

Zorn 引理

Zorn 引理 也被称为 Kuratowski–Zorn 引理，其内容为：若非空偏序集的每条链都有上界，则该偏序集存在极大元。

Zorn 引理与 选择公理、良序定理 等价。

有向集与格

我们知道若偏序集的子集存在上（下）确界，则一定唯一。但是这一点并不适用于极大（小）元。例如：考虑偏序集 $S=\{\{0\},\{1\},\{2\},\{0,1\},\{0,2\},\{1,2\}\}$ 和其上的偏序 $\subseteq$ ，不难发现其有个极大元和个极小元。

我们希望通过向偏序集添加一定的条件来使得若极大（小）元存在则一定唯一，这样我们就可以定义最大（小）元的概念了。

有向集

对预序集和其上的预序 $\preceq$ ，若 $(\forall~a,b\in S)~~(\exists~c\in S)~~a\preceq c\land b\preceq c$ ，则称 $\preceq$ 为的一个方向（direction），称为 有向集（directed set）或 过滤集（filtered set）。

有时也将满足上述定义的集合称为 上有向集（upward directed set），类似地可定义 下有向集（downward directed set）。

有向集也可用如下方式定义：

有向集的等价定义

对预序集和其上的预序 $\preceq$ ，若的任意有限子集均有上界，则称 $\preceq$ 为的一个方向，称为有向集。

不难发现：

若上有向集存在极大元，则一定唯一。我们将上有向集的极大元称为 最大元（greatest element）。
若下有向集存在极小元，则一定唯一。我们将下有向集的极小元称为 最小元（least element）。

有方向的偏序集中，对任意元素， $\{a,b\}$ 都有上界，若将上界修改为上确界，则得到了并半格的定义。

对偏序集和其上的偏序 $\preceq$ ：

并半格

若对中的任意元素， $\{a,b\}$ 均有上确界，则称为 并半格（join-semilattice，upper semilattice），并且我们称为和的并（join），记为 $a\lor b$ .

交半格

若对中的任意元素， $\{a,b\}$ 均有下确界，则称为 交半格（meet-semilattice，lower semilattice），并且我们称为和的交（meet），记为 $a\land b$ .

格

若既是并半格也是交半格，则称为格（lattice）。

例如的正因子构成的集合 $S=\{1,2,3,4,5,6,10,12,15,20,30,60\}$ 关于整除构成偏序集，其上的任意正整数， $\operatorname{lcm}(a,b)$ 为和的并， $\gcd(a,b)$ 为和的交，从而是格。

对偶

在序理论中，对偶是非常常见的概念，如上文提到的极大元与极小元对偶、上界与下界对偶、上确界与下确界对偶。

对偏序集和其上的偏序 $\preceq$ ，定义其对偶（dual，opposite）偏序集满足： $x \preceq y$ 在中成立当且仅当 $y \preceq x$ 在中成立。将的 Hasse 图的边反转即可得到的 Hasse 图。

Dilworth 定理与 Mirsky 定理

对有限偏序集和其上的偏序 $\preceq$ ，我们有如下的一对对偶的定理：

Dilworth 定理

的宽度（最长反链长度）等于最小的链覆盖数。

证明

考虑数学归纳法。当 $|S|\leq 3$ 时，命题显然成立。

假设命题对所有元素个数小于的偏序集都成立，令的宽度为 . 若中所有元素均不可比，则命题显然成立，否则在中取一条长度大于的链，令其中的最小元为，最大元为 .

令 $T=S\setminus\{m,M\}$ ，若中的宽度不超过，则由归纳假设知可被至多条链覆盖，进而可被这些链再加上链 $\{m,M\}$ 覆盖，命题成立，否则说明中的宽度也为，令中最长的一条反链为 .

我们考虑如下两个集合：

S^+:=\{x\in S:(\exists~a\in A)~~a\preceq x\}

S^-:=\{x\in S:(\exists~a\in A)~~x\preceq a\}

我们不难发现如下性质：

$S^+\cup S^-=S$ ，
$S^+\cap S^-=A$ ，
,（因为 $m\notin S^+$ 且 $M\notin S^-$ ）。

对和都应用归纳假设，则这两个集合的最小链覆盖数为，且这些链中恰好包含一个中的元素，设这些链分别为，，则 $\{C_a^-\cup\{a\}\cup C_a^+\}_{a\in A}$ 是的一个最小链覆盖，命题得证。

Mirsky 定理

的最长链长度等于最小的反链覆盖数。

证明

设的最长链长度为，则由定义，最小反链覆盖数至少为 .

令为以为最小元的最长链长度，注意到若，则与不可比，进而 $(\forall~n\in\mathbf{N})~~f^{-1}(\{n\})$ 均为反链，其中 $f^{-1}(\{n\}):=\{a\in S:f(a)=n\}$ 称为水平集（level set）。

因此不难得出 $\{f^{-1}(\{i\}):1\leq i\leq d\}$ 是一个反链覆盖，从而最小反链覆盖数至多为 .

Dilworth 定理与 Hall 婚配定理等价。

我们可以用 Dilworth 定理证明如下定理：

Erdős–Szekeres 定理

含至少个元素的实数序列 $\{a_i\}$ 要么有一个长为的不下降子序列，要么有一个长为的不上升子序列。

证明

设序列长度为 $n\geq rs+1$ ，定义偏序集 $\{(i,a_i)\}_{i=1}^{n}$ ，其上的偏序 $\preceq$ 定义为：

(i,a_i)\preceq (j,a_j)\iff (i\leq j\land a_i\leq a_j)

假设该偏序集的宽度不超过，则由 Dilworth 定理可知该偏序集可以被至多条链覆盖，若这些链的长度都不超过，则序列所含元素数至多为，与条件矛盾。

例题

Luogu P1020 [NOIP1999 提高组] 导弹拦截

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

对于全部数据，满足导弹的高度为正整数，且不超过 $5\times 10^4$ .

题解

令一共有个导弹，第个导弹的高度为，则集合 $\{(i,h_i)\}_{i=1}^{n}$ 为偏序集，其上的偏序 $\preceq$ 定义为：

(i,h_i)\preceq(j,h_j) \iff (i\leq j \land h_i\geq h_j)

进而根据 Dilworth 定理有：序列的不上升子序列的最少覆盖数等于最长上升子序列长度。从而可以通过最长不下降子序列的 $O(n\log n)$ 做法解决本题。

参考代码

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

int main() {
  vector<int> a;
  int x;
  while (cin >> x) a.push_back(x);
  vector<int> f, g;
  for (int i : a) {
    if (f.empty() || -i >= f.back())
      f.push_back(-i);
    else
      *upper_bound(f.begin(), f.end(), -i) = -i;
    if (g.empty() || i > g.back())
      g.push_back(i);
    else
      *lower_bound(g.begin(), g.end(), i) = i;
  }
  cout << f.size() << '\n' << g.size() << '\n';
  return 0;
}

[TJOI2015] 组合数学

给一个行列的网格图，其中每个格子中均有若干块财宝。每次从左上角出发，只能往右或下走，每次经过一个格子至多只能捡走一块财宝。问至少要走几次才可能把财宝全捡完。

$1\le n \le 1000$ ， $1\le m \le 1000$ ，每个格子中的财宝不超过块。

题解

不考虑网格图的点权，不难发现按给定的规则下在网格图上行走等价于在 DAG 上行走，从而我们可以将其视作 Hasse 图来构造偏序集，进而根据 Dilworth 定理有：DAG 的最小链覆盖数等于最大的点独立集大小。

因此本题所求即为给定网格图最大点权独立集的点权和。

令 $a_{ij}$ 为网格图在点处的权值，为从到这个子网格中的答案，注意到每个点都和其右上角的点不相邻，则状态转移方程为：

f(i,j)=\max\{f(i-1,j),f(i,j+1),f(i-1,j+1)+a_{ij}\}

答案即为 .

参考代码

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int t = 0;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<vector<int64_t>> a(n, vector<int64_t>(m));
    for (auto &i : a)
      for (auto &j : i) cin >> j;
    vector<vector<int64_t>> f(n, vector<int64_t>(m));
    for (int i = 0; i < n; ++i)
      for (int j = m - 1; j >= 0; --j)
        f[i][j] =
            max({(i == 0 ? 0 : f[i - 1][j]), (j == m - 1 ? 0 : f[i][j + 1]),
                 (i == 0 || j == m - 1 ? 0 : f[i - 1][j + 1]) + a[i][j]});
    cout << f[n - 1][0] << '\n';
  }
  return 0;
}

习题

C++ 中的应用

另请参阅：排序相关 STL - 算法基础。

C++ STL 中需要使用比较的算法和数据结构中有序理论的应用。我们经常需要在 C++ 中自定义比较器，STL 要求其必须为 严格弱序。令为自定义比较器，则可以定义：

为；
$x \leq y$ 为 $y \nless x$ ；
$x \geq y$ 为 $x \nless y$ ；
为 $x \nless y\land y \nless x$ .

参考资料与拓展阅读

本页面最近更新：2024/7/12 21:55:11，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, iamtwz, ImpleLee, isdanni, liuzimingc, opsiff, shaokeyibb, StudyingFather, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用