基族

【きぞく (base family)】

マトロイド $\mathbf {M} =(N,{\mathcal {I}})\,$ において, 極大な独立集合を基と呼ぶ. すべての基を集めた基族 ${\mathcal {B}}\,$ は以下の $(\mathbf {B0} )-(\mathbf {B1} )\,$ を満たす.

$(\mathbf {B0} )\,$ ${\mathcal {B}}\neq \emptyset \,$.

$(\mathbf {B1} )\,$ $B,F\in {\mathcal {B}}\,$, $i\in B\backslash F\Rightarrow \exists j\in F\backslash B\,$: $(B\backslash \{i\})\cup \{j\}\in {\mathcal {B}}\,$.

逆に, $(\mathbf {B0} )-(\mathbf {B1} )\,$ を満たす部分集合族 ${\mathcal {B}}\,$ によってマトロイドを定義することもできる.