En la 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 subgráficos se puede describir algebraicamente como un espacio vectorial sobre el campo finito de dos elementos . La dimensión de este espacio es el rango de circuito del gráfico. El mismo espacio también se puede describir en términos de topología algebraica como el primer grupo de homología del gráfico. Usando la teoría de la homología, el espacio de ciclo binario se puede generalizar a espacios de ciclo sobre anillos arbitrarios .
Definiciones
Teoría de grafos
Un subgrafo que abarca de un dado gráfico G se puede definir de cualquier subconjunto S de los bordes de G . El subgrafo tiene el mismo conjunto de vértices que G en sí mismo (este es el significado de la palabra "abarcando") pero tiene los elementos de S como sus aristas. Por lo tanto, un gráfico G con m bordes tiene 2 m que abarca subgraphs, incluyendo G en sí, así como el gráfico de vacío en el mismo conjunto de vértices como G . La colección de todos los subgraphs que abarcan de un gráfico G forma el espacio de borde de G . [1] [2]
Se dice que un gráfico G , o uno de sus subgráficos, es euleriano si cada uno de sus vértices tiene un número par de aristas incidentes (este número se denomina grado del vértice). Esta propiedad lleva el nombre de Leonhard Euler, quien demostró en 1736, en su trabajo sobre los siete puentes de Königsberg , que un gráfico conectado tiene un recorrido que visita cada borde exactamente una vez si y solo si es euleriano. Sin embargo, no es necesario conectar un subgrafo euleriano; por ejemplo, el gráfico vacío, en el que todos los vértices están desconectados entre sí, es euleriano. El espacio cíclico de un gráfico es la colección de sus subgráficos que abarcan eulerianos. [1] [2]
Álgebra
Si se aplica cualquier operación de conjunto , como la unión o la intersección de conjuntos, a dos subgráficos que abarcan un gráfico determinado, el resultado volverá a ser un subgráfico. De esta manera, el espacio de borde de un gráfico arbitrario se puede interpretar como un álgebra de Boole . [3]
El espacio cíclico 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 subgráficos eulerianos (el gráfico que consta de los bordes que pertenecen exactamente a uno de los dos gráficos dados) es nuevamente euleriano. [1] Esto se deriva del hecho de que la diferencia simétrica de dos conjuntos con un número par de elementos también es par. La aplicación de este hecho por separado a las vecindades de cada vértice 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 campo finito de dos elementos. . [4] Este campo tiene dos elementos, 0 y 1, y sus operaciones de suma y multiplicación pueden describirse como la conocida suma y multiplicación de números enteros , tomada en 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 cíclico, los elementos del espacio vectorial son los subgráficos eulerianos, la operación de adición es la diferenciación simétrica, la multiplicación por el escalar 1 es la operación de identidad , y la multiplicación por el escalar 0 lleva cada elemento al gráfico vacío, que forma el elemento de identidad aditivo para el espacio cíclico.
El espacio de borde es también un espacio vectorial sobre si usamos la diferencia simétrica como suma. Como espacios vectoriales, el espacio de ciclo y el espacio de corte del gráfico (la familia de conjuntos de bordes que abarcan los cortes del gráfico) son los complementos ortogonales entre sí dentro del espacio de borde. Esto significa que un conjunto de aristas en un grafo forma un corte si y solo si cada subgrafo euleriano tiene un numero par de aristas en comun con , y forma un subgrafo euleriano si y solo si cada corte tiene un nmero par de bordes en comn con . [2] Aunque estos dos espacios son complementos ortogonales, algunos gráficos tienen subgrafos no vacíos que pertenecen a ambos. Tal subgrafo (un corte euleriano) existe como parte de un grafo si y solo si tiene un número par de bosques extensos . [5]
Topología
Un grafo no dirigido puede verse como un complejo simple con sus vértices como simples de dimensión cero y los bordes como simples unidimensionales. [6] El complejo de cadena de este espacio topológico consiste en su espacio de borde y espacio de vértice (el álgebra booleana de conjuntos de vértices), conectados por un operador de límite que mapea cualquier subgrafo de expansión (un elemento del espacio de borde) a su conjunto de vértices de grado impar (un elemento del espacio de vértices). El grupo de homología
consta de los elementos del espacio de borde que se asignan al elemento cero del espacio de vértice; estos son exactamente los subgrafos eulerianos. Su operación de grupo es la operación de diferencia simétrica en subgrafos eulerianos.
Reemplazo en esta construcción por un anillo arbitrario permite extender la definición de espacios de ciclo a espacios de ciclo con coeficientes en el anillo dado, que forman módulos sobre el anillo. [7] En particular, el espacio del ciclo integral es el espacio
Se puede definir en términos teóricos de gráficos eligiendo una orientación arbitraria del gráfico y definiendo un ciclo integral de un gráfico. ser 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 módulo del espacio cíclico ) con la propiedad adicional de que todos los números asignados a los bordes son distintos de cero, se denomina flujo cero en ninguna parte o cero en ninguna parte.-flujo. [9]
Rango de circuito
Como espacio vectorial, la dimensión del espacio cíclico de un gráfico con vértices bordes, y componentes conectados es. [1] [2] [10] Este número puede interpretarse topológicamente como el primer número 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 cíclico es un espacio vectorial sobre el campo de dos elementos muestra que el número total de elementos en el espacio cíclico es exactamente .
Bases de ciclo
Una base de un espacio vectorial es un subconjunto mínimo de elementos con la propiedad de que todos los demás elementos pueden escribirse como una combinación lineal de elementos base. Cada base de un espacio de dimensión finita tiene el mismo número de elementos, lo que equivale a la dimensión del espacio. En el caso del espacio cíclico, una base es una familia de exactamente Subgrafos eulerianos, con la propiedad de que cada subgrafo euleriano puede escribirse como la diferencia simétrica de una familia de elementos básicos.
Existencia
Según el teorema de Veblen , [11] cada subgrafo euleriano de un gráfico dado se puede descomponer en ciclos simples , subgrafos en los que todos los vértices tienen grados cero o dos y en los que los vértices de dos grados forman un conjunto conectado. Por lo tanto, siempre es posible encontrar una base en la que los elementos básicos sean ellos mismos todos ciclos simples. Esta base se denomina base de ciclo del gráfico dado. Más fuertemente, siempre es posible encontrar una base en la que los elementos base sean ciclos inducidos o incluso (en un gráfico conectado a 3 vértices ) ciclos inducidos cuya eliminación no separe el gráfico restante. [12]
Bases fundamentales y débilmente fundamentales
Una forma de construir una base de ciclo es formar un bosque de expansión del gráfico, y luego para cada borde que no pertenece al bosque, forma un ciclo que consiste en junto con el camino en el bosque que conecta los puntos finales de . El conjunto de ciclos formados de esta manera son linealmente independientes (cada uno contiene un borde que no pertenece a ninguno de los otros ciclos) y tiene el tamaño correcto para ser una base, por lo que necesariamente es una base. Una base formada de esta manera se denomina base de ciclo fundamental . [1]
Si existe un orden lineal de los ciclos en una base de ciclo tal que cada ciclo incluye al menos un borde que no es parte de ningún ciclo anterior, entonces la base de ciclo se denomina débilmente fundamental . Cada base de ciclo fundamental es débilmente fundamental (para todos los ordenamientos lineales) pero no necesariamente al revés. Existen gráficos y bases de ciclo para esos gráficos que no son débilmente fundamentales. [13]
Bases de peso mínimo
Si a los bordes de un gráfico se les asignan pesos numéricos reales, el peso de un subgráfico se puede calcular como la suma de los pesos de sus bordes. La base de peso mínimo del espacio de ciclo es necesariamente una base de ciclo y se puede construir 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 mínimo peso posible. [13]
Gráficos planos
Homologia
Si un gráfico plano está incrustado en el plano, su complejo de cadenas de aristas y vértices puede incrustarse en un complejo de cadena de dimensiones superiores que también incluye los conjuntos de caras del gráfico. El mapa de límites de este complejo de cadenas toma cualquier cadena de 2 (un conjunto de caras) al conjunto de aristas que pertenecen a un número impar de caras en la cadena de 2. El límite de una cadena 2 es necesariamente un subgrafo euleriano, y cada subgrafo euleriano se puede generar de esta manera a partir de exactamente dos cadenas 2 diferentes (cada una de las cuales es el complemento de la otra). [14] De esto se deduce que el conjunto de caras limitadas de la incrustación forma una base de ciclo para el gráfico plano: eliminar la cara ilimitada de este conjunto de ciclos reduce el número de formas en que cada subgrafo euleriano se puede generar de dos a exactamente uno. .
Criterio de planaridad de Mac Lane
El criterio de planaridad de Mac Lane , que lleva el nombre de Saunders Mac Lane , caracteriza las gráficas planas en términos de sus espacios de ciclo y bases de ciclo. Establece que un gráfico finito no dirigido es plano si y solo si el gráfico tiene una base cíclica en la que cada borde del gráfico participa como máximo en dos ciclos básicos. En un gráfico plano, una base de ciclo formada por el conjunto de caras acotadas de una incrustación necesariamente tiene esta propiedad: cada borde participa solo en los ciclos de base para las dos caras que separa. Por el contrario, si una base de ciclo tiene como máximo dos ciclos por borde, entonces sus ciclos se pueden usar como el conjunto de caras acotadas de una incrustación plana de su gráfico. [14] [15]
Dualidad
El espacio cíclico de un gráfico plano es el espacio de corte de su gráfico dual y viceversa. La base del ciclo de peso mínimo para un gráfico plano 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 incluirse como ciclos en la base del ciclo de peso mínimo. Existe una base de ciclo de peso mínimo en la que no hay dos ciclos que se crucen: por cada dos ciclos en la base, o los ciclos encierran subconjuntos disjuntos de las caras delimitadas, o uno de los dos ciclos encierra al otro. Siguiendo la dualidad entre espacios de ciclo y espacios de corte, esta base para un gráfico plano corresponde a un árbol de Gomory-Hu del gráfico dual, una base de peso mínimo para su espacio de corte. [dieciséis]
En ninguna parte cero fluye
En gráficos planos, los colorantes con los colores distintos son duales a ninguna parte cero fluye sobre el anillo de enteros modulo . 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 cuatro flujos cero en ninguna parte es equivalente al teorema de los cuatro colores . El teorema de snark generaliza este resultado a gráficos no planos. [17]
Referencias
- ^ a b c d e Gross, Jonathan L .; Yellen, Jay (2005), "4.6 Gráficos y espacios vectoriales", Teoría de gráficos y sus aplicaciones (2ª ed.), CRC Press, págs. 197–207, ISBN 9781584885054.
- ^ a b c d Diestel, Reinhard (2012), "1.9 Un poco de álgebra lineal", Teoría de grafos , Textos de posgrado en matemáticas, 173 , Springer, págs. 23-28.
- ^ Joshi, KD (1997), Estructuras discretas aplicadas , New Age International, p. 172, ISBN 9788122408263.
- ^ Wallis, WD (2010), Guía para principiantes de teoría de grafos , Springer, p. 66, ISBN 9780817645809.
- ^ Eppstein, David (1996), Sobre la paridad de los números de árboles de expansión de gráficos (PDF) , Informe técnico 96-14, Departamento de Información y Ciencias de la Computación, Universidad de California, Irvine.
- ^ a b Serre, Jean-Pierre (2003), Trees , Springer Monographs in Mathematics, Springer, p. 23, ISBN 9783540442370.
- ^ Biggs, Norman (1993), Teoría de grafos algebraicos , Cambridge Mathematical Library, Cambridge University Press, pág. 154, ISBN 9780521458979.
- ^ a b Berger, Franziska; Gritzmann, Peter; de Vries, Sven (2009), "Las bases del ciclo mínimo y sus aplicaciones", Algoritmos de redes grandes y complejas , Lecture Notes in Computer Science, 5515 , pp. 34–49, doi : 10.1007 / 978-3-642-02094- 0_2 , ISBN 978-3-642-02093-3.
- ^ Seymour, PD (1995), "Flujos cero en ninguna parte", Manual de combinatoria, vol. 1, 2 , Amsterdam: Elsevier, págs. 289-299, MR 1373660.
- ^ Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs , Publicaciones de Courier Dover, págs. 27-30, ISBN 9780486419756.
- ^ Veblen, Oswald (1912), "Una aplicación de ecuaciones modulares en el análisis situs", Annals of Mathematics , Second Series, 14 (1): 86–94, doi : 10.2307 / 1967604 , JSTOR 1967604.
- ^ Diestel (2012) , págs. 32, 65.
- ^ a b Rizzi, Romeo (2009), "Las bases del ciclo mínimo débilmente fundamental son difíciles de encontrar", Algorithmica , 53 (3): 402–424, doi : 10.1007 / s00453-007-9112-8 , MR 2482112.
- ↑ a b Diestel (2012) , págs. 105-106.
- ^ Mac Lane, S. (1937), "Una condición combinatoria para gráficas planas" (PDF) , Fundamenta Mathematicae , 28 : 22–32.
- ^ Hartvigsen, David; Mardon, Russell (1994), "El problema de corte mínimo de todos los pares y el problema de base de ciclo mínimo en gráficas planas", SIAM Journal on Discrete Mathematics , 7 (3): 403–418, doi : 10.1137 / S0895480190177042 , MR 1285579.
- ^ Thomas, Robin (1999), "Teoremas menores excluidos recientes para gráficos", Encuestas en combinatoria, 1999 (PDF) , Cambridge University Press, págs. 201–222