一様マトロイド
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
Eを有限集合とし、ある整数r以下の要素数を持つ2Eの部分集合をFとするとき、(E,F)はマトロイドとなる。これを、一様マトロイド（英語版） (uniform matroid)と呼び、n=|E|としたとき U n r {\displaystyle U_{n}^{r}} などと書く。 U n r {\displaystyle U_{n}^{r}} における基は、要素数がrであるようなEの部分集合であり、サーキットは要素数がr+1であるようなEの部分集合である。また、一様マトロイドの直和は分割マトロイド（英語版） (partition matroid)と呼ばれる。具体的には、 B 1 , … , B k {\displaystyle B_{1},\ldots ,B_{k}} を互いに素な集合とし、それぞれに 0 ≤ d i ≤ | B i | {\displaystyle 0\leq d_{i}\leq |B_{i}|} ( 0 ≤ i ≤ k {\displaystyle 0\leq i\leq k} )を定めたとき、 0 ≤ i ≤ k {\displaystyle 0\leq i\leq k} それぞれにおいて | I ∩ B i | ≤ d i {\displaystyle |I\cap B_{i}|\leq d_{i}} を満たすような I ⊂ ⋃ i B i {\displaystyle I\subset \bigcup _{i}B_{i}} の集合をFとすれば、マトロイドとなる。
※この「一様マトロイド」の解説は、「マトロイド」の解説の一部です。
「一様マトロイド」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
- 一様マトロイドのページへのリンク
