Base de ciclo
En la teoría de grafos , una rama de las matemáticas, una base de ciclo de un gráfico no dirigido es un conjunto de ciclos simples que forma una base del espacio de ciclo del gráfico. Es decir, es un conjunto mínimo de ciclos que permite que cada subgrafo de grado par se exprese como una diferencia simétrica de ciclos base.
Se puede formar una base de ciclo fundamental a partir de cualquier árbol de expansión o bosque de expansión del gráfico dado, seleccionando los ciclos formados por la combinación de un camino en el árbol y un solo borde fuera del árbol. Alternativamente, si los bordes del gráfico tienen pesos positivos, la base del ciclo de peso mínimo puede construirse en tiempo polinomial .
En gráficos planos , el conjunto de ciclos acotados de una incrustación del gráfico forma una base de ciclo. La base del ciclo de peso mínimo de un gráfico plano corresponde al árbol de Gomory-Hu del gráfico dual .
Un subgrafo generador de un grafo dado G tiene el mismo conjunto de vértices que el propio G pero, posiblemente, menos aristas. Se dice que un grafo G , o uno de sus subgrafos, es euleriano si cada uno de sus vértices tiene grado par (su número de aristas incidentes). Todo ciclo simple en un grafo es un subgrafo euleriano, pero puede haber otros. El espacio de ciclo de un grafo es la colección de sus subgrafos eulerianos. Forma un espacio vectorial sobre el campo finito de dos elementos . La operación de suma de vectores es la diferencia simétricade dos o más subgrafos, que forma otro subgrafo formado por las aristas que aparecen un número impar de veces en los argumentos de la operación diferencia simétrica. [1]
Una base de ciclo es una base de este espacio vectorial en el que cada vector base representa un ciclo simple. Consiste en un conjunto de ciclos que se pueden combinar, usando diferencias simétricas, para formar cada subgrafo euleriano, y que es mínimo con esta propiedad. Cada base de ciclo de un gráfico dado tiene el mismo número de ciclos, lo que equivale a la dimensión de su espacio de ciclo. Este número se llama el rango del circuito del gráfico, y es igual a donde es el número de aristas en el gráfico, es el número de vértices y es el número de componentes conectados . [2]
Se han estudiado varios tipos especiales de bases cíclicas, incluidas las bases cíclicas fundamentales, las bases cíclicas débilmente fundamentales, las bases cíclicas dispersas (o de 2) y las bases cíclicas integrales. [3]
