独立集合族

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

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