Espacio para bicicletas

Un subgrafo generador de un grafo G dado puede definirse a partir de cualquier subconjunto S de las aristas de G. El subgrafo tiene el mismo conjunto de vértices que G (este es el significado de la palabra "generador"), pero sus aristas son los elementos de S. Por lo tanto, un grafo G con m aristas tiene 2 ^m subgrafos generadores, incluyendo a G mismo, así como el grafo vacío sobre 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 ]}

Se dice que un grafo G , o uno de sus subgrafos, 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 obra 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 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 generadores eulerianos. ^{[ 1 ] [ 2 ]} Dado que el conjunto de vértices de cualquier subgrafo de este tipo es siempre el mismo, es igualmente válido definir el espacio de ciclos como la colección de conjuntos de aristas de subgrafos eulerianos.

Si se aplica cualquier operación de conjuntos, como la unión o la intersección de conjuntos, a dos subgrafos generadores de un grafo dado, el resultado será nuevamente un subgrafo generador. De esta manera, el espacio de aristas de un grafo arbitrario, que es simplemente el conjunto de todos los subconjuntos del conjunto de aristas del grafo, puede interpretarse como un álgebra booleana . ^{[ 3 ]}

El espacio cíclico también posee 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 formado por las aristas que pertenecen a uno solo de los dos grafos dados y los vértices de ambos) sí es 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 entornos de cada vértice, se observa 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 puede describirse algebraicamente como un espacio vectorial sobre el cuerpo finito de dos elementos.${\displaystyle \mathbb {Z} _ {2}}$. ^{[ 4 ]} Este campo tiene dos elementos, 0 y 1, y sus operaciones de suma y multiplicación pueden describirse como la suma y multiplicación familiares de enteros , tomadas módulo  2 . Un espacio vectorial consiste en un conjunto de elementos junto con una operación de suma y multiplicación escalar que satisface ciertas propiedades que generalizan las propiedades de los espacios vectoriales reales familiares . Para el espacio de ciclos, los elementos del espacio vectorial son los subgrafos generadores eulerianos (o sus conjuntos de aristas), la operación de suma es la diferenciación simétrica, la multiplicación por el escalar  1 es la operación identidad multiplicativa , y la multiplicación por el escalar  0 lleva cada elemento al grafo sin aristas (o al conjunto de aristas vacío), que forma el elemento identidad aditivo para el espacio de ciclos.

El espacio de aristas es también un espacio vectorial sobre${\displaystyle \mathbb {Z} _ {2}}$con la diferencia simétrica como suma. Como espacios vectoriales, el espacio de ciclos y el espacio de cortes del grafo (la familia de conjuntos de aristas que abarcan los cortes del grafo) son complementos ortogonales entre sí dentro del espacio de aristas. Esto significa que un conjunto${\displaystyle S}$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${\displaystyle S}$, y${\displaystyle S}$forma un subgrafo euleriano si y solo si cada corte tiene un número par de aristas en común con${\displaystyle S}$. ^{[ 2 ]} Aunque estos dos espacios son complementos ortogonales, algunos grafos tienen subgrafos no vacíos que pertenecen a ambos. Dicho subgrafo (un corte euleriano) existe como parte de un grafo${\displaystyle G}$si y solo si${\displaystyle G}$tiene un número par de bosques que se extienden . ^{[ 5 ]}

Un grafo no dirigido puede considerarse como un complejo simplicial con sus vértices como símplices de dimensión cero y las aristas como símplices de dimensión uno. ^{[ 6 ]} El complejo de cadenas de este espacio topológico consta de su espacio de aristas y su espacio de vértices (el álgebra booleana de conjuntos de vértices), conectados por un operador de frontera que asigna a cualquier subgrafo generador (un elemento del espacio de aristas) su conjunto de vértices de grado impar (un elemento del espacio de vértices). El grupo de homología

${\ Displaystyle H_ {1} (G, \ mathbb {Z} _ {2})}$

Consiste en los elementos del espacio de aristas que se corresponden con el elemento cero del espacio de vértices; estos son precisamente los subgrafos eulerianos. Su operación de grupo es la diferencia simétrica aplicada a los subgrafos eulerianos.

Reemplazar${\displaystyle \mathbb {Z} _ {2}}$En esta construcción mediante un anillo arbitrario , la definición de espacios de ciclos se extiende a espacios de ciclos con coeficientes en el anillo dado, que forman módulos sobre el anillo. ^{[ 7 ]} En particular, el espacio de ciclos integral es el espacio

${\displaystyle H_{1}(G,\mathbb {Z} ).}$

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.${\displaystyle G}$ser una asignación de enteros a las aristas de${\displaystyle G}$(un elemento del grupo abeliano libre sobre las aristas) con la propiedad de que, en cada vértice, la suma de los números asignados a las aristas entrantes es igual a la suma de los números asignados a las aristas salientes. ^{[ 8 ]}

Un miembro de${\displaystyle H_{1}(G,\mathbb {Z} )}$o de${\ Displaystyle H_ {1} (G, \ mathbb {Z} _ {k})}$(el espacio de ciclo módulo${\displaystyle k}$) con la propiedad adicional de que todos los números asignados a las aristas son distintos de cero se denomina flujo cero en ninguna parte o flujo cero en ninguna parte.${\displaystyle k}$-flujo respectivamente. ^{[ 9 ]}

Según el teorema de Veblen , ^{[ 11 ]} todo 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 todos ciclos simples. Dicha base se denomina base cíclica del grafo dado. Más concretamente, 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${\displaystyle e}$que no pertenece al bosque, forman un ciclo${\displaystyle C_{e}}$compuesto de${\displaystyle e}$junto con el sendero en el bosque que conecta los extremos de ${\displaystyle e}$Los ciclos${\displaystyle C_{e}}$formadas de esta manera son linealmente independientes (cada una contiene una arista${\displaystyle e}$que no pertenece a ninguno de los otros ciclos) y tiene el tamaño correcto${\displaystyle m-n+c}$ser una base, por lo tanto, 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 forma parte de ningún ciclo anterior, entonces la base de ciclos se denomina débilmente fundamental . Toda base de ciclos fundamental es débilmente fundamental (para todos los ordenamientos lineales), pero no necesariamente a la inversa. Existen grafos, y bases de ciclos para esos grafos, que no son débilmente fundamentales. ^{[ 13 ]}

Si a las aristas de un grafo se les asignan pesos reales, el peso de un subgrafo puede calcularse como la suma de los pesos de sus aristas. 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 dimensión superior que también incluye los conjuntos de caras del grafo. El mapa de frontera de este complejo de cadenas transforma cualquier 2-cadena (un conjunto de caras) en el conjunto de aristas que pertenecen a un número impar de caras en la 2-cadena. La frontera 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 ciclos para el grafo planar: al eliminar la cara no acotada de este conjunto de ciclos, se reduce el número de formas en que cada subgrafo euleriano puede generarse de dos a exactamente una.

El criterio de planaridad de Mac Lane , que recibe su nombre de Saunders Mac Lane , caracteriza los grafos planares en términos de sus espacios de ciclos y bases de ciclos. Establece que un grafo finito no dirigido es planar si y solo si posee una base de ciclos en la que cada arista participa en como máximo dos ciclos de la base. En un grafo planar, una base de ciclos formada por el conjunto de caras acotadas de una incrustación necesariamente posee esta propiedad: cada arista participa únicamente en los ciclos de la 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 utilizarse como el conjunto de caras acotadas de una incrustación planar de su grafo. ^{[ 14 ] [ 15 ]}

El espacio de ciclos de un grafo planar es el espacio de cortes 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 son 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: 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. Siguiendo la dualidad entre espacios de ciclos y espacios de cortes, 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 cortes. ^{[ 16 ]}

En gráficos planares, coloraciones con${\displaystyle k}$Los colores distintos son duales a ningún lugar: los flujos cero recorren el anillo.${\displaystyle \mathbb {Z} _{k}}$de enteros módulo${\displaystyle k}$En esta dualidad, la diferencia entre los colores de dos regiones adyacentes se representa mediante un valor de flujo a través de la arista que separa las regiones. En particular, la existencia de flujos de cuatro colores sin cero en ninguna parte es equivalente al teorema de los cuatro colores . El teorema de Snark generaliza este resultado a grafos no planares. ^{[ 17 ]}