首页/拟阵math.matroid 页面信息 拟阵有限集上满足遗传性与交换公理的独立集族;极大独立集称为基,秩是子集的最大独立集大小。标签 数学 / 拟阵 / 独立集 / 交换公理 / 回路定义设 𝐸 有限。ℐ︀⊆2𝐸 若满足:∅∈ℐ︀;𝐴∈ℐ︀、𝐵⊆𝐴 时 𝐵∈ℐ︀;对任意 𝐴,𝐵∈ℐ︀ 且 |𝐴|<|𝐵|,存在 𝑏∈𝐵∖𝐴 使 𝐴∪{𝑏}∈ℐ︀。第三条称为交换公理。满足上述条件时,称 (𝐸,ℐ︀) 为拟阵,ℐ︀ 中元素为独立集;不属于 ℐ︀ 的子集称为依赖集。基与秩极大独立集称为基。对 𝐴⊆𝐸,秩定义为𝑟(𝐴)=max{|𝐵|:𝐵⊆𝐴,𝐵∈ℐ︀}.基的等势性与交换性见 拟阵基定理;常见模型见 拟阵实例。回路若 𝐶⊆𝐸 不是独立集,且对任意 𝑒∈𝐶 都有 𝐶∖{𝑒}∈ℐ︀,则称 𝐶 为回路。等价地,回路是极小的依赖集。设 𝐼 独立、𝑦∉𝐼,且 𝐼∪{𝑦} 依赖。则 𝐼∪{𝑦} 含有唯一回路,称为 𝑦 关于 𝐼 的基本回路,记作 𝐶𝐼(𝑦)。它一定包含 𝑦,并由 𝑦 及所有满足 (𝐼∖{𝑥})∪{𝑦} 独立的 𝑥∈𝐼 组成。