マトロイドの例

ここでは何種類かの重要なマトロイドについて述べる。

例[自明マトロイド]

空でない有限集合$E$に対して、 空集合だけが独立集合であるような$E$上のマトロイドが定義できる。 このようなマトロイドは、 $E$上の自明マトロイド(trivial matroid)と呼ばれる。

自明マトロイドの基は$\emptyset$のみである。 従ってその階数は$0$である。

例[離散マトロイド]

すべての部分集合を独立集合とすることにより、$E$上のマトロイドが定まる。 これを離散マトロイド(discrete matroid)と呼ぶ。 $E$上の離散マトロイドには基がひとつしかなく、それは$E$自身である。 また任意の部分集合$A$の階数は、 $A$の元の個数である。

例[一様マトロイド]

$k$元部分集合をすべて基とすることにより定まる、 $E$上のマトロイドを$k$-一様マトロイド($k-$uniform matroid)と呼ぶ。 自明マトロイド、離散マトロイドは それぞれ$0$-、$|E|$-一様マトロイドである。 独立集合は$E$の$k$個以下の元を含む部分集合であり、任意の部分集合$A$の階数は $|A|$または$k$ のどちらか小さいほうに等しい。

例[グラフ的マトロイド]

グラフの閉路マトロイドと 同型なマトロイドを、 グラフ的マトロイド(graphic matroid)と呼ぶ。

例[コグラフ的マトロイド]

グラフ$G$に対して、カットセットの性質により、 $G$のカットセットの全体を閉路の全体とするマトロイドが定義できる。 それを$G$のカットセットマトロイドと呼び、$M^*(G)$と書く。

カットセットマトロイドと同型なマトロイドを、 コグラフ的マトロイド(cographic matroid)と呼ぶ。

例[平面的マトロイド]

グラフ的かつコグラフ的マトロイドを、 平面的マトロイド(planar matroid)と呼ぶ。