En matemáticas, un matroide bipartito es un matroide cuyos circuitos tienen un tamaño uniforme .
Ejemplo
Una matroide uniforme es bipartito si y solo si es un número impar, porque los circuitos en tal matroide tienen tamaño .
Relación con los gráficos bipartitos
Las matroides bipartitas fueron definidas por Welsh (1969) como una generalización de los gráficos bipartitos , gráficos en los que cada ciclo tiene un tamaño uniforme. Un matroide gráfico es bipartito si y solo si proviene de un gráfico bipartito. [1]
Dualidad con las matroides eulerianas
Un grafo euleriano es aquel en el que todos los vértices tienen un grado par; Los gráficos eulerianos pueden estar desconectados. Para los gráficos planos , las propiedades de ser bipartito y euleriano son duales: un gráfico plano es bipartito si y solo si su gráfico dual es euleriano. Como mostró Welsh, esta dualidad se extiende a las matroides binarias : una matroide binaria es bipartita si y solo si su matroide dual es una matroide euleriana , una matroide que puede dividirse en circuitos disjuntos.
Para las matroides que no son binarias, la dualidad entre las matroides eulerianas y bipartitas puede romperse. Por ejemplo, el uniforme matroide no es bipartito pero es dual es euleriano, ya que se puede dividir en dos 3 ciclos. La matroide uniforme auto-dual es bipartita pero no euleriana.
Complejidad computacional
Es posible probar en tiempo polinomial si una matriz binaria dada es bipartita. [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]
Referencias
- ↑ Welsh, DJA (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory , 6 (4): 375-377, doi : 10.1016 / s0021-9800 (69) 80033-5 , MR 0237368.
- ^ 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 , MR 1215334.
- ^ Jensen, Per M .; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedad matroide", SIAM Journal on Computing , 11 (1): 184-190, doi : 10.1137 / 0211014 , MR 0646772.