基族

出典: ORWiki

【きぞく (base family)】

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

(\mathbf{B0})\, \mathcal{B}\neq\emptyset\,.

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

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

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E5%9F%BA%E6%97%8F" より作成