フリーマトロイド

数学において、与えられた基底集合E上の自由マトロイドは、独立集合がすべてEの部分集合であるマトロイドである。これは一様マトロイドの特殊なケースである。^[1]このマトロイドの唯一の基底は基底集合E自体である。E上のマトロイドの中で、 E上の自由マトロイドは独立集合が最も多く、ランクが最も高く、回路が最も少ない。

マトロイド を何らかの要素 によって自由に拡張したもの(と表記)は、 の要素に新しい要素を加えたマトロイドであり、次のようになります。 ${\displaystyle M}$${\displaystyle e\not \in M}$${\displaystyle M+e}$${\displaystyle M}$${\displaystyle e}$

• その回路はの回路とのすべての基数に対する集合を足したものになる。^[2]${\displaystyle M}$${\displaystyle B\cup \{e\}}$ ${\displaystyle B}$${\displaystyle M}$
• 同様に、その独立集合は の独立集合に、基底ではないすべての独立集合の集合を加えたものです。${\displaystyle M}$${\displaystyle I\cup \{e\}}$${\displaystyle I}$
• 同様に、その基底はの基底に、サイズ のすべての独立集合の集合を加えたものです。${\displaystyle M}$${\displaystyle I\cup \{e\}}$${\displaystyle {\text{rank}}(M)-1}$