在 \(sort\) 的时候, 我们的 \(cmp\)函数应该满足 \(<\)

可什么是小于 它需要满足什么性质才能等价于小于?

序理论给出了严格的定义

二元关系

集合\(X\)和集合\(Y\)上的一个二元关系, \(G(R) \subseteq X \times Y = \{ (x,y); x \in X, y \in Y \}\)

\(xRy\) 成立当且仅当 \((x,y) \in G(R)\)

例如 \(N_+\) 上的整除 与 小于等于都是二元关系

性质

• 自反性 \(\forall a \in S, aRa\)

• 反自反性 \(\forall a \in S, \neg (aRb)\)

• 对称性 \(\forall a, b \in S, (aRb) \Longleftrightarrow (bRa)\)

• 反对称性 \(\forall a, b \in S, (aRb \wedge bRa) \Longrightarrow a = b\)

• 非对称性 \(\forall a, b \in S, (aRb) \Longrightarrow \neg (bRa)\)

• 传递性 \(\forall a, b, c \in S, (aRb \wedge bRc) \Longrightarrow aRc\)

• 连接性 \(\forall a, b \in S, a \ne b \Longrightarrow (aRb \vee bRa)\)

• 不可比的传递性 \(\forall a,b,c \in S, (\neg (aRb \vee bRa) \wedge \neg (bRc \vee cRb)) \Longrightarrow \neg(aRc \vee cRa)\)

这就是它所有的定义

等价关系

满足自反性, 对称性, 传递性

例子:

• =

• 有集合\(S\), 这是集合 \(S\)的一种划分 $S = \sqcup_{\alpha \in I}S_{\alpha} $

\(\{ (a,b) \in S \times S;a,b \in S_{\alpha},\alpha \in I \}\)

• 有线性空间 \(L\) , \(V\) 是 \(L\)的一个线性子空间

\(\{ (a,b) \in L \times L; a + V = b + V\}\)

等价关系与集合的划分

如果把一个二元关系理解成为一条边 那么它形成的图就是多个无向子图

所以我们可以把每一个无向子图看成一个等价类 于是这个就形成了一个原集合的一种划分!

也就是说一个等价关系会诱导形成一个集合的划分

一个集合的划分也会诱导形成一个等价关系

全序

满足自反性, 反对称性, 传递性, 连接性

例子

• \(\le\)

• 一条链

若 \(a\) 可以到达 \(b\), 则\(aRb\)成立

偏序

满足自反性, 反对称性, 传递性

例子:

• 一个 \(DAG\)

若 \(a\) 可以到达 \(b\), 则\(aRb\)成立

偏序集

若集合 \(S\) 上的一个二元关系 \(\preceq\) 具有 自反性、反对称性、传递性，则称 \(S\) 是 偏序集，\(\preceq\) 为其上一偏序。

链与反链

链就是偏序集的全序子集

若 \(S\) 的子集 \(T\) 中任意两个不同元素均不可比,（即 \((\forall~a,b \in T)~~a \neq b \implies (a \npreceq b \land b \npreceq a)\)），则称 \(T\) 为反链

Dilworth定理

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

同理也有 \(S\) 的最长链长度等于最小的反链覆盖数

证明

咕咕咕

例题

• 导弹拦截

• 组合数学

咕咕咕

严格弱序

满足反自反性 非对称性 传递性 不可比的传递性

这个是C++ STL里面要求排序的二元关系

例子

• <

严格弱序与贪心

在一种贪心题目中 我们通常需要确定一种排列 让他最优

我们通常会使用一种方法是考虑相邻交换满足什么条件的时候是不用交换的 然后以这个条件作为二元关系 进行 \(sort\) 排序

容易证明这样是对的 因为考虑 \(i\) 和 \(j (i < j)\) 交换会不会更优我们考虑每次交换相邻的 然后每次交换都是不优的, 所以排完序后就是最优的

但是 这里有一个非常重要的点就是它必须满足严格弱序

例题

• 国王游戏

• 皇后游戏

咕咕咕