2部マトロイドのソースを表示

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

==例==
[[一様マトロイド]] <math>U{}^r_n</math> は、 <math>r</math> が奇数のとき、かつそのときのみ2部マトロイドである。これは、一様マトロイドのサーキットのサイズが <math>r+1</math> であるからである。

==2部グラフとの関係==
2部マトロイドは、{{harvtxt|Welsh|1969}}によって、[[2部グラフ]]の[[グラフ的マトロイド]]の一般化として定義された。グラフ的マトロイドが2部マトロイドであることと、グラフが2部グラフであることは同値である<ref name="w69">{{citation
 | last = Welsh | first = D. J. A.
 | journal = Journal of Combinatorial Theory
 | mr = 0237368
 | pages = 375–377
 | title = Euler and bipartite matroids
 | volume = 6
 | year = 1969
 | doi=10.1016/s0021-9800(69)80033-5| doi-access = free
 }}.</ref>。

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

2値マトロイドでない場合、そうなるとは限らない。例えば、一様マトロイド <math>U{}^4_6</math> は2部マトロイドではないが、この双対はオイラーマトロイドである。また、一様マトロイド <math>U{}^3_6</math> は2部マトロイドであるが、オイラーマトロイドではない。

==計算の複雑さ==
与えられた2値マトロイドが2部マトロイドかを[[多項式時間]]でテストすることが可能である<ref>{{citation
 | last1 = Lovász | first1 = László | author1-link = ラースロー・ロヴァース
 | last2 = Seress | first2 = Ákos
 | doi = 10.1006/eujc.1993.1027
 | issue = 3
 | journal = European Journal of Combinatorics
 | mr = 1215334
 | pages = 241–250
 | title = The cocycle lattice of binary matroids
 | volume = 14
 | year = 1993}}.</ref>。しかし、与えられたマトロイドがオイラーマトロイドであるかを、独立性オラクルを介してテストするには、指数回のオラクルアクセスを必要とする<ref>{{citation
 | last1 = Jensen | first1 = Per M.
 | last2 = Korte | first2 = Bernhard
 | doi = 10.1137/0211014
 | issue = 1
 | journal = SIAM Journal on Computing
 | mr = 646772
 | pages = 184–190
 | title = Complexity of matroid property algorithms
 | volume = 11
 | year = 1982}}.</ref>。

==参考文献==
{{reflist}}

{{DEFAULTSORT:にふまとろいと}}
[[Category:マトロイド理論]]
[[Category:数学に関する記事]]