拟阵笔记

拟阵笔记

（注：本篇内容参考于2018国家候选队选手杨乾澜的论文。）

拟阵的定义

拟阵\(M=(S,T)\)，其中\(S\)为一个有限集，\(T\)为该有限集的独立集组成的集合。显然，有\(T\subseteq 2^S\)（\(2^S\)表示S的所有子集组成的集合，也叫\(S\)的幂集）。

拟阵需要满足以下公理：

• 如果\(I\in T,J \subseteq I\)那么\(J\in I\)。（拟阵的遗传性）
• 如果\(I,J\in T\)，且\(|J|>|I|\)，那么存在元素\(z\in J\)\\(I\)满足\(I \cup z\in T\)。（拟阵的扩张性）

如果\(I\in T\)，则称\(I\)是独立集，通常认为空集也是独立集。

满足以上两条，即可认为是一个拟阵模型。

拟阵的极大独立集称作基，拟阵的极小非独立集称作环。可以证明，基和环的大小唯一。

由于拟阵有不止一个大小都相同的基，所以我们根据扩张性，可以证明将所有的元素按权值从大到小排序，挨个看插入后是否仍然为独立集来判断该元素是否能插入。插入结束时得到权值最大的基。（贪心)

证明具体看论文。

拟阵的一些应用

无向图的生成森林为拟阵问题。

线性基为拟阵问题。

拟阵笔记

原文：https://www.cnblogs.com/surculosaoi/p/13081185.html