2部マトロイド(bipartite matroid)は、サーキットのサイズがすべて偶数であるようなマトロイドである。

一様マトロイド   は、   が奇数のとき、かつそのときのみ2部マトロイドである。これは、一様マトロイドのサーキットのサイズが   であるからである。

2部グラフとの関係

編集

2部マトロイドは、Welsh (1969)によって、2部グラフグラフ的マトロイドの一般化として定義された。グラフ的マトロイドが2部マトロイドであることと、グラフが2部グラフであることは同値である[1]

オイラーマトロイドの双対

編集

オイラーグラフは、すべての頂点の次数が偶数であるようなグラフだが、平面グラフにおいて2部グラフの双対はオイラーグラフとなる。Welsh (1969)は、これがマトロイドにも拡張できることを示した。つまり、2値マトロイドにおいて、2部マトロイドの双対はオイラーマトロイドとなる。

2値マトロイドでない場合、そうなるとは限らない。例えば、一様マトロイド   は2部マトロイドではないが、この双対はオイラーマトロイドである。また、一様マトロイド   は2部マトロイドであるが、オイラーマトロイドではない。

計算の複雑さ

編集

与えられた2値マトロイドが2部マトロイドかを多項式時間でテストすることが可能である[2]。しかし、与えられたマトロイドがオイラーマトロイドであるかを、独立性オラクルを介してテストするには、指数回のオラクルアクセスを必要とする[3]

参考文献

編集
  1. ^ Welsh, D. J. A. (1969), “Euler and bipartite matroids”, Journal of Combinatorial Theory 6: 375–377, doi:10.1016/s0021-9800(69)80033-5, MR0237368 .
  2. ^ Lovász, László; Seress, Ákos (1993), “The cocycle lattice of binary matroids”, European Journal of Combinatorics 14 (3): 241–250, doi:10.1006/eujc.1993.1027, MR1215334 .
  3. ^ Jensen, Per M.; Korte, Bernhard (1982), “Complexity of matroid property algorithms”, SIAM Journal on Computing 11 (1): 184–190, doi:10.1137/0211014, MR646772 .