基族
において, 
は以下の 
を
. 
, 
: 
. | グラフ･ネットワーク： | 劣モジュラ関数 同形性 基多面体 基族 基本分割 多品種フロー 多項式時間アルゴリズム |
基族
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
有限集合 E {\displaystyle E} と B ⊆ 2 E {\displaystyle {\mathcal {B}}\subseteq 2^{E}} とする。 B {\displaystyle {\mathcal {B}}} がマトロイド (E,F) の基族であるための必要十分条件は次の(B1),(B2)が成り立つことである。 (B1) B ≠ ∅ {\displaystyle {\mathcal {B}}\neq \emptyset } (B2) 任意の B ′ , B ″ ∈ B , x ∈ B ′ ∖ B ″ {\displaystyle B',B''\in {\mathcal {B}},x\in B'\setminus B''} について ( B ′ ∖ { x } ) ∪ { y } ∈ B {\displaystyle (B'\setminus \{x\})\cup \{y\}\in {\mathcal {B}}} となる y ∈ B ″ ∖ B ′ {\displaystyle y\in {B''}\setminus {B'}} が存在する。 基が1つしかない場合は明らかにマトロイドとなる。そうでない場合、例えば E = { 1 , 2 , 3 } {\displaystyle E=\{1,2,3\}} , B = { { 1 , 2 } , { 2 , 3 } , { 1 , 3 } } {\displaystyle {\mathcal {B}}=\{\{1,2\},\{2,3\},\{1,3\}\}} とすると B {\displaystyle {\mathcal {B}}} は(B1)及び(B2)を満たす。このような基の族を持つマトロイドは、一様マトロイド U 3 2 {\displaystyle U_{3}^{2}} ただ１つに決まることが分かる。また、基族が B = { { 1 , 2 } , { 3 } } {\displaystyle {\mathcal {B}}=\{\{1,2\},\{3\}\}} のときは(B2)を満たさないため、この基族ではマトロイドにならない。事実、 F = { { 1 } , { 2 } , { 3 } , { 1 , 2 } } {\displaystyle F=\{\{1\},\{2\},\{3\},\{1,2\}\}} とすると、この例の基族となるが、(A3)を満たさずマトロイドになっていない。
※この「基族」の解説は、「マトロイド」の解説の一部です。
「基族」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
- >> 「基族」を含む用語の索引
- 基族のページへのリンク
