2部マトロイド

2部マトロイド("bipartite matroid")は、サーキットのサイズがすべて偶数であるようなマトロイドである。
例.
一様マトロイド formula_1 は、 formula_2 が奇数のとき、かつそのときのみ2部マトロイドである。これは、一様マトロイドのサーキットのサイズが formula_3 であるからである。
2部グラフとの関係.
2部マトロイドは、によって、2部グラフのグラフ的マトロイドの一般化として定義された。グラフ的マトロイドが2部マトロイドであることと、グラフが2部グラフであることは同値である。
オイラーマトロイドの双対.
オイラーグラフは、すべての頂点の次数が偶数であるようなグラフだが、平面グラフにおいて2部グラフの双対はオイラーグラフとなる。は、これがマトロイドにも拡張できることを示した。つまり、2値マトロイドにおいて、2部マトロイドの双対はオイラーマトロイドとなる。
2値マトロイドでない場合、そうなるとは限らない。例えば、一様マトロイド formula_4 は2部マトロイドではないが、この双対はオイラーマトロイドである。また、一様マトロイド formula_5 は2部マトロイドであるが、オイラーマトロイドではない。
計算の複雑さ.
与えられた2値マトロイドが2部マトロイドかを多項式時間でテストすることが可能である。しかし、与えられたマトロイドがオイラーマトロイドであるかを、独立性オラクルを介してテストするには、指数回のオラクルアクセスを必要とする。