独立集合族

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

有限集合 $N\,$ とその部分集合族 ${\mathcal I}\,$ が以下の (I0)-(I2) を満たすとき, ${\mathbf M}=(N,{\mathcal I})\,$ をマトロイドと呼び, ${\mathcal I}\,$ を ${\mathbf M}\,$ の独立集合族と呼ぶ.

(I0)	$\emptyset\in{\mathcal I}\,$ .
(I1)	$I\subseteq J\in{\mathcal I}\Rightarrow I\in{\mathcal I}\,$ .
(I2)	$I,J\in{\mathcal I}\,$ , $\|I\|<\|J\|\Rightarrow\exists j\in J\backslash I\,$ : $I\cup\{j\}\in{\mathcal I}\,$ .