2部マトロイド
2部マトロイド(bipartite matroid)は、サーキットのサイズがすべて偶数であるようなマトロイドである。
例
[編集]一様マトロイド は、 が奇数のとき、かつそのときのみ2部マトロイドである。これは、一様マトロイドのサーキットのサイズが であるからである。
2部グラフとの関係
[編集]2部マトロイドは、Welsh (1969)によって、2部グラフのグラフ的マトロイドの一般化として定義された。グラフ的マトロイドが2部マトロイドであることと、グラフが2部グラフであることは同値である[1]。
オイラーマトロイドの双対
[編集]オイラーグラフは、すべての頂点の次数が偶数であるようなグラフだが、平面グラフにおいて2部グラフの双対はオイラーグラフとなる。Welsh (1969)は、これがマトロイドにも拡張できることを示した。つまり、2値マトロイドにおいて、2部マトロイドの双対はオイラーマトロイドとなる。
2値マトロイドでない場合、そうなるとは限らない。例えば、一様マトロイド は2部マトロイドではないが、この双対はオイラーマトロイドである。また、一様マトロイド は2部マトロイドであるが、オイラーマトロイドではない。
計算の複雑さ
[編集]与えられた2値マトロイドが2部マトロイドかを多項式時間でテストすることが可能である[2]。しかし、与えられたマトロイドがオイラーマトロイドであるかを、独立性オラクルを介してテストするには、指数回のオラクルアクセスを必要とする[3]。
参考文献
[編集]- ^ 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.
- ^ 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.
- ^ Jensen, Per M.; Korte, Bernhard (1982), “Complexity of matroid property algorithms”, SIAM Journal on Computing 11 (1): 184–190, doi:10.1137/0211014, MR646772.