Matroide euleriano

En la teoría matroide , una matroide euleriana es una matroide cuyos elementos pueden dividirse en una colección de circuitos disjuntos.

Ejemplos

En un uniforme matroid ${\displaystyle U{}_{n}^{r}}$, los circuitos son los conjuntos de exactamente ${\displaystyle r+1}$elementos. Por lo tanto, una matroide uniforme es euleriana si y solo si${\displaystyle r+1}$ es un divisor de ${\displaystyle n}$. Por ejemplo, el${\displaystyle n}$-líneas de puntos ${\displaystyle U{}_{n}^{2}}$ son eulerianos si y solo si ${\displaystyle n}$ es divisible por tres.

El plano de Fano tiene dos tipos de circuitos: conjuntos de tres puntos colineales y conjuntos de cuatro puntos que no contienen ninguna línea. Los circuitos de tres puntos son los complementos de los circuitos de cuatro puntos, por lo que es posible dividir los siete puntos del plano en dos circuitos, uno de cada tipo. Por tanto, el plano de Fano también es euleriano.

Relación con las gráficas eulerianas

Las matroides eulerianas fueron definidas por Welsh (1969) como una generalización de las gráficas eulerianas , gráficas en las que cada vértice tiene un grado par. Según el teorema de Veblen, los bordes de cada uno de estos gráficos pueden dividirse en ciclos simples, de lo que se deduce que las matroides gráficas de los gráficos eulerianos son ejemplos de matroides eulerianos. ^[1]

La definición de un gráfico euleriano anterior permite gráficos que están desconectados, por lo que no todos los gráficos tienen un recorrido de Euler. Wilde (1975) observa que las gráficas que tienen recorridos de Euler se pueden caracterizar de una manera alternativa que generaliza a las matroides: una gráfica${\displaystyle G}$ tiene un recorrido de Euler si y solo si se puede formar a partir de algún otro gráfico ${\displaystyle H}$y un ciclo ${\displaystyle C}$ en ${\displaystyle H}$, contrayendo los bordes de${\displaystyle H}$ que no pertenecen a ${\displaystyle C}$. En el gráfico contraído,${\displaystyle C}$generalmente deja de ser un ciclo simple y se convierte en su lugar en un tour de Euler. De manera análoga, Wilde considera las matroides que se pueden formar a partir de una matroide más grande al contraer los elementos que no pertenecen a algún circuito en particular. Él muestra que esta propiedad es trivial para las matroides generales (implica solo que cada elemento pertenece al menos a un circuito) pero puede usarse para caracterizar las matroides eulerianas entre las matroides binarias , matroides representables sobre GF (2) : una matroide binaria es Euleriano si y solo si es la contracción de otra matroide binaria en un circuito. ^[2]

Dualidad con matroides bipartitas

Para los gráficos planos , las propiedades de ser euleriano y bipartito son duales: un gráfico plano es euleriano si y solo si su gráfico dual es bipartito. Como mostró Welsh, esta dualidad se extiende a las matroides binarias: una matroide binaria es euleriana si y solo si su matroide dual es una matroide bipartita , una matroide en la que cada circuito tiene incluso cardinalidad. ^{[1] [3]}

Para las matroides que no son binarias, la dualidad entre las matroides eulerianas y bipartitas puede romperse. Por ejemplo, el uniforme matroide${\displaystyle U{}_{6}^{2}}$ es euleriano pero su dual ${\displaystyle U{}_{6}^{4}}$no es bipartito, ya que sus circuitos tienen un tamaño de cinco. La matroide uniforme auto-dual${\displaystyle U{}_{6}^{3}}$ es bipartita pero no euleriana.

Caracterizaciones alternativas

Debido a la correspondencia entre las matroides eulerianas y bipartitas entre las matroides binarias, las matroides binarias que son eulerianas pueden caracterizarse de formas alternativas. La caracterización de Wilde (1975) es un ejemplo; dos más son que una matroide binaria es euleriana si y solo si cada elemento pertenece a un número impar de circuitos, si y solo si toda la matroide tiene un número impar de particiones en circuitos. ^[4] Lovász & Seress (1993) recopilan varias caracterizaciones adicionales de matroides binarios eulerianos, de las cuales derivan un algoritmo de tiempo polinomial para probar si una matroide binaria es euleriana. ^[5]

Complejidad computacional

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. ^[6]

Extensión euleriana

Si ${\displaystyle M}$es una matroide binaria que no es euleriana, entonces tiene una extensión euleriana única , una matroide binaria${\displaystyle {\bar {M}}}$ cuyos elementos son los elementos de ${\displaystyle M}$ junto con un elemento adicional ${\displaystyle e}$, tal que la restricción de ${\displaystyle {\bar {M}}}$ a los elementos de ${\displaystyle M}$ es isomorfo a ${\displaystyle M}$. El dual de${\displaystyle {\bar {M}}}$ es un matroide bipartito formado a partir del dual de ${\displaystyle M}$ añadiendo ${\displaystyle e}$a todos los circuitos impares. ^[7]

Referencias

1. Welsh, DJA (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory , 6 : 375–377, doi : 10.1016 / s0021-9800 (69) 80033-5 , MR  0237368.
2. Wilde, PJ (1975), "El teorema del circuito de Euler para matroides binarios", Journal of Combinatorial Theory , Serie B, 18 : 260-264, doi : 10.1016 / 0095-8956 (75) 90051-9 , MR 0384577 .
3. Harary, Frank ; Welsh, Dominic (1969), "Matroids versus graphs", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, 110 , Berlín: Springer, págs. 155-170, doi : 10.1007 / BFb0060114 , MR 0263666 .
4. Shikare, MM (2001), "Nuevas caracterizaciones de las matroides binarias bipartitas y eulerianas" (PDF) , Indian Journal of Pure and Applied Mathematics , 32 (2): 215-219, MR 1820861 , archivado desde el original (PDF) en 2015-07-06 , consultado el 2012-08-28   .
5. 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 .
6. 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 .
7. Sebő, András (1990), "El problema del multiflujo cográfico: un epílogo", Combinatoria poliédrica (Morristown, NJ, 1989) , DIMACS Ser. Matemáticas discretas. Theoret. Computación. Sci., 1 , Providence, RI: Amer. Matemáticas. Soc., Págs. 203-234, MR 1105128 .