之前听讲课自闭了好久，后面补了一下，还是记下来免得忘了
# 定义
- 子集系统
子集系统是一个二元组 $M=(S,L)$，其中：
- $S$ 是一个有限集；
- $L$ 是一个以 $S$ 的子集为元素的集合，其中 $L$ 的元素是 $S$ 中的所有独立集；
性质-遗传性：若 $B\in L$，则任意 $A\subseteq B$ 满足 $A\in L$，因此 $\varnothing$ 也是 $L$ 的元素。
- 拟阵
拟阵是一种特殊的子集系统，满足交换性：对任意 $A,B\in L$，且 $|A|<|B|$，存在一个 $x\in B,x\not\in A$ 使得 $A\cup\{x\}\in L$。
eg.
对于最小生成树问题，这样定义拟阵：
- $S$ 是边集 $E$
- $T\subseteq S$；则 $T\in L$ 当且仅当 $T$ 无环
由于 $T$ 本身无环，那么 $T$ 的子集一定也无环，满足遗传性。
对于 $A,B\in L,|A|<|B|$，可知 $A$ 不是一棵生成树（边数不足），那么一定存在从 $B$ 中取出一个不属于 $A$ 的边 $x$ 加入 $A$，使得 $A+\{x\}$ 也无环，满足交换性。
- 独立集
这个是我自己的理解，不一定准确
在定义拟阵时，我们定义了一种“运算规则”，在这种运算规则下，若集合 $A$ 中的任意一个元素都不能被 $A$ 中的其他元素根据这种运算规则表达出来，则 $A$ 被称为独立集。
极大独立集被称为基；极小非独立集被称为回路。
可以发现独立集满足：独立集的任意子集都是独立集（类似于遗传性），那么 $\varnothing$ 也是独立集。
而极大独立集满足：向极大独立集中加入任何一个其他元素，都会变成非独立集。
- 秩函数
对于 $U\subseteq S$，定义 $r(U)$ 为 $U$ 的子集中的最大独立集的大小，即
则成 $r(U)$ 为 $U$ 的秩，而 $r$ 为该拟阵的秩函数。
# 拟阵最优性问题 - 贪心
- 问题
对于拟阵 $M=(S,L)$，对 $x\in S$ 定义 $w(x)$ 表示 $x$ 的权值，对集合 $U\subseteq S$ 定义 $w(U)$：
求 $M$ 中权值最大的独立集。
- 解决
将初始独立集 $A$ 设为 $\varnothing$。
先给所有元素 $x$ 按 $w(x)$ 从大到小排序；从大到小枚举 $x$，若 $x$ 加入 $A$ 后 $A$ 仍然是独立集（也就是 $A+\{x\}\in L$），则把 $x$ 加入 $A$。
最后得到的 $A$ 就是答案。
伪代码：
复杂度分析：设判断 $A\cup\{x\}\in L$ 需要 $f(n)$ 的复杂度
> Hint
一般来说，判断一个集合是否为独立集的复杂度是多项式复杂度。
则算法复杂度为 $O\left[n\log n+n\cdot f(n)\right]$。
# 特殊拟阵 - 线性基
- 概念
1. 线性空间
$V$ 是一个含“0”元素的非空集合，$F$ 是一个含单位元和“0”元素的数域，对 $V$ 中的元素定义两种运算：
- 加法：满足对于任意 $a,b\in V$，有 $a+b\in V$；
- 数乘：满足对于任意 $a\in V,k\in F$，有 $ka\in V$；
其中加法满足交换律、结合律，并且“0”加任何 $a\in V$ 均为 $a$。
数乘满足分配律、结合律，并且单位元乘任何 $a\in V$ 均为 $a$，零元素（$F$ 中的）乘任何 $a\in V$ 都为零元素（$V$ 中的）。
则称 $V$ 是 $F$ 上的一个线性空间。
2. 线性表出
若向量组 $(\alpha_1,\alpha_2,\dots,\alpha_m)$ （$\alpha_1,\alpha_2,\dots,\alpha_m\in V$），若 $\beta\in V$ 满足存在 $c_1,c_2,\dots,c_m\in F$ 使得：
> Hint.
这里的乘法加法均是在线性空间定义下的
则称 $\beta$ 可以被 $(\alpha_1,\alpha_2,\dots,\alpha_m)$ 线性表出。
3. 线性相关
对于向量组 $(\alpha_1,\alpha_2,\dots,\alpha_m)$ ，若存在 $c_1,c_2,\dots,c_m\in F$ 使得
则称 $(\alpha_1,\alpha_2,\dots,\alpha_m)$ 线性相关，反之则称为线性无关。
> Hint.
这意味着存在 $\alpha_i$ 可以被 $(\alpha_1,\dots,\alpha_{i-1},\alpha_{i+1},\alpha_m)$ 线性表出。
4. 极大线性无关组
类似于极大独立集——基。
性质：向极大线性无关组中加入任意一个元素，就会变为线性相关。
- 线性基
线性空间的定义：$V$ 为 $\mathbb N$(自然数集)，$F$ 为 $\{0,1\}$，“数乘”为整数乘法，“加法”为异或。
对于一个 $S\subseteq\mathbb N$，记 $S$ 的张成为 $\text{span}(S)$，即能用 $S$ 线性表出的所有元素集合：
对于这个线性空间来说，若 $S$ 中存在元素 $x$ 使 $S’=S-\{x\}$ 满足 $x\in\text{span}(S’)$ ，则 $S$ 线性相关，若不存在则称为线性无关。
对于 $S\subseteq V$，称集合 $B$ 是 $S$ 的线性基，当且仅当：
- $S\subseteq\text{span}(B)$，不一定要完全等于；
- $B$ 线性无关。
于是可以得到两个显然的性质：
- $S$ 中任意元素都可以被 $B$ 线性表出；
- $B$ 的任意一个真子集都不是线性基；
写不完了 gugugu இ௰இ