基によるマトロイドの定義

$B_{1}$と$B_{2}$が$G$の全域木であり、$e$が$B_{1}$の辺ならば、 $B_{2}$の辺$f$で$(B_{1} - \{ e \}) \union \{ f \}$ （すなわち、$B_{1}$の$e$を$f$で入れかえて得られるグラフ）も、 $G$の全域木になるような$f$を見つけることができる。 同様な結果が、ベクトル空間についても成り立つ。 この性質を抽象することにより、マトロイドの第一の定義を得る。

マトロイド$M$とは、空でない有限集合$E$と、$E$の部分集合の空でない族${\cal B}$の対で、 以下の条件をみたすものを言う。

基(i)

${\cal B}$の相異なる2元$B_{1}, B_{2}$に対して、$B_{1} \not \subset B_{2}$.

基(ii)

${\cal B}$の任意の2元$B_{1}, \, B_{2}$と$e\in B_{1}$に対して、$f\in B_{2}$で、 $(B_{1} \setminus \{ e \}) \union \{ f \} \in {\cal B}$をみたすものが存在する。

${\cal B}$の元を、$M$の基と呼ぶ。 マトロイド$M$のどの基にも、同じ個数の元が含まれている。 その個数のことを、$M$の階数(rank)と呼ぶ。

マトロイドの同型

マトロイド$M=(E,{\cal B})$と$M' = (E',{\cal B}')$に対して、 全単射$f:M \rightarrow M'$で、

\[ A \in {\cal B} \iff f(A) \in {\cal B}' \forall A \subset E \]

をみたすものが存在するとき、$M$と$M'$は同型(isomorphic)であるという。