matroide euleriana

Sistema de independencia divisible en circuitos.

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

Ejemplos

En una matroide uniforme , los circuitos son conjuntos de exactamente elementos. Por lo tanto, una matroide uniforme es euleriana si y sólo si es divisor de . Por ejemplo, las rectas de puntos son eulerianas si y sólo si son divisibles 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 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. Así, el plano de Fano también es euleriano.

Relación con los gráficos eulerianos

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 gráfico de este tipo pueden dividirse en ciclos simples, de lo que se deduce que las matroides gráficas de los gráficos eulerianos son ejemplos de matroides eulerianas. ^[1]

La definición anterior de un gráfico euleriano permite gráficos que están desconectados, por lo que no todos los gráficos 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 matroides: un grafo tiene un recorrido de Euler si y sólo si se puede formar a partir de algún otro grafo , y un ciclo en , mediante la contracción. los bordes de eso no pertenecen . En la gráfica contraída, generalmente deja de ser un simple ciclo y se convierte en un recorrido de Euler. De manera análoga, Wilde considera que las matroides pueden formarse a partir de una matroide más grande contrayendo los elementos que no pertenecen a ningún circuito en particular. Muestra que esta propiedad es trivial para las matroides generales (implica sólo 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 sólo si es la contracción de otra matroide binaria en un circuito. ^[2] ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle C}$

Dualidad con matroides bipartitas

Para grafos planos , las propiedades de ser euleriano y bipartito son duales: un grafo plano es euleriano si y sólo si su grafo dual es bipartito. Como demostró Welsh, esta dualidad se extiende a las matroides binarias: una matroide binaria es euleriana si y sólo si su matroide dual es una matroide bipartita , una matroide en la que cada circuito tiene cardinalidad par. ^{[1] [3]}

Para las matroides que no son binarias, la dualidad entre las matroides eulerianas y bipartitas puede romperse. Por ejemplo, la matroide uniforme es euleriana pero su dual no es bipartita, ya que sus circuitos tienen tamaño cinco. La matroide uniforme autodual es bipartita pero no euleriana. ${\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 formas alternativas. La caracterización de Wilde (1975) es un ejemplo; dos más son que una matroide binaria es euleriana si y sólo si cada elemento pertenece a un número impar de circuitos, si y sólo si toda la matroide 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 una matroide determinada es euleriana, al tener acceso a la 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 polinómico. En particular, es difícil distinguir una matroide uniforme sobre un conjunto de elementos, con todos los ciclos de tamaño , de una matroide pavimentadora que se diferencia de la matroide uniforme por tener dos ciclos complementarios de tamaño . La matroide pavimentadora es euleriana pero la matroide uniforme no lo es. Cualquier algoritmo de Oracle, aplicado a la matroide uniforme, debe realizar consultas, un número exponencial, para verificar que la entrada no sea una instancia de la matroide pavimentadora. ^[6] ${\displaystyle 2n}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle {\tbinom {2n}{n}}/2}$

extensión euleriana

Si es una matroide binaria que no es euleriana, entonces tiene una extensión euleriana única , una matroide binaria 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 una matroide bipartita formada a partir del dual de agregando 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), "Euler y las matroides bipartitas", 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 binarias", 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 gráficos", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Michigan, 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) en 06 de julio de 2015 , consultado el 28 de agosto de 2012.
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 , MR  1215334.
6. Jensen, por M.; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedades matroides", SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR  0646772.
7. Sebő, András (1990), "El problema cográfico de flujo múltiple: un epílogo", Combinatoria poliédrica (Morristown, Nueva Jersey, 1989) , DIMACS Ser. Matemáticas discretas. Teoría. Computadora. Ciencia, vol. 1, Providencia, RI: Amer. Matemáticas. Soc., págs. 203–234, SEÑOR  1105128.