拟阵

有限集上满足遗传性与交换公理的独立集族;极大独立集称为基,秩是子集的最大独立集大小。

标签 数学 / 拟阵 / 独立集 / 交换公理 / 回路

定义

设 𝐸 有限。ℐ︀⊆2𝐸 若满足:

  • ∅∈ℐ︀;
  • 𝐴∈ℐ︀、𝐵⊆𝐴 时 𝐵∈ℐ︀;
  • 对任意 𝐴,𝐵∈ℐ︀ 且 |𝐴|<|𝐵|,存在 𝑏∈𝐵∖𝐴 使 𝐴∪{𝑏}∈ℐ︀。

第三条称为交换公理。满足上述条件时,称 (𝐸,ℐ︀) 为拟阵,ℐ︀ 中元素为独立集;不属于 ℐ︀ 的子集称为依赖集。

基与秩

极大独立集称为基。对 𝐴⊆𝐸,秩定义为

𝑟(𝐴)=max{|𝐵|:𝐵⊆𝐴,𝐵∈ℐ︀}.

基的等势性与交换性见 拟阵基定理;常见模型见 拟阵实例。

回路

若 𝐶⊆𝐸 不是独立集,且对任意 𝑒∈𝐶 都有 𝐶∖{𝑒}∈ℐ︀,则称 𝐶 为回路。等价地,回路是极小的依赖集。

设 𝐼 独立、𝑦∉𝐼,且 𝐼∪{𝑦} 依赖。则 𝐼∪{𝑦} 含有唯一回路,称为 𝑦 关于 𝐼 的基本回路,记作 𝐶𝐼(𝑦)。它一定包含 𝑦,并由 𝑦 及所有满足 (𝐼∖{𝑥})∪{𝑦} 独立的 𝑥∈𝐼 组成。

源码位置