En matemáticas, un matroide bipartito es un matroide cuyos circuitos tienen todos el mismo tamaño.
Un matroide uniforme es bipartito si y sólo si es un número impar, porque los circuitos en dicho matroide tienen tamaño .
Los matroides bipartitos fueron definidos por Welsh (1969) como una generalización de los grafos bipartitos , grafos en los que cada ciclo tiene un tamaño par. Un matroide gráfico es bipartito si y sólo si proviene de un grafo bipartito. [1]
Un grafo euleriano es aquel en el que todos los vértices tienen grado par; los grafos eulerianos pueden estar desconectados. Para los grafos planos , las propiedades de ser bipartito y euleriano son duales: un grafo plano es bipartito si y solo si su grafo dual es euleriano. Como mostró Welsh, esta dualidad se extiende a los matroides binarios : un matroide binario es bipartito si y solo si su matroide dual es un matroide euleriano , un matroide que puede dividirse en circuitos disjuntos.
En el caso de los matroides que no son binarios, la dualidad entre los matroides eulerianos y bipartitos puede romperse. Por ejemplo, el matroide uniforme no es bipartito, pero su dual es euleriano, ya que se puede dividir en dos ciclos de 3. El matroide uniforme autodual es bipartito, pero no euleriano.
Es posible probar en tiempo polinomial si un matroide binario dado es bipartito. [2] Sin embargo, cualquier algoritmo que pruebe si un matroide dado es euleriano, dado acceso al matroide a través de un oráculo de independencia , debe realizar un número exponencial de consultas de oráculo y, por lo tanto, no puede tomar tiempo polinomial. [3]
