跳转至

序理论

引入

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

定义

二元关系

定义

集合 和集合 上的一个 二元关系(binary relation) 定义为元组 ,其中 称为定义域(domain), 称为陪域(codomain), 称为二元关系 的图(graph)。 成立当且仅当

,则称该二元关系为齐次二元关系(homogeneous relation)或内关系(endorelation)。

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

例如 上的整除 和小于等于 均为二元关系。

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

  1. 自反性(reflexive):
  2. 反自反性(irreflexive,anti-reflexive):
  3. 对称性(symmetric):
  4. 反对称性(antisymmetric):
  5. 非对称性(asymmetric):
  6. 传递性(transitive):
  7. 连接性(connected):
  8. 良基性(well-founded):(即非空集合 中有极小元 ),
  9. 不可比的传递性(transitive of incomparability):(若 ,则称 是不可比的)。

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

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

关系间的运算

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

  1. 的并 满足 (如 的并),
  2. 的交 满足
  3. 的补 满足
  4. 的对偶 满足 .

对集合 和集合 上的二元关系 以及集合 和集合 上的二元关系 ,我们可以定义其复合 满足 .

偏序集

定义

若集合 上的一个二元关系 具有 自反性反对称性传递性,则称 偏序集(partially ordered set,poset), 为其上一 偏序(partial order)。

若偏序 还具有 连接性,则称其为 全序(total order),对应的集合称为 全序集(totally ordered set)、线性序集(linearly ordered set,loset)、简单序集(simply ordered set)。

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

不难发现 均关于 构成全序集。

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

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

定义

对有限偏序集 和其上的偏序 ,定义 其对应的 Hasse 图 为满足如下条件的图

  • ,

如对于集合 的幂集 和集合的包含关系 ,其对应的 Hasse 图为:

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

链与反链

定义

对偏序集 和其上的偏序 ,称 的全序子集为 (chain)。若 的子集 中任意两个不同元素均不可比(即 ),则称 反链(antichain)。

对偏序集 和其上的偏序 ,我们将偏序集 的最长反链长度称为 宽度(partial order width)。

如对于集合 的幂集 和集合的包含关系 为一条链, 为一条反链, 的宽度为 .

预序集中的特殊元素

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

定义

对预序集 和其上的预序 ,取 中的元素

  1. ,则称 极大元(maximal element),
  2. 若对 满足 ,则称 上界(upper bound),
  3. 若对 满足 的上界且对 的任意上界 均有 ,则称 上确界(supremum)。

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

的极小元和下界。

可以证明:

  • 预序集中,极大(小)元、上(下)界、上(下)确界都是不一定存在的,即使存在也不一定唯一。

  • 若偏序集 的子集 存在上(下)确界,则一定唯一。

    我们可将 的上确界、下确界分别记为 . 若偏序集 既有上界又有下界,则称 是有界的。

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

Zorn 引理

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

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

有向集与格

我们知道若偏序集的子集存在上(下)确界,则一定唯一。但是这一点并不适用于极大(小)元。例如:考虑偏序集 和其上的偏序 ,不难发现其有 个极大元和 个极小元。

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

有向集

对预序集 和其上的预序 ,若 ,则称 的一个 方向(direction), 称为 有向集(directed set)或 过滤集(filtered set)。

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

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

有向集的等价定义

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

不难发现:

  • 若上有向集存在极大元,则一定唯一。我们将上有向集的极大元称为 最大元(greatest element)。
  • 若下有向集存在极小元,则一定唯一。我们将下有向集的极小元称为 最小元(least element)。

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

对偏序集 和其上的偏序

并半格

若对 中的任意元素 均有上确界 ,则称 并半格(join-semilattice,upper semilattice),并且我们称 (join),记为 .

交半格

若对 中的任意元素 均有下确界 ,则称 交半格(meet-semilattice,lower semilattice),并且我们称 (meet),记为 .

既是并半格也是交半格,则称 (lattice)。

例如 的正因子构成的集合 关于整除构成偏序集,其上的任意正整数 的并, 的交,从而 是格。

对偶

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

对偏序集 和其上的偏序 ,定义其 对偶(dual,opposite)偏序集 满足: 中成立当且仅当 中成立。将 的 Hasse 图的边反转即可得到 的 Hasse 图。

Dilworth 定理与 Mirsky 定理

对有限偏序集 和其上的偏序 ,我们有如下的一对对偶的定理:

Dilworth 定理

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

证明

考虑数学归纳法。当 时,命题显然成立。

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

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

我们考虑如下两个集合:

我们不难发现如下性质:

  • ,(因为 )。

都应用归纳假设,则这两个集合的最小链覆盖数为 ,且这些链中恰好包含一个 中的元素 ,设这些链分别为 ,则 的一个最小链覆盖,命题得证。

Mirsky 定理

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

证明

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

为以 为最小元的最长链长度,注意到若 ,则 不可比,进而 均为反链,其中 称为 水平集(level set)

因此不难得出 是一个反链覆盖,从而最小反链覆盖数至多为 .

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

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

Erdős–Szekeres 定理

含至少 个元素的实数序列 要么有一个长为 的不下降子序列,要么有一个长为 的不上升子序列。

证明

设序列长度为 ,定义偏序集 ,其上的偏序 定义为:

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

例题

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

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

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

对于全部数据,满足导弹的高度为正整数,且不超过 .

题解

令一共有 个导弹,第 个导弹的高度为 ,则集合 为偏序集,其上的偏序 定义为:

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

参考代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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] 组合数学

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

,每个格子中的财宝不超过 块。

题解

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

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

为网格图在点 处的权值, 为 从 这个子网格中的答案,注意到每个点都和其右上角的点不相邻,则状态转移方程为:

答案即为 .

参考代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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 要求 其必须为 严格弱序。令 为自定义比较器,则可以定义:

  • .

参考资料与拓展阅读

  1. Order theory - From Academic Kids
  2. Binary Relation - Wikipedia
  3. Order Theory - Wikipedia
  4. Hasse diagram - Wikipedia
  5. Directed set - Wikipedia
  6. Order Theory, Lecture Notes by Mark Dean for Decision Theory
  7. 卢开澄,卢华明,《组合数学》(第 3 版), 2006
  8. List of Order Theory Topics - Wikipedia
  9. 浅谈邻项交换排序的应用以及需要注意的问题 by ouuan
  10. One thing you should know about comparators—Strict Weak Ordering
  11. Dilworth's theorem - Wikipedia
  12. Dilworth's Theorem | Brilliant Math & Science Wiki
  13. Hall's marriage theorem - Wikipedia
  14. Hall's Marriage Theorem | Brilliant Math & Science Wiki
  15. Dilworth 学习笔记 - Selfish