拟阵简介（unfin）

发表于 更新于 分类于 ， 本文字数： 2k 阅读时长 ≈ 7 分钟

拟阵最早由 Hassler Whitney 于 1935 年作为线性相关的推广提出。拟阵理论在组合数学、最优化、图论等领域有很多应用。拟阵可以用来证明贪心算法的正确性，如 Kruskal 算法、匈牙利算法等。

定义

拟阵有许多等价定义，为方便起见，我们先给出基于独立集的定义。

拟阵

定义 - 1-1（基于独立集的拟阵定义）

定义 \(M=(E,\mathcal{I})\)，其中 \(E\) 是有限集合，\(\mathcal{I}\) 是 \(E\) 的子集族。若 \(\mathcal{I}\) 满足：

  1. \(\varnothing\in\mathcal{I}\)，
  2. （遗传性，hereditary property）\(\forall A'\subseteq A\subseteq E\)，\(A\in\mathcal{I}\implies A'\in\mathcal{I}\)，
  3. （独立集的交换性，independent set exchange property）若 \(A,B\in\mathcal{I}\) 且 \(|A|>|B|\)，则存在 \(x\in A\setminus B\) 使得 \(B\cup\{x\}\in\mathcal{I}\).

则称 \(M\) 是（有限）拟阵（matroid），\(E\) 称为基础集（ground set），\(\mathcal{I}\) 称为独立集族（independent sets）。

对拟阵 \(M=(E,\mathcal{I})\)，若 \(A\in\mathcal{I}\)，则称 \(A\) 为独立集（independent set），否则称为相关集（dependent）。

为便于理解，我们在此先给出一个简单的例子：考虑 \(V=(\mathrm{Z}_3)^2\)，\(\mathcal{I}=\{\varnothing,\{(0,1)\},\{(1,0)\},\{(2,0)\},\{(0,1),(1,0)\},\{(0,1),(2,0)\}\}\)，则可验证 \(\mathcal{I}\) 满足上述的三条性质，故 \((V,\mathcal{I})\) 为一拟阵。

接下来我们给出一些基本概念。

同构

定义 - 1-2 对拟阵 \(M_1=(E_1,\mathcal{I}_1)\) 和 \(M_2=(E_2,\mathcal{I}_2)\)，若存在双射 \(f:E_1\to E_2\) 使得

\[ A\in\mathcal{I}_1\iff f(A)\in\mathcal{I}_2,\quad \forall A\subseteq E_1, \]

则称 \(M_1\) 和 \(M_2\) 同构，记作 \(M_1\cong M_2\).

类似可定义拟阵的单同态和满同态。

基

定义 - 1-3 对拟阵 \(M=(E,\mathcal{I})\)，若 \(B\in\mathcal{I}\)，但 \(\nexists B'\supset B\) 使得 \(B'\in\mathcal{I}\)（即极大独立集），则称 \(B\) 为拟阵 \(M\) 的基（basis）。

称 \(\mathcal{B}(M)\) 或 \(\mathcal{B}\) 为拟阵 \(M\) 中所有基构成的集合。

圈

定义 - 1-4 对拟阵 \(M=(E,\mathcal{I})\)，若 \(C\notin\mathcal{I}\)，但 \(\forall C'\subset C\) 均有 \(C'\in\mathcal{I}\)（即极小相关集），则称 \(C\) 为拟阵 \(M\) 的圈（circuit）。

称 \(\mathcal{C}(M)\) 或 \(\mathcal{C}\) 为拟阵 \(M\) 中所有圈构成的集合。

秩函数

定义 - 1-5 对拟阵 \(M=(E,\mathcal{I})\)，定义函数 \(r_M(A)=\max\{|X|:X\subseteq A, X\in\mathcal{I}\},~\forall A\subseteq E\)，称其为拟阵 \(M\) 的秩函数（rank function）。不引起歧义时可简记为 \(r(A)\).

称 \(r(M)=r(E)\) 为拟阵 \(M\) 的秩（rank）。

若 \(\exists x\in E,~~r(A\cup\{x\})=r(A)\)，则称 \(x\) 与 \(A\) 相关。

闭包算子与闭集

定义 - 1-6 对拟阵 \(M=(E,\mathcal{I})\)，定义 \(\operatorname{cl}(A)=\{x\in E:r(A)=r(A\cup\{x\})\},~\forall A\subseteq E\)，称其为闭包算子（closure operator）。

称 \(\operatorname{cl}(A)\) 为 \(A\) 的闭包（closure/span）。

若 \(A=\operatorname{cl}(A)\)，则称 \(A\) 为拟阵 \(M\) 的闭集（closed/flat/subspace）。

性质

基的性质

性质 - 2-1 对拟阵 \(M=(E,\mathcal{I})\)，

  1. 拟阵的极大独立集是最大独立集，即 \(\forall B_1,B_2\in\mathcal{B}(M)\)，\(|B_1|=|B_2|\)；
  2. （1 的推论）\(\forall B\in\mathcal{B}(M)\)，\(\nexists B'\in\mathcal{B}(M)\) 使得 \(B'\subset B\)；
  3. 对任意 \(X\in\mathcal{I}\) 均存在 \(B\in\mathcal{B}(M)\) 使得 \(X\subseteq B\)；
  4. （基的交换性，basis exchange property）在 \(\mathcal{B}(M)\) 中任取两个基 \(B_1\)，\(B_2\)，设 \(a\in B_1\setminus B_2\)，则存在 \(b\in B_2\setminus B_1\) 使得 \((B_1\setminus \{a\})\cup\{b\}\in\mathcal{B}(M)\).

不难发现基的概念和线性空间中的基对应。

圈的性质

性质 - 2-2 对拟阵 \(M=(E,\mathcal{I})\)，

  1. \(\forall C\in\mathcal{C}(M),x\in C\)，\(C\setminus\{x\}\in\mathcal{I}\)；
  2. （1 的推论）\(\forall C\in\mathcal{C}(M)\)，\(\nexists C'\in\mathcal{C}(M)\) 使得 \(C'\subset C\)；
  3. \(\forall X\notin\mathcal{I}\)，\(\exists C\subseteq X\) 使得 \(C\in\mathcal{C}(M)\)；
  4. \(\forall C_1,C_2\in\mathcal{C}(M),x\in C_1\cap C_2\)，令 \(X=(C_1\cap C_2)\setminus\{x\}\)，则 \(\exists C\in\mathcal{C}(M)\) 使得 \(C\subseteq X\).

秩函数的性质

性质 - 2-3 对拟阵 \(M=(E,\mathcal{I})\)，

  1. \(r(\varnothing)=0\)；

  2. \(r(X)\leq r(X\cup\{x\})\leq r(X)+1,\quad \forall X\subseteq E;x\in E\)；

  3. （2 的推论）\(\forall X'\subseteq X\subseteq E\)，

    \[ 0\leq r(X)-r(X')\leq |X\setminus X'|; \]

  4. 若 \(r(X\cup\{x\})=r(X\cup\{y\})=r(X)\), 则 \(r(X\cup\{x\}\cup\{y\})=r(X),\quad \forall X\subseteq E;x,y\in E\)；

  5. （4 的推论）\(\forall X_1,X_2\subseteq E\)，若 \(\forall x\in X_2\) 均有 \(r(X_1\cup\{x\})=r(X_1)\)，则

    \[ r(X_1\cup X_2)=r(X_1); \]

  6. 函数 \(r:2^E\to \mathbf{Z}^+\) 是秩函数当且仅当以下诸款成立：

    1. \(\forall X\subseteq E\)，\(0\leq r(X)\leq |X|\)，
    2. \(\forall X\subseteq Y\subseteq E\)，\(r(X)\leq r(Y)\)，
    3. （次模性）\(\forall X,Y\subseteq E\)，\(r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y)\).

不难发现秩和秩函数的概念和线性空间中的秩对应。

闭包算子的性质

性质 - 2-4 对拟阵 \(M=(E,\mathcal{I})\)，

  1. \(\forall X\subseteq E,x\in\operatorname{cl}(X)\)，\(\operatorname{cl}(X)=\operatorname{cl}(X\cup\{x\})\)；
  2. \(\forall A\subseteq E\)，令 \(X\) 为 \(A\) 的极大独立子集，则 \(\operatorname{cl}(X)=\operatorname{cl}(A)\)；
  3. （2 的推论）\(\forall X,Y\subseteq E\)，\(r(X)=r(Y)\implies\operatorname{cl}(X)=\operatorname{cl}(Y)\)，
  4. （2 的推论）\(\forall X\subseteq E\)，\(r(X)=r(\operatorname{cl}(X))\)；
  5. \(\forall x\in E,X\subseteq E\)，\(x\in\operatorname{cl}(X)\) 当且仅当 \(x\in X\) 或存在圈 \(C\) 使得 \(C\setminus X=\{x\}\)；
  6. 算子 \(\operatorname{cl}:2^E\to 2^E\) 是闭包算子当且仅当以下诸款成立：
    1. \(\forall X\subseteq E\)，\(X\subseteq\operatorname{cl}(X)\)，
    2. \(\forall X\subseteq Y\subseteq E\)，\(\operatorname{cl}(X)\subseteq\operatorname{cl}(Y)\)，
    3. \(\forall X\subseteq E\)，\(\operatorname{cl}(X)=\operatorname{cl}(\operatorname{cl}(X))\)，
    4. （Mac Lane–Steinitz 交换性，Mac Lane–Steinitz exchange property）\(\forall a,b\in E,X\subseteq E\)，\(a\in\operatorname{cl}(X\cup\{b\})\setminus\operatorname{cl}(X)\implies b\in\operatorname{cl}(X\cup\{a\})\setminus\operatorname{cl}(X)\).

不难发现闭包和线性空间中的闭包对应。

例子

均匀拟阵

定义 - 3-1 对有限集合 \(E\) 和自然数 \(k\)，定义 \(\mathcal{I}\) 为 \(E\) 中所有满足 \(|A|\leq k\) 的子集 \(A\) 构成的集族，则称拟阵 \((E,\mathcal{I})\) 为均匀拟阵（uniform matroid），其秩为 \(k\)，记含 \(n\) 个元素且秩为 \(k\) 的均匀拟阵为 \(U_{k,n}\).

线性拟阵 / 向量拟阵

定义 - 3-2 对线性空间 \(V\) 的有限子集 \(E\)，定义 \(\mathcal{I}\) 为 \(E\) 中所有线性无关子集构成的子集族，则称拟阵 \((E,\mathcal{I})\) 为线性拟阵（linear matroid）/ 向量拟阵（vector matroid）。

图拟阵

定义 - 3-3 对有限图 \(G=\langle V,E\rangle\)，定义 \(\mathcal{I}\) 为 \(E\) 的某些子集构成的子集族，这些子集满足对任意 \(A\subseteq E\)，\(A\) 在 \(\mathcal{I}\) 中当且仅当 \(A\) 无环，则称拟阵 \((E,\mathcal{I})\) 为图拟阵（graphic matroid）。

若图 \(G\) 连通，则其图拟阵的基是生成树，圈是简单环。

划分拟阵

运算

对偶拟阵

定义 - 4-1 对拟阵 \(M=(E,\mathcal{I})\)，定义其对偶拟阵（dual matroid）为 \(M^*=(E,\mathcal{I}^*)\)，其中

\[ \mathcal{I}^*=\{A\subseteq E:\exists B\in\mathcal{B}(M),~B\subseteq E\setminus A\} \]

不难验证 \(M^*\) 是拟阵。

若 \(M\cong M^*\)，则称 \(M\) 为自对偶拟阵（self-dual matroid）。

对偶拟阵有如下性质：

性质 - 4-1 对拟阵 \(M=(E,\mathcal{I})\)，

  1. \((M^*)^*=M\)；
  2. \(M^*\) 的秩函数 \(r_{M^*}(A)=|A|+r_{M}(E\setminus A)-r_{M}(A)\).

拟阵的和

拟阵的并

相关算法

求拟阵的并

求拟阵的交

应用

Kruskal 算法的正确性证明

例题

参考文献与链接