Base cíclica

Cada grafo tiene una base de ciclos en la que cada ciclo es un ciclo inducido . En un grafo conexo de 3 vértices , siempre existe una base que consiste en ciclos periféricos , ciclos cuya eliminación no separa el grafo restante. ^{[ 4 ] [ 5 ]} En cualquier grafo que no sea uno formado al agregar una arista a un ciclo, un ciclo periférico debe ser un ciclo inducido.

Si${\displaystyle T}$es un árbol de expansión o bosque de expansión de un grafo dado${\displaystyle G}$, y${\displaystyle e}$es un borde que no pertenece a${\displaystyle T}$, luego el ciclo fundamental${\displaystyle C_{e}}$definido por${\displaystyle e}$es el ciclo simple que consiste en${\displaystyle e}$junto con el camino en${\displaystyle T}$conectar los puntos finales de${\displaystyle e}$. Hay exactamente${\displaystyle m-n+c}$ciclos fundamentales, uno por cada arista que no pertenece a${\displaystyle T}$Cada uno de ellos es linealmente independiente de los ciclos restantes, porque incluye una arista.${\displaystyle e}$que no está presente en ningún otro ciclo fundamental. Por lo tanto, los ciclos fundamentales forman una base para el espacio de ciclos. ^{[ 1 ] [ 2 ]} Una base de ciclos construida de esta manera se llama base de ciclos fundamental o base de ciclos fuertemente fundamental . ^{[ 3 ]}

También es posible caracterizar bases de ciclos fundamentales sin especificar el árbol para el cual son fundamentales. Existe un árbol para el cual una base de ciclos dada es fundamental si y solo si cada ciclo contiene una arista que no está incluida en ningún otro ciclo base, es decir, cada ciclo es independiente de los demás. De ello se deduce que una colección de ciclos es una base de ciclos fundamental de${\displaystyle G}$si y solo si tiene la propiedad de independencia y tiene el número correcto de ciclos para ser una base de${\displaystyle G}$. ^{[ 6 ]}

Una base de ciclos se denomina débilmente fundamental si sus ciclos pueden colocarse en un orden lineal tal que cada ciclo incluya al menos una arista que no esté incluida en ningún ciclo anterior. Una base de ciclos fundamental es automáticamente débilmente fundamental (para cualquier orden de aristas). ^{[ 3 ] [ 7 ]} Si cada base de ciclos de un grafo es débilmente fundamental, lo mismo ocurre con cada menor del grafo. Basándose en esta propiedad, la clase de grafos (y multigrafos ) para los que cada base de ciclos es débilmente fundamental puede caracterizarse por cinco menores prohibidos : el grafo de la pirámide cuadrada , el multigrafo formado al duplicar todas las aristas de un ciclo de cuatro vértices, dos multigrafos formados al duplicar dos aristas de un tetraedro y el multigrafo formado al triplicar las aristas de un triángulo. ^{[ 8 ]}

Si un grafo planar finito conexo se incrusta en el plano, cada cara de la incrustación está delimitada por un ciclo de aristas. Una cara es necesariamente no delimitada (incluye puntos arbitrariamente alejados de los vértices del grafo) y las caras restantes están delimitadas. Según la fórmula de Euler para grafos planares , hay exactamente${\displaystyle m-n+1}$caras acotadas. La diferencia simétrica de cualquier conjunto de ciclos de caras es el límite del conjunto de caras correspondiente, y diferentes conjuntos de caras acotadas tienen límites diferentes, por lo que no es posible representar el mismo conjunto como una diferencia simétrica de ciclos de caras de más de una manera; esto significa que el conjunto de ciclos de caras es linealmente independiente. Como un conjunto linealmente independiente de suficientes ciclos, necesariamente forma una base de ciclos. ^{[ 9 ]} Siempre es una base de ciclos débilmente fundamental, y es fundamental si y solo si la incrustación del grafo es exteriorplanar .

Para grafos correctamente incrustados en otras superficies de modo que todas las caras de la incrustación sean discos topológicos, no es cierto en general que exista una base de ciclos que utilice solo ciclos de caras. Los ciclos de caras de estas incrustaciones generan un subconjunto propio de todos los subgrafos eulerianos. El grupo de homología${\ Displaystyle H_ {2} (S, \ mathbb {Z} _ {2})}$de la superficie dada${\displaystyle S}$caracteriza los subgrafos eulerianos que no pueden representarse como el límite de un conjunto de caras. El criterio de planaridad de Mac Lane utiliza esta idea para caracterizar los grafos planares en términos de las bases de ciclos: un grafo finito no dirigido es planar si y solo si tiene una base de ciclos dispersa o 2-base , ^{[ 3 ]} una base en la que cada arista del grafo participa en como máximo dos ciclos de la base. En un grafo planar, la base de ciclos formada por el conjunto de caras acotadas es necesariamente dispersa, y a la inversa, una base de ciclos dispersa de cualquier grafo forma necesariamente el conjunto de caras acotadas de una incrustación planar de su grafo. ^{[ 9 ] [ 10 ]}

El espacio cíclico de un grafo puede interpretarse utilizando la teoría de la homología como el grupo de homología.${\ Displaystyle H_ {1} (G, \ mathbb {Z} _ {2})}$de un complejo simplicial con un punto por cada vértice del grafo y un segmento de línea por cada arista del grafo. Esta construcción puede generalizarse al grupo de homología.${\displaystyle H_{1}(G,R)}$sobre un anillo arbitrario${\displaystyle R}$. Un caso especial importante es el anillo de enteros , para el cual el grupo de homología${\displaystyle H_{1}(G,\mathbb {Z} )}$es un grupo abeliano libre , un subgrupo del grupo abeliano libre generado por las aristas del grafo. De forma menos abstracta, este grupo se puede construir asignando una orientación arbitraria a las aristas del grafo dado; entonces los elementos de${\displaystyle H_{1}(G,\mathbb {Z} )}$son etiquetas de las aristas del grafo mediante números enteros con la propiedad de que, en cada vértice, la suma de las etiquetas de las aristas entrantes es igual a la suma de las etiquetas de las aristas salientes. La operación de grupo es la suma de estos vectores de etiquetas. Una base de ciclos enteros es un conjunto de ciclos simples que genera este grupo. ^{[ 3 ]}

En cualquier espacio vectorial, y más generalmente en cualquier matroide , se puede encontrar una base de peso mínimo mediante un algoritmo voraz que considera los elementos potenciales de la base uno a uno, ordenados según sus pesos, e incluye un elemento en la base cuando es linealmente independiente de los elementos de la base previamente elegidos. La prueba de independencia lineal se puede realizar mediante eliminación gaussiana . Sin embargo, un grafo no dirigido puede tener un conjunto exponencialmente grande de ciclos simples, por lo que sería computacionalmente inviable generar y probar todos esos ciclos.

Horton (1987) proporcionó el primer algoritmo de tiempo polinomial para encontrar una base de peso mínimo, en grafos para los cuales cada peso de arista es positivo. Su algoritmo utiliza este enfoque de generar y probar, pero restringe los ciclos generados a un pequeño conjunto de${\displaystyle O(mn)}$ciclos, llamados ciclos de Horton . Un ciclo de Horton es un ciclo fundamental de un árbol de caminos más cortos del grafo dado. Hay como máximo n árboles de caminos más cortos diferentes (uno para cada vértice inicial) y cada uno tiene menos de m ciclos fundamentales, lo que da el límite del número total de ciclos de Horton. Como demostró Horton, cada ciclo en la base de ciclos de peso mínimo es un ciclo de Horton. ^{[ 13 ]} Usando el algoritmo de Dijkstra para encontrar cada árbol de caminos más cortos y luego usando la eliminación gaussiana para realizar los pasos de prueba del algoritmo de base voraz conduce a un algoritmo de tiempo polinomial para la base de ciclos de peso mínimo. Investigadores posteriores han desarrollado algoritmos mejorados para este problema, ^{[ 14 ] [ 15 ] [ 16 ] [ 17 ]} reduciendo la complejidad temporal del peor caso para encontrar una base de ciclos de peso mínimo en un grafo con${\displaystyle m}$bordes y${\displaystyle n}$vértices a${\displaystyle O(m^{2}n/\log n)}$. ^{[ 18 ]}

Encontrar la base fundamental con el peso mínimo posible está estrechamente relacionado con el problema de encontrar un árbol de expansión que minimice el promedio de las distancias por pares; ambos son NP-difíciles . ^{[ 19 ]} Encontrar una base débilmente fundamental de peso mínimo también es NP-difícil, ^{[ 7 ]} y aproximarla es MAXSNP-difícil . ^{[ 20 ]} Si se permiten pesos negativos y ciclos con peso negativo, entonces encontrar una base de ciclo mínimo (sin restricciones) también es NP-difícil, ya que puede usarse para encontrar un ciclo hamiltoniano : si un grafo es hamiltoniano y a todas las aristas se les da un peso de − 1, entonces una base de ciclo de peso mínimo necesariamente incluye al menos un ciclo hamiltoniano.

La base de ciclos de peso mínimo para un grafo planar no es necesariamente la misma que la base formada por sus caras acotadas: puede incluir ciclos que no son caras, y algunas caras pueden no estar incluidas como ciclos en la base de ciclos de peso mínimo. Sin embargo, existe una base de ciclos de peso mínimo en la que no hay dos ciclos que se crucen: para cada par de ciclos en la base, o bien los ciclos encierran subconjuntos disjuntos de las caras acotadas, o bien uno de los dos ciclos encierra al otro. Este conjunto de ciclos corresponde, en el grafo dual del grafo planar dado, a un conjunto de cortes que forman un árbol de Gomory-Hu del grafo dual, la base de peso mínimo de su espacio de cortes . ^{[ 21 ]} Basándose en esta dualidad, se puede construir una representación implícita de la base de ciclos de peso mínimo en un grafo planar en tiempo${\displaystyle O(n\log ^{3}n)}$. ^{[ 22 ]}