拟阵

对于 \(n\) 个元素的集合 \(S\)，其一些子集组成了集合 \(L\)。若满足以下性质：

• 遗传性：对于任意 \(B\in L,C\subseteq B\)，有 \(C\in L\)；
• 扩展性：对于任意 \(A,B \in L\)，若 \(|A|<|B|\)，有 \(\exists x\in B,x\notin A,A\cup{\{x\}}\in L\)。

则称二元组 \((S,L)\) 为一个拟阵。对于拟阵，有一下定义：

• \(L\) 中的元素叫独立集；
• 不能继续扩展的独立集叫极大独立集。

定理：

• 所有极大独立集大小相等。

在拟阵上贪心是有正确性的。我们给 \(S\) 中每个元素赋一个权值 \(w_x\)。对于拟阵，若要选出一个权值和最大的极大独立集，可以直接排序使用贪心解决。