拟阵理论简述

拟阵

拟阵( matroid )是一个数学结构，是对（线性）独立的概括与归纳。常用于排列组合和图论等方面。 – 维基百科

拟阵就是满足如下条件的序偶$M=(S,I)$：
1. $S$是一个有限集合；
2. $I$是$S$的子集的非空族，这些子集称为独立子集，使得$if$$B\in I$且$A\subseteq B$,则$A \in I$。注意，$\emptyset \in I$;
3. $if$$A \in I$且$B \in I$,$|A|<|B|$,那么存在某个元素$x \in B-A$,使得$A \bigcup{x} \in I$,则称$M$满足交换性质。

拟阵理论描述了很多贪心方法生成最优解的问题。

图拟阵

图拟阵与最小生成树紧密相关。
在寻找最小生成树时，贪心算法（Kruskal 算法与Prime 算法都为贪心算法）非常有效的原因是图的森林集合形成一个图拟阵。
图拟阵定义 $M_G=(S_G,I_G)$
- $S_G为G$的边集
- $if$$A$是$E$的子集，则$A \in I_G$当且仅当$A$是无圈的，即$G_A=(V,A)$是一个森林。