独立集合族のソースを表示

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

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

<table>
   <tr><td>(I0)</td> <td><math>\emptyset\in{\mathcal I}\,</math>.</td></tr>
   <tr><td>(I1)</td> <td><math>I\subseteq J\in{\mathcal I}\Rightarrow I\in{\mathcal I}\,</math>.</td></tr>
   <tr><td>(I2)</td> <td><math>I,J\in{\mathcal I}\,</math>, <math>|I|<|J|\Rightarrow\exists j\in J\backslash I\,</math>:
<math>I\cup\{j\}\in{\mathcal I}\,</math>.</td></tr>
</table>