Matroide euleriano

Sistema de independencia divisible en circuitos

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

Ejemplos

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

El plano de Fano tiene dos tipos de circuitos: conjuntos de tres puntos colineales y conjuntos de cuatro puntos que no contienen ninguna recta. 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 los grafos eulerianos

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

La definición de grafo euleriano anterior permite grafos que están desconectados, por lo que no todos los grafos de este tipo tienen un recorrido de Euler. Wilde (1975) observa que los grafos que tienen recorridos de Euler se pueden caracterizar de una manera alternativa que se generaliza a los matroides: un grafo tiene un recorrido de Euler si y solo si se puede formar a partir de algún otro grafo , y un ciclo en , contrayendo las aristas de que no pertenecen a . En el grafo contraído, generalmente deja de ser un ciclo simple y se convierte en cambio en un recorrido de Euler. Análogamente, Wilde considera los matroides que se pueden formar a partir de un matroide más grande contrayendo los elementos que no pertenecen a algún circuito particular. Muestra que esta propiedad es trivial para matroides generales (solo implica que cada elemento pertenece al menos a un circuito) pero puede usarse para caracterizar los matroides eulerianos entre los matroides binarios , matroides representables sobre GF(2) : un matroide binario es euleriano si y solo si es la contracción de otro matroide binario en un circuito. ^[2] ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle C}$

Dualidad con matroides bipartitas

Para los grafos planares , las propiedades de ser euleriano y bipartito son duales: un grafo planar es euleriano si y solo si su grafo dual es bipartito. Como demostró Welsh, esta dualidad se extiende a los matroides binarios: un matroide binario es euleriano si y solo si su matroide dual es un matroide bipartito , un matroide en el que cada circuito tiene cardinalidad par. ^{[1] [3]}

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 es euleriano, pero su dual no es bipartito, ya que sus circuitos tienen un tamaño de cinco. El matroide uniforme autodual es bipartito, pero no euleriano. ${\displaystyle U{}_{6}^{2}}$ ${\displaystyle U{}_{6}^{4}}$ ${\displaystyle U{}_{6}^{3}}$

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 maneras 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 la matroide completa tiene un número impar de particiones en circuitos. ^[4] Lovász y Seress (1993) recopilan varias caracterizaciones adicionales de matroides binarias eulerianas, 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 al oráculo y, por lo tanto, no puede tomar tiempo polinomial. En particular, es difícil distinguir un matroide uniforme en un conjunto de elementos, con todos los ciclos de tamaño , de un matroide de pavimentación que se diferencia del matroide uniforme en tener dos ciclos complementarios de tamaño . El matroide de pavimentación es euleriano, pero el matroide uniforme no lo es. Cualquier algoritmo de oráculo, aplicado al matroide uniforme, debe realizar consultas, un número exponencial, para verificar que la entrada no sea en cambio una instancia del matroide de pavimentación. ^[6] ${\displaystyle 2n}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle {\tbinom {2n}{n}}/2}$

Extensión euleriana

Si es un matroide binario que no es euleriano, entonces tiene una extensión euleriana única , un matroide binario cuyos elementos son los elementos de junto con un elemento adicional , de modo que la restricción de a los elementos de es isomorfa a . El dual de es un matroide bipartito formado a partir del dual de sumando a cada circuito impar. ^[7] ${\displaystyle M}$ ${\displaystyle {\bar {M}}}$ ${\displaystyle M}$ ${\displaystyle e}$ ${\displaystyle {\bar {M}}}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle {\bar {M}}}$ ${\displaystyle M}$ ${\displaystyle e}$

Referencias

1. Welsh, DJA (1969), "Matroides de Euler y bipartitos", 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), "Matroides versus grafos", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, vol. 110, Berlín: Springer, págs. 155–170, doi :10.1007/BFb0060114, MR  0263666.
4. Shikare, MM (2001), "Nuevas caracterizaciones de matroides binarias eulerianas y bipartitas" (PDF) , Indian Journal of Pure and Applied Mathematics , 32 (2): 215–219, MR  1820861, archivado desde el original (PDF) el 2015-07-06 , consultado el 2012-08-28.
5. Lovász, László ; Seress, Ákos (1993), "La red de cociclos de matroides binarias", European Journal of Combinatorics , 14 (3): 241–250, doi : 10.1006/eujc.1993.1027 , SEÑOR  1215334.
6. Jensen, Per M.; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedades de matroides", SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR  0646772.
7. Sebő, András (1990), "El problema del flujo múltiple cográfico: un epílogo", Combinatoria poliédrica (Morristown, NJ, 1989) , DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 1, Providence, RI: Amer. Math. Soc., págs. 203–234, MR  1105128.