基族

【きぞく (base family)】

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

\vspace{-0.4zw} \begin{description} \item[(B0)] ${\cal B}\neq\emptyset$. \vspace{-0.7zw} \item[(B1)] $B,F\in{\cal B}$, $i\in B\backslash F\Rightarrow\exists j\in F\backslash B$: $(B\backslash\{i\})\cup\{j\}\in{\cal B}$. \end{description} \vspace{-0.4zw}

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