マトロイド

有限集合 $E$ と、$E$ の部分集合の族 $\mathcal{I}$（その元を独立集合という）の組 $(E,\mathcal{I})$ がマトロイドであるとは、次の 3 条件を満たすことをいう。

• (I1) $\varnothing\in\mathcal{I}$。
• (I2)（遺伝性）$J\subseteq I\in\mathcal{I}$ ならば $J\in\mathcal{I}$。
• (I3)（交換公理）$I,J\in\mathcal{I}$ かつ $|I|<|J|$ ならば、$I\cup\{x\}\in\mathcal{I}$ となる $x\in J\setminus I$ が存在する。

$E$ の部分集合 $A$ の極大独立部分集合（$A$ に含まれる独立集合のうち、包含で極大のもの）を、$A=E$ のとき基という。