2019-09-27
本文以矩阵交相关内容为主,忽略掉了大部分证明,感兴趣的读者请自行阅读集训队论文。
拟阵的定义
记 M=(S,L) 表示一个定义在有限集 S 上,独立集的集合为 L 的拟阵。其中 L 是 S 的一些子集构成的集合。拟阵 M 满足以下公理:
- (遗传性). 如果 I∈L,J⊆I,那么 J∈L。
- (交换性). 如果 I,J∈L 且 ∣I∣<∣J∣,那么 ∃x∈J∖I 满足 I∪{x}∈L。
如果 I∈L,我们称 I 是独立的,也称 I 是独立集;否则,我们称 I 是不独立的,也成 I 是非独立集。通常,我们认为 ∅ 是独立的。