独立集合族

【どくりつしゅうごうぞく (independent set family)】

有限集合 $N$ とその部分集合族 ${\cal I}$ が以下の (I0)--(I2) を満たすとき, ${\bf M}=(N,{\cal I})$ をマトロイドと呼び, ${\cal I}$ を ${\bf M}$ の独立集合族と呼ぶ. \vspace{-0.6zw} \begin{description} \item[(I0)] $\emptyset\in{\cal I}$. \vspace{-0.6zw} \item[(I1)] $I\subseteq J\in{\cal I}\Rightarrow I\in{\cal I}$. \vspace{-0.6zw} \item[(I2)] $I,J\in{\cal I}$, $|I|<|J|\Rightarrow\exists j\in J\backslash I$: $I\cup\{j\}\in{\cal I}$. \end{description}