序理論

引入

序理論是利用二元關係來將「次序」這一概念嚴格化的數學分支，下面將介紹這一分支的基本定義。

定義

二元關係

定義

集合 \(X\) 和集合 \(Y\) 上的一個 二元關係（binary relation）\(R\) 定義為元組 \((X,Y,G(R))\)，其中 \(X\) 稱為定義域（domain），\(Y\) 稱為陪域（codomain），\(G(R)\subseteq X\times Y=\{(x,y):x\in X,y\in Y\}\) 稱為二元關係 \(R\) 的圖（graph）。\(xRy\) 成立當且僅當 \((x,y)\in G(R)\)。

若 \(X=Y\)，則稱該二元關係為齊次二元關係（homogeneous relation）或內關係（endorelation）。

若沒有特別説明，下文中的二元關係均為齊次二元關係。

例如 \(\mathbf{N}_+\) 上的整除 \(\mid\) 和小於等於 \(\leq\) 均為二元關係。

我們研究二元關係時，往往會關注其是否具有一些特別的性質。對集合 \(S\) 上的二元關係 \(R\)，我們定義如下特殊性質：

自反性（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)\)（即非空集合 \(S\) 中有極小元 \(m\)），
不可比的傳遞性（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)\)，則稱 \(a\) 和 \(b\) 是不可比的）。

同時我們定義一些特殊的二元關係：

二元關係	自反性	反自反性	對稱性	反對稱性	非對稱性	傳遞性	連接性	良基性	不可比的傳遞性
等價關係（equivalence relation）	有		有			有
預序（preorder，quasiorder）	有					有
偏序（partial order）	有			有		有
全序（total order）	有			有		有	有
良序（well-order）	有			有		有	有	有
嚴格預序（strict preorder）		有				有
嚴格偏序（strict partial order）		有			有	有
嚴格弱序（strict weak order）		有			有	有			有
嚴格全序（strict total order）		有			有	有	有

關係間的運算

對集合 \(X\) 和集合 \(Y\) 上的二元關係 \(R\) 和 \(S\)，我們可以定義如下運算：

\(R\) 和 \(S\) 的並 \(R\cup S\) 滿足 \(G(R\cup S):=\{(x,y):xRy \lor xSy\}\)（如 \(\leq\) 是 \(<\) 和 \(=\) 的並），
\(R\) 和 \(S\) 的交 \(R\cap S\) 滿足 \(G(R\cap S):=\{(x,y):xRy \land xSy\}\)，
\(R\) 的補 \(\bar{R}\) 滿足 \(G(\bar{R}):=\{(x,y):\lnot(xRy)\}\)，
\(R\) 的對偶 \(R^T\) 滿足 \(G(R^T):=\{(y,x):xRy\}\).

對集合 \(X\) 和集合 \(Y\) 上的二元關係 \(R\) 以及集合 \(Y\) 和集合 \(Z\) 上的二元關係 \(S\)，我們可以定義其複合 \(S\circ R\) 滿足 \(G(S\circ R):=\{(x,z):(\exists~y\in Y)~~xRy\land ySz\}\).

偏序集

定義

若集合 \(S\) 上的一個二元關係 \(\preceq\) 具有 自反性、反對稱性、傳遞性，則稱 \(S\) 是 偏序集（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 圖直觀地表示其上的偏序關係。

定義

對有限偏序集 \(S\) 和其上的偏序 \(\preceq\)，定義 \(x\prec y\iff (x\preceq y\land x\neq y)\) 其對應的 Hasse 圖 為滿足如下條件的圖 \(G=\langle V,E\rangle\)：

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

如對於集合 \(\{0,1,2\}\) 的冪集 \(S\) 和集合的包含關係 \(\subseteq\)，其對應的 Hasse 圖為：

由於偏序具有反對稱性，所以 Hasse 圖一定是有向無環圖，進而我們可以根據拓撲排序對任意有限偏序集構造全序。

鏈與反鏈

定義

對偏序集 \(S\) 和其上的偏序 \(\preceq\)，稱 \(S\) 的全序子集為鏈（chain）。若 \(S\) 的子集 \(T\) 中任意兩個不同元素均不可比（即 \((\forall~a,b \in T)~~a \neq b \implies (a \npreceq b \land b \npreceq a)\)），則稱 \(T\) 為反鏈（antichain）。

對偏序集 \(S\) 和其上的偏序 \(\preceq\)，我們將偏序集 \(S\) 的最長反鏈長度稱為寬度（partial order width）。

如對於集合 \(\{0,1,2\}\) 的冪集 \(S\) 和集合的包含關係 \(\subseteq\)，\(\{\varnothing,\{1\},\{1,2\}\}\) 為一條鏈，\(\{\{1\},\{0,2\}\}\) 為一條反鏈，\(S\) 的寬度為 \(3\).

預序集中的特殊元素

在預序集中，我們可以定義極大（小）元、上（下）界、上（下）確界等概念，這些概念可以推廣到其他序關係中。

定義

對預序集 \(S\) 和其上的預序 \(\preceq\)，取 \(S\) 中的元素 \(m\)：

若 \((\forall~a \in S\setminus\{m\})~~\lnot(m\preceq a)\)，則稱 \(m\) 為 極大元（maximal element），
若對 \(T \subseteq S\) 滿足 \((\forall~t\in T)~~t\preceq m\)，則稱 \(m\) 為 \(T\) 的上界（upper bound），
若對 \(T \subseteq S\) 滿足 \(m\) 是 \(T\) 的上界且對 \(T\) 的任意上界 \(n\) 均有 \(m \preceq n\)，則稱 \(m\) 為 \(T\) 的 上確界（supremum）。

類似可定義 極小元（minimal element）、下界（lower bound）和 下確界（infimum）。

如 \(1\) 是 \(\mathbf{N}_+\) 的極小元和下界。

可以證明：

預序集中，極大（小）元、上（下）界、上（下）確界都是不一定存在的，即使存在也不一定唯一。
若偏序集 \(S\) 的子集 \(T\) 存在上（下）確界，則一定唯一。

我們可將 \(T\) 的上確界、下確界分別記為 \(\sup T\)，\(\inf T\). 若偏序集 \(S\) 既有上界又有下界，則稱 \(S\) 是有界的。

在無限偏序集中，極大元不一定存在。可用 Zorn 引理（Zorn's Lemma）來判斷無限偏序集中是否存在極大元。

Zorn 引理

Zorn 引理 也被稱為 Kuratowski–Zorn 引理，其內容為：若非空偏序集的每條鏈都有上界，則該偏序集存在極大元。

Zorn 引理與 選擇公理、良序定理 等價。

有向集與格

我們知道若偏序集的子集存在上（下）確界，則一定唯一。但是這一點並不適用於極大（小）元。例如：考慮偏序集 \(S=\{\{0\},\{1\},\{2\},\{0,1\},\{0,2\},\{1,2\}\}\) 和其上的偏序 \(\subseteq\)，不難發現其有 \(3\) 個極大元和 \(3\) 個極小元。

我們希望通過向偏序集添加一定的條件來使得若極大（小）元存在則一定唯一，這樣我們就可以定義最大（小）元的概念了。

有向集

對預序集 \(S\) 和其上的預序 \(\preceq\)，若 \((\forall~a,b\in S)~~(\exists~c\in S)~~a\preceq c\land b\preceq c\)，則稱 \(\preceq\) 為 \(S\) 的一個方向（direction），\(S\) 稱為 有向集（directed set）或 過濾集（filtered set）。

有時也將滿足上述定義的集合 \(S\) 稱為 上有向集（upward directed set），類似地可定義 下有向集（downward directed set）。

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

有向集的等價定義

對預序集 \(S\) 和其上的預序 \(\preceq\)，若 \(S\) 的任意有限子集 \(T\) 均有上界，則稱 \(\preceq\) 為 \(S\) 的一個方向，\(S\) 稱為有向集。

不難發現：

若上有向集存在極大元，則一定唯一。我們將上有向集的極大元稱為 最大元（greatest element）。
若下有向集存在極小元，則一定唯一。我們將下有向集的極小元稱為 最小元（least element）。

有方向的偏序集中，對任意元素 \(a,b\)，\(\{a,b\}\) 都有上界，若將上界修改為上確界，則得到了並半格的定義。

對偏序集 \(S\) 和其上的偏序 \(\preceq\)：

並半格

若對 \(S\) 中的任意元素 \(a,b\)，\(\{a,b\}\) 均有上確界 \(c\)，則稱 \(S\) 為 並半格（join-semilattice，upper semilattice），並且我們稱 \(c\) 為 \(a\) 和 \(b\) 的並（join），記為 \(a\lor b\).

交半格

若對 \(S\) 中的任意元素 \(a,b\)，\(\{a,b\}\) 均有下確界 \(c\)，則稱 \(S\) 為 交半格（meet-semilattice，lower semilattice），並且我們稱 \(c\) 為 \(a\) 和 \(b\) 的交（meet），記為 \(a\land b\).

格

若 \(S\) 既是並半格也是交半格，則稱 \(S\) 為格（lattice）。

例如 \(60\) 的正因子構成的集合 \(S=\{1,2,3,4,5,6,10,12,15,20,30,60\}\) 關於整除構成偏序集，其上的任意正整數 \(a,b\)，\(\operatorname{lcm}(a,b)\) 為 \(a\) 和 \(b\) 的並，\(\gcd(a,b)\) 為 \(a\) 和 \(b\) 的交，從而 \(S\) 是格。

對偶

在序理論中，對偶是非常常見的概念，如上文提到的極大元與極小元對偶、上界與下界對偶、上確界與下確界對偶。

對偏序集 \(P\) 和其上的偏序 \(\preceq\)，定義其對偶（dual，opposite）偏序集 \(P^d\) 滿足：\(x \preceq y\) 在 \(P\) 中成立當且僅當 \(y \preceq x\) 在 \(P^d\) 中成立。將 \(P\) 的 Hasse 圖的邊反轉即可得到 \(P^d\) 的 Hasse 圖。

Dilworth 定理與 Mirsky 定理

對有限偏序集 \(S\) 和其上的偏序 \(\preceq\)，我們有如下的一對對偶的定理：

Dilworth 定理

\(S\) 的寬度（最長反鏈長度）等於最小的鏈覆蓋數。

證明

考慮數學歸納法。當 \(|S|\leq 3\) 時，命題顯然成立。

假設命題對所有元素個數小於 \(|S|\) 的偏序集都成立，令 \(S\) 的寬度為 \(d\). 若 \(|S|\) 中所有元素均不可比，則命題顯然成立，否則在 \(S\) 中取一條長度大於 \(1\) 的鏈，令其中的最小元為 \(m\)，最大元為 \(M\).

令 \(T=S\setminus\{m,M\}\)，若 \(T\) 中的寬度不超過 \(d-1\)，則由歸納假設知 \(T\) 可被至多 \(d-1\) 條鏈覆蓋，進而 \(S\) 可被這些鏈再加上鍊 \(\{m,M\}\) 覆蓋，命題成立，否則説明 \(T\) 中的寬度也為 \(d\)，令 \(T\) 中最長的一條反鏈為 \(A\).

我們考慮如下兩個集合：

\[ 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\)，
\(|S^+|<|S|\),\(|S^-|<|S|\)（因為 \(m\notin S^+\) 且 \(M\notin S^-\)）。

對 \(S^+\) 和 \(S^-\) 都應用歸納假設，則這兩個集合的最小鏈覆蓋數為 \(d\)，且這些鏈中恰好包含一個 \(A\) 中的元素 \(a\)，設這些鏈分別為 \(C_a^+\)，\(C_a^-\)，則 \(\{C_a^-\cup\{a\}\cup C_a^+\}_{a\in A}\) 是 \(S\) 的一個最小鏈覆蓋，命題得證。

Mirsky 定理

\(S\) 的最長鏈長度等於最小的反鏈覆蓋數。

證明

設 \(S\) 的最長鏈長度為 \(d\)，則由定義，最小反鏈覆蓋數至少為 \(d\).

令 \(f(s)\) 為以 \(s\) 為最小元的最長鏈長度，注意到若 \(f(s)=f(t)\)，則 \(s\) 與 \(t\) 不可比，進而 \((\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\}\) 是一個反鏈覆蓋，從而最小反鏈覆蓋數至多為 \(d\).

Dilworth 定理與 Hall 婚配定理等價。

我們可以用 Dilworth 定理證明如下定理：

Erdős–Szekeres 定理

含至少 \(rs+1\) 個元素的實數序列 \(\{a_i\}\) 要麼有一個長為 \(r+1\) 的不下降子序列，要麼有一個長為 \(s+1\) 的不上升子序列。

證明

設序列長度為 \(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) \]

假設該偏序集的寬度不超過 \(s+1\)，則由 Dilworth 定理可知該偏序集可以被至多 \(s\) 條鏈覆蓋，若這些鏈的長度都不超過 \(r\)，則序列所含元素數至多為 \(rs\)，與條件矛盾。

例題

Luogu P1020 [NOIP1999 提高組] 導彈攔截

某國為了防禦敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。

輸入導彈依次飛來的高度，計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。

對於全部數據，滿足導彈的高度為正整數，且不超過 \(5\times 10^4\).

題解

令一共有 \(n\) 個導彈，第 \(i\) 個導彈的高度為 \(h_i\)，則集合 \(\{(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 <bits/stdc++.h>
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] 組合數學

給一個 \(n\) 行 \(m\) 列的網格圖，其中每個格子中均有若干塊財寶。每次從左上角出發，只能往右或下走，每次經過一個格子至多隻能撿走一塊財寶。問至少要走幾次才可能把財寶全撿完。

\(1\le n \le 1000\)，\(1\le m \le 1000\)，每個格子中的財寶不超過 \(10^6\) 塊。

題解

不考慮網格圖的點權，不難發現按給定的規則下在網格圖上行走等價於在 DAG 上行走，從而我們可以將其視作 Hasse 圖來構造偏序集，進而根據 Dilworth 定理有：DAG 的最小鏈覆蓋數等於最大的點獨立集大小。

因此本題所求即為給定網格圖最大點權獨立集的點權和。

令 \(a_{ij}\) 為網格圖在點 \((i,j)\) 處的權值，\(f(i,j)\) 為從 \((i,j)\) 到 \((1,m)\) 這個子網格中的答案，注意到每個點都和其右上角的點不相鄰，則狀態轉移方程為：

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

答案即為 \(f(n,1)\).

參考代碼

#include <bits/stdc++.h>
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>y\) 為 \(y<x\)；
\(x \leq y\) 為 \(y \nless x\)；
\(x \geq y\) 為 \(x \nless y\)；
\(x=y\) 為 \(x \nless y\land y \nless x\).

參考資料與拓展閲讀

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用