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 ]}

In any vector space, and more generally in any matroid, a minimum weight basis may be found by a greedy algorithm that considers potential basis elements one at a time, in sorted order by their weights, and that includes an element in the basis when it is linearly independent of the previously chosen basis elements. Testing for linear independence can be done by Gaussian elimination. However, an undirected graph may have an exponentially large set of simple cycles, so it would be computationally infeasible to generate and test all such cycles.

Horton (1987) provided the first polynomial time algorithm for finding a minimum weight basis, in graphs for which every edge weight is positive. His algorithm uses this generate-and-test approach, but restricts the generated cycles to a small set of ${\displaystyle O(mn)}$ cycles, called Horton cycles. A Horton cycle is a fundamental cycle of a shortest path tree of the given graph. There are at most n different shortest path trees (one for each starting vertex) and each has fewer than m fundamental cycles, giving the bound on the total number of Horton cycles. As Horton showed, every cycle in the minimum weight cycle basis is a Horton cycle.^[13] Using Dijkstra's algorithm to find each shortest path tree and then using Gaussian elimination to perform the testing steps of the greedy basis algorithm leads to a polynomial time algorithm for the minimum weight cycle basis. Subsequent researchers have developed improved algorithms for this problem,^{[14][15][16][17]} reducing the worst-case time complexity for finding a minimum weight cycle basis in a graph with ${\displaystyle m}$ edges and ${\displaystyle n}$ vertices to ${\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 ]}