子集系统

一个 子集系统 是一个有序二元组 $(E,\mathfrak I)$

$E$ 是一个非空集合

$\mathfrak I$ 是 $E$ 的一个 子集族 （符合一定规则的的子集的集合）

$\mathfrak I$ 在包含运算下 封闭 ，即满足遗传性质

​ $\forall a\in \mathfrak I,a\subseteq E$

​ $\forall a'\subseteq a,a'\in\mathfrak I$

子集系统的 最大独立集 ：将 $\mathfrak I$ 中的元素都称为独立集，对于 $\mathfrak I$ 中的元素 $a$ ，若不存在 $\mathfrak I$ 中的另一个元素 $a'$ 使得 $a\subset a'$ ，则称 $a$ 是极大独立集。

极大独立集的 基数 为它包含的元素个数。

子集系统最优化问题

加权子集系统 ： $E$ 中每个元素都被赋予了一个严格大于 $0$ 的权重 $w(x)$ ，一个子集的权重为所有元素之和，即 $$\begin{align}w(A)=\sum_{x\in A}w(x),A\subseteq E\end{align}$ $

优化问题 ：在子集系统中选取 $S\in \mathfrak I$ 使得 $w(S)$ 最大

拟阵

拟阵是一个有序二元组 $M=(E,\mathfrak I)$

$E$ 是一个非空有限集，称为基础集。 $\mathfrak I$ 是 $E$ 的一个有限非空子集族。

它满足三个条件：

1、独立集公理： $\varnothing\in\mathfrak I$

2、可遗传性：若 $A\in\mathfrak I,A'\subset A$ ，则 $A'\in\mathfrak I$

3、独立扩充公理（交换性质）：若 $A,B\in\mathfrak I$ 且 $|A|<|B|$ ，则存在 $x\in B-A$ ，使得 $A\cup{x}\in\mathfrak I$

$\mathfrak I$ 中的极大独立集称为拟阵的 基 。

拟阵所有基的大小相同，否则可以扩充。

拟阵的秩就是基的大小，拟阵的并仍是拟阵。

加权拟阵上的贪心算法

一个子集系统是拟阵当且仅当其所有极大独立集具有相同的基数，可以用这一点判断一个子集系统是否是拟阵。

加权拟阵的 最大权极大独立集问题 ：寻找独立集 $A\in\mathfrak I$ 使得 $w(A)$ 最大。

将所有的 $e\in E$ 按 $w(e)$ 排序，如果可以加入，就把他加入 $A$ 中，这种做法当且仅当在拟阵中正确，也就是说一旦确定系统是一个拟阵，就有了一个贪心策略。

这是因为拟阵具有贪心选择性质和最优子结构性质。

贪心选择性质：对于 $E$ 中权值最小的独立元素 $x$ ，必然存在一个最优解 $A$ 使得 $x\in A$ 。

最优子结构性质：如果 $x$ 是第一个贪心选出的元素，那么后面的问题还可以归结为一个拟阵上的最大独立集问题。

常见模型

$kruskal$ ：图拟阵： $E$ 是边集， $\mathfrak I$ 是图森林的集合。

线性基：线性基的维数是固定的，所以最大独立集也是拟阵。