基族のソースを表示

'''【きぞく (base family)】'''

マトロイド <math>\mathbf{M}=(N,\mathcal{I})\,</math> において, 極大な独立集合を基と呼ぶ. すべての基を集めた基族 <math>\mathcal{B}\,</math> は以下の <math>(\mathbf{B0})-(\mathbf{B1})\,</math> を満たす. 

<math>(\mathbf{B0})\,</math> <math>\mathcal{B}\neq\emptyset\,</math>. 

<math>(\mathbf{B1})\,</math> <math>B,F\in\mathcal{B}\,</math>, 
<math>i\in B\backslash F\Rightarrow\exists j\in F\backslash B\,</math>:
<math>(B\backslash\{i\})\cup\{j\}\in\mathcal{B}\,</math>. 

逆に, <math>(\mathbf{B0})-(\mathbf{B1})\,</math> を満たす部分集合族 <math>\mathcal{B}\,</math> によってマトロイドを定義することもできる.

[[Category:グラフ･ネットワーク|きぞく]]