序理论
引入
序理论是利用二元关系来将「次序」这一概念严格化的数学分支,下面将介绍这一分支的基本定义。
定义
二元关系
定义
集合
和集合
上的一个 二元关系(binary relation)
定义为元组
,其中
称为定义域(domain),
称为陪域(codomain),
称为二元关系
的图(graph)。
成立当且仅当
。
若
,则称该二元关系为齐次二元关系(homogeneous relation)或内关系(endorelation)。
若没有特别说明,下文中的二元关系均为齐次二元关系。
例如
上的整除
和小于等于
均为二元关系。
我们研究二元关系时,往往会关注其是否具有一些特别的性质。对集合
上的二元关系
,我们定义如下特殊性质:
- 自反性(reflexive):
, - 反自反性(irreflexive,anti-reflexive):
, - 对称性(symmetric):
, - 反对称性(antisymmetric):
, - 非对称性(asymmetric):
, - 传递性(transitive):
, - 连接性(connected):
, - 良基性(well-founded):
(即非空集合
中有极小元
), - 不可比的传递性(transitive of incomparability):
(若
,则称
和
是不可比的)。
同时我们定义一些特殊的二元关系:
二元关系 | 自反性 | 反自反性 | 对称性 | 反对称性 | 非对称性 | 传递性 | 连接性 | 良基性 | 不可比的传递性 |
---|
等价关系(equivalence relation) | 有 | | 有 | | | 有 | | | |
预序(preorder,quasiorder) | 有 | | | | | 有 | | | |
偏序(partial order) | 有 | | | 有 | | 有 | | | |
全序(total order) | 有 | | | 有 | | 有 | 有 | | |
良序(well-order) | 有 | | | 有 | | 有 | 有 | 有 | |
严格预序(strict preorder) | | 有 | | | | 有 | | | |
严格偏序(strict partial order) | | 有 | | | 有 | 有 | | | |
严格弱序(strict weak order) | | 有 | | | 有 | 有 | | | 有 |
严格全序(strict total order) | | 有 | | | 有 | 有 | 有 | | |
关系间的运算
对集合
和集合
上的二元关系
和
,我们可以定义如下运算:
和
的并
满足
(如
是
和
的并),
和
的交
满足
,
的补
满足
,
的对偶
满足
.
对集合
和集合
上的二元关系
以及集合
和集合
上的二元关系
,我们可以定义其复合
满足
.
偏序集
定义
若集合
上的一个二元关系
具有 自反性、反对称性、传递性,则称
是 偏序集(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)。
如对于集合
的幂集
和集合的包含关系
,
为一条链,
为一条反链,
的宽度为
.
预序集中的特殊元素
在预序集中,我们可以定义极大(小)元、上(下)界、上(下)确界等概念,这些概念可以推广到其他序关系中。
定义
对预序集
和其上的预序
,取
中的元素
:
- 若
,则称
为 极大元(maximal element), - 若对
满足
,则称
为
的 上界(upper bound), - 若对
满足
是
的上界且对
的任意上界
均有
,则称
为
的 上确界(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 要求 其必须为 严格弱序。令
为自定义比较器,则可以定义:
为
;
为
;
为
;
为
.
参考资料与拓展阅读
- Order theory - From Academic Kids
- Binary Relation - Wikipedia
- Order Theory - Wikipedia
- Hasse diagram - Wikipedia
- Directed set - Wikipedia
- Order Theory, Lecture Notes by Mark Dean for Decision Theory
- 卢开澄,卢华明,《组合数学》(第 3 版), 2006
- List of Order Theory Topics - Wikipedia
- 浅谈邻项交换排序的应用以及需要注意的问题 by ouuan
- One thing you should know about comparators—Strict Weak Ordering
- Dilworth's theorem - Wikipedia
- Dilworth's Theorem | Brilliant Math & Science Wiki
- Hall's marriage theorem - Wikipedia
- Hall's Marriage Theorem | Brilliant Math & Science Wiki
- Dilworth 学习笔记 - Selfish
本页面最近更新:2025/6/9 00:41:27,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Tiphereth-A, c-forrest, Enter-tainer, iamtwz, ImpleLee, isdanni, liuzimingc, opsiff, shaokeyibb, StudyingFather, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用