En teoría de grafos , una rama de las matemáticas , el espacio de ciclo (binario) de un grafo no dirigido es el conjunto de sus subgrafos de grado par .
Este conjunto de subgrafos se puede describir algebraicamente como un espacio vectorial sobre el cuerpo finito de dos elementos . La dimensión de este espacio es el rango de circuito del grafo. El mismo espacio también se puede describir en términos de topología algebraica como el primer grupo de homología del grafo. Utilizando la teoría de homología, el espacio de ciclo binario se puede generalizar a espacios de ciclo sobre anillos arbitrarios .
El espacio de ciclo de un gráfico se puede describir con niveles crecientes de sofisticación matemática como un conjunto de subgráficos, como un espacio vectorial binario o como un grupo de homología .
Un subgrafo generador de un grafo dado G puede definirse a partir de cualquier subconjunto S de las aristas de G . El subgrafo tiene el mismo conjunto de vértices que el propio G (este es el significado de la palabra "generador") pero tiene los elementos de S como aristas. Por lo tanto, un grafo G con m aristas tiene 2 m subgrafos generadores, incluyendo al propio G así como al grafo vacío en el mismo conjunto de vértices que G . La colección de todos los subgrafos generadores de un grafo G forma el espacio de aristas de G . [1] [2]
Un grafo G , o uno de sus subgrafos, se dice que es euleriano si cada uno de sus vértices tiene un número par de aristas incidentes (este número se llama grado del vértice). Esta propiedad recibe su nombre de Leonhard Euler , quien demostró en 1736, en su trabajo sobre los Siete Puentes de Königsberg , que un grafo conexo tiene un recorrido que visita cada arista exactamente una vez si y solo si es euleriano. Sin embargo, para los fines de definir espacios de ciclos, un subgrafo euleriano no necesita ser conexo; por ejemplo, el grafo vacío, en el que todos los vértices están desconectados entre sí, es euleriano en este sentido. El espacio de ciclos de un grafo es la colección de sus subgrafos eulerianos que lo abarcan. [1] [2]
Si se aplica una operación de conjunto, como la unión o la intersección de conjuntos, a dos subgrafos de un grafo dado, el resultado será nuevamente un subgrafo. De esta manera, el espacio de aristas de un grafo arbitrario puede interpretarse como un álgebra de Boole . [3]
El espacio de ciclos también tiene una estructura algebraica, pero más restrictiva. La unión o intersección de dos subgrafos eulerianos puede no ser euleriana. Sin embargo, la diferencia simétrica de dos subgrafos eulerianos (el grafo que consiste en las aristas que pertenecen exactamente a uno de los dos grafos dados) es nuevamente euleriana. [1] Esto se deduce del hecho de que la diferencia simétrica de dos conjuntos con un número par de elementos también es par. Aplicando este hecho por separado a los vecindarios de cada vértice se muestra que el operador de diferencia simétrica conserva la propiedad de ser euleriano.
Una familia de conjuntos cerrados bajo la operación de diferencia simétrica se puede describir algebraicamente como un espacio vectorial sobre el cuerpo finito de dos elementos . [4] Este cuerpo tiene dos elementos, 0 y 1, y sus operaciones de adición y multiplicación se pueden describir como la familiar adición y multiplicación de números enteros , tomados módulo 2 . Un espacio vectorial consiste en un conjunto de elementos junto con una operación de adición y multiplicación escalar que satisface ciertas propiedades que generalizan las propiedades de los familiares espacios vectoriales reales . Para el espacio cíclico, los elementos del espacio vectorial son los subgrafos eulerianos, la operación de adición es la diferenciación simétrica, la multiplicación por el escalar 1 es la operación identidad , y la multiplicación por el escalar 0 lleva cada elemento al gráfico vacío, que forma el elemento identidad aditivo para el espacio cíclico.
El espacio de aristas es también un espacio vectorial sobre con la diferencia simétrica como adición. Como espacios vectoriales, el espacio de ciclos y el espacio de corte del grafo (la familia de conjuntos de aristas que abarcan los cortes del grafo) son los complementos ortogonales entre sí dentro del espacio de aristas. Esto significa que un conjunto de aristas en un grafo forma un corte si y solo si cada subgrafo euleriano tiene un número par de aristas en común con , y forma un subgrafo euleriano si y solo si cada corte tiene un número par de aristas en común con . [2] Aunque estos dos espacios son complementos ortogonales, algunos grafos tienen subgrafos no vacíos que pertenecen a ambos. Un subgrafo de este tipo (un corte euleriano) existe como parte de un grafo si y solo si tiene un número par de bosques de expansión . [5]
Un grafo no dirigido puede ser visto como un complejo simplicial con sus vértices como símplices de dimensión cero y las aristas como símplices unidimensionales. [6] El complejo de cadena de este espacio topológico consiste en su espacio de aristas y espacio de vértices (el álgebra booleana de conjuntos de vértices), conectados por un operador de frontera que asigna cualquier subgrafo generador (un elemento del espacio de aristas) a su conjunto de vértices de grado impar (un elemento del espacio de vértices). El grupo de homología
consiste en los elementos del espacio de aristas que se asignan al elemento cero del espacio de vértices; estos son exactamente los subgrafos eulerianos. Su operación de grupo es la operación de diferencia simétrica sobre subgrafos eulerianos.
Reemplazar en esta construcción por un anillo arbitrario permite extender la definición de espacios de ciclos a espacios de ciclos con coeficientes en el anillo dado, que forman módulos sobre el anillo. [7] En particular, el espacio de ciclo integral es el espacio
Se puede definir en términos de teoría de grafos eligiendo una orientación arbitraria del grafo y definiendo un ciclo integral de un grafo como una asignación de números enteros a los bordes de (un elemento del grupo abeliano libre sobre los bordes) con la propiedad de que, en cada vértice, la suma de los números asignados a los bordes entrantes es igual a la suma de los números asignados a los bordes salientes. [8]
Un miembro de o de (el espacio de ciclo módulo ) con la propiedad adicional de que todos los números asignados a los bordes son distintos de cero se denomina flujo de cero en ninguna parte o flujo de cero en ninguna parte respectivamente. [9]
Como espacio vectorial, la dimensión del espacio de ciclo de un gráfico con vértices, aristas y componentes conectados es . [1] [2] [10] Este número se puede interpretar topológicamente como el primer número de Betti del gráfico. [6] En teoría de grafos, se conoce como rango de circuito , número ciclomático o nulidad del grafo.
La combinación de esta fórmula para el rango con el hecho de que el espacio del ciclo es un espacio vectorial sobre el campo de dos elementos muestra que el número total de elementos en el espacio del ciclo es exactamente .
Una base de un espacio vectorial es un subconjunto mínimo de los elementos con la propiedad de que todos los demás elementos pueden escribirse como una combinación lineal de elementos de la base. Toda base de un espacio de dimensión finita tiene el mismo número de elementos, que es igual a la dimensión del espacio. En el caso del espacio cíclico, una base es una familia de subgrafos exactamente eulerianos, con la propiedad de que cada subgrafo euleriano puede escribirse como la diferencia simétrica de una familia de elementos de la base.
Por el teorema de Veblen , [11] cada subgrafo euleriano de un grafo dado puede descomponerse en ciclos simples , subgrafos en los que todos los vértices tienen grado cero o dos y en los que los vértices de grado dos forman un conjunto conexo. Por lo tanto, siempre es posible encontrar una base en la que los elementos de la base sean en sí mismos todos ciclos simples. Tal base se llama base de ciclo del grafo dado. Más fuertemente, siempre es posible encontrar una base en la que los elementos de la base sean ciclos inducidos o incluso (en un grafo conexo de 3 vértices ) ciclos inducidos no separables . [12]
Una forma de construir una base de ciclo es formar un bosque máximo del grafo y luego, para cada arista que no pertenece al bosque, formar un ciclo que consiste en junto con el camino en el bosque que conecta los puntos finales de . Los ciclos formados de esta manera son linealmente independientes (cada uno contiene una arista que no pertenece a ninguno de los otros ciclos) y tienen el tamaño correcto para ser una base, por lo que necesariamente es una base. Una base formada de esta manera se llama base de ciclo fundamental (con respecto al bosque elegido). [1]
Si existe un ordenamiento lineal de los ciclos en una base de ciclos tal que cada ciclo incluye al menos una arista que no es parte de ningún ciclo anterior, entonces la base de ciclos se llama débilmente fundamental . Toda base de ciclos fundamental es débilmente fundamental (para todos los ordenamientos lineales) pero no necesariamente al revés. Existen grafos, y bases de ciclos para esos grafos, que no son débilmente fundamentales. [13]
Si a los bordes de un grafo se les asignan pesos de números reales, el peso de un subgrafo puede calcularse como la suma de los pesos de sus bordes. La base de peso mínimo del espacio de ciclos es necesariamente una base de ciclos y puede construirse en tiempo polinomial. [8] La base de peso mínimo no siempre es débilmente fundamental y, cuando no lo es, es NP-difícil encontrar la base débilmente fundamental con el peso mínimo posible. [13]
Si un grafo planar se incrusta en el plano, su complejo de cadenas de aristas y vértices puede incrustarse en un complejo de cadenas de dimensiones superiores que también incluye los conjuntos de caras del grafo. El mapa de límites de este complejo de cadenas lleva cualquier 2-cadena (un conjunto de caras) al conjunto de aristas que pertenecen a un número impar de caras en la 2-cadena. El límite de una 2-cadena es necesariamente un subgrafo euleriano, y cada subgrafo euleriano puede generarse de esta manera a partir de exactamente dos 2-cadenas diferentes (cada una de las cuales es el complemento de la otra). [14] De esto se deduce que el conjunto de caras acotadas de la incrustación forma una base de ciclo para el grafo planar: eliminar la cara no acotada de este conjunto de ciclos reduce el número de formas en que cada subgrafo euleriano puede generarse de dos a exactamente uno.
El criterio de planaridad de Mac Lane , llamado así por Saunders Mac Lane , caracteriza a los grafos planares en términos de sus espacios de ciclos y bases de ciclos. Afirma que un grafo finito no dirigido es planar si y solo si el grafo tiene una base de ciclos en la que cada arista del grafo participa en, como máximo, dos ciclos de base. En un grafo planar, una base de ciclos formada por el conjunto de caras acotadas de una incrustación necesariamente tiene esta propiedad: cada arista participa solo en los ciclos de base para las dos caras que separa. Por el contrario, si una base de ciclos tiene, como máximo, dos ciclos por arista, entonces sus ciclos pueden usarse como el conjunto de caras acotadas de una incrustación plana de su grafo. [14] [15]
El espacio de ciclos de un grafo planar es el espacio de corte de su grafo dual , y viceversa. 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 sean caras, y algunas caras pueden no estar incluidas como ciclos en la base de ciclos de peso mínimo. Existe una base de ciclos de peso mínimo en la que no hay dos ciclos que se crucen entre sí: por cada dos 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. Siguiendo la dualidad entre espacios de ciclos y espacios de corte, esta base para un grafo planar corresponde a un árbol de Gomory-Hu del grafo dual, una base de peso mínimo para su espacio de corte. [16]
En los grafos planares, las coloraciones con colores distintos son duales a los flujos cero-en-ninguna parte sobre el anillo de números enteros módulo . En esta dualidad, la diferencia entre los colores de dos regiones adyacentes está representada por un valor de flujo a través del borde que separa las regiones. En particular, la existencia de 4-flujos cero-en-ninguna parte es equivalente al teorema de los cuatro colores . El teorema de snark generaliza este resultado a los grafos no planares. [17]
