拟阵简介(unfin)
拟阵最早由 Hassler Whitney 于 1935 年作为线性相关的推广提出。拟阵理论在组合数学、最优化、图论等领域有很多应用。拟阵可以用来证明贪心算法的正确性,如 Kruskal 算法、匈牙利算法等。
定义
拟阵有许多等价定义,为方便起见,我们先给出基于独立集的定义。
拟阵
定义 - 1-1(基于独立集的拟阵定义)
定义 \(M=(E,\mathcal{I})\),其中 \(E\) 是有限集合,\(\mathcal{I}\) 是 \(E\) 的子集族。若 \(\mathcal{I}\) 满足:
- \(\varnothing\in\mathcal{I}\),
- (遗传性,hereditary property)\(\forall A'\subseteq A\subseteq E\),\(A\in\mathcal{I}\implies A'\in\mathcal{I}\),
- (独立集的交换性,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})\),
- 拟阵的极大独立集是最大独立集,即 \(\forall B_1,B_2\in\mathcal{B}(M)\),\(|B_1|=|B_2|\);
- (1 的推论)\(\forall B\in\mathcal{B}(M)\),\(\nexists B'\in\mathcal{B}(M)\) 使得 \(B'\subset B\);
- 对任意 \(X\in\mathcal{I}\) 均存在 \(B\in\mathcal{B}(M)\) 使得 \(X\subseteq B\);
- (基的交换性,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})\),
- \(\forall C\in\mathcal{C}(M),x\in C\),\(C\setminus\{x\}\in\mathcal{I}\);
- (1 的推论)\(\forall C\in\mathcal{C}(M)\),\(\nexists C'\in\mathcal{C}(M)\) 使得 \(C'\subset C\);
- \(\forall X\notin\mathcal{I}\),\(\exists C\subseteq X\) 使得 \(C\in\mathcal{C}(M)\);
- \(\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})\),
\(r(\varnothing)=0\);
\(r(X)\leq r(X\cup\{x\})\leq r(X)+1,\quad \forall X\subseteq E;x\in E\);
(2 的推论)\(\forall X'\subseteq X\subseteq E\),
\[ 0\leq r(X)-r(X')\leq |X\setminus X'|; \]
若 \(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\);
(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); \]
函数 \(r:2^E\to \mathbf{Z}^+\) 是秩函数当且仅当以下诸款成立:
- \(\forall X\subseteq E\),\(0\leq r(X)\leq |X|\),
- \(\forall X\subseteq Y\subseteq E\),\(r(X)\leq r(Y)\),
- (次模性)\(\forall X,Y\subseteq E\),\(r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y)\).
不难发现秩和秩函数的概念和线性空间中的秩对应。
闭包算子的性质
性质 - 2-4 对拟阵 \(M=(E,\mathcal{I})\),
- \(\forall X\subseteq E,x\in\operatorname{cl}(X)\),\(\operatorname{cl}(X)=\operatorname{cl}(X\cup\{x\})\);
- \(\forall A\subseteq E\),令 \(X\) 为 \(A\) 的极大独立子集,则 \(\operatorname{cl}(X)=\operatorname{cl}(A)\);
- (2 的推论)\(\forall X,Y\subseteq E\),\(r(X)=r(Y)\implies\operatorname{cl}(X)=\operatorname{cl}(Y)\),
- (2 的推论)\(\forall X\subseteq E\),\(r(X)=r(\operatorname{cl}(X))\);
- \(\forall x\in E,X\subseteq E\),\(x\in\operatorname{cl}(X)\) 当且仅当 \(x\in X\) 或存在圈 \(C\) 使得 \(C\setminus X=\{x\}\);
- 算子 \(\operatorname{cl}:2^E\to 2^E\) 是闭包算子当且仅当以下诸款成立:
- \(\forall X\subseteq E\),\(X\subseteq\operatorname{cl}(X)\),
- \(\forall X\subseteq Y\subseteq E\),\(\operatorname{cl}(X)\subseteq\operatorname{cl}(Y)\),
- \(\forall X\subseteq E\),\(\operatorname{cl}(X)=\operatorname{cl}(\operatorname{cl}(X))\),
- (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})\),
- \((M^*)^*=M\);
- \(M^*\) 的秩函数 \(r_{M^*}(A)=|A|+r_{M}(E\setminus A)-r_{M}(A)\).
拟阵的和
拟阵的并
相关算法
求拟阵的并
求拟阵的交
应用
Kruskal 算法的正确性证明
例题
参考文献与链接
- Introduction to Graph Theory (5th Edition) : Wilson, Robin J.
- Matroid - Wikipedia
- [Tutorial] Matroid intersection in simple words - Codeforces
- 从拟阵基础到 Shannon 开关游戏 - zghtyarecrenj 的博客 - 洛谷博客