Espacio de bucle

El espacio de ciclos de un grafo no dirigido  es un espacio lineal sobre un campo formado por sus subgrafos de Euler . La dimensión de este espacio se llama rango de contorno del gráfico. Desde el punto de vista de la topología algebraica, un espacio cíclico es el primer grupo de homología de un grafo.

Definiciones

Teoría de grafos

Un subgrafo generador de un grafo dado es su subgrafo tal que el conjunto de vértices coincide con el conjunto de vértices . Por lo tanto, cualquier gráfico con aristas tiene subgráficos que se expanden, incluyéndose a sí mismo y al gráfico vacío en el conjunto de vértices del gráfico . La familia de todos los subgrafos que se expanden forma el espacio de borde del grafo dado. Un grafo se llama Euler si cada uno de sus vértices incide con un número par de aristas (en otras palabras, el grado de cualquier vértice del grafo es par). La familia de todos los subgrafos de expansión de Euler forma el espacio cíclico del gráfico dado [1] [2] .

Álgebra

El espacio de borde de cualquier gráfico es cerrado con respecto a las operaciones de teoría de conjuntos, por lo que forma un álgebra booleana [3] . Los espacios cíclicos también tienen una estructura algebraica: la unión o intersección de subgrafos de Euler puede no ser Euler, pero su diferencia simétrica será [1] . Esto se debe a que la diferencia simétrica de conjuntos con un conjunto par de elementos ( vecindades del vértice en el primer y segundo subgrafo) también contiene un conjunto par de elementos.

Una familia de conjuntos cerrados con respecto a una diferencia simétrica se puede describir algebraicamente mediante un espacio vectorial sobre un campo finito de dos elementos [4] . Este campo consta de dos elementos, y , y la suma y la multiplicación corresponden a las operaciones lógicas de "o" exclusiva y conjunción (suma y multiplicación módulo 2 ). En un espacio cíclico, los vectores serán subgrafos de Euler, su suma corresponde a una diferencia simétrica, la multiplicación por un escalar  es el mapa identidad , y la multiplicación por un escalar convierte cualquier subgrafo en uno vacío, que corresponde al vector cero del cíclico . espacio.

El espacio de borde también es un espacio vectorial con la operación de diferencia simétrica como suma. El espacio cíclico y el espacio de cortes [5] son ​​complementos ortogonales entre sí dentro del espacio de borde. Esto significa que un conjunto de aristas es un corte si y solo si cualquier subgrafo de Euler contiene un número par de aristas de y, a la inversa, un conjunto es un subgrafo de Euler si y solo si cualquier corte contiene un número par de aristas de [2] . Aunque estos espacios son complementos ortogonales entre sí, pueden tener una intersección no trivial. En general, un grafo tiene un corte de Euler no vacío si y solo si el número de bosques que lo abarcan es par [6] .

Topología

Un grafo no dirigido puede verse como un complejo simplicial cuyos vértices son simples de dimensión cero y cuyas aristas son simples de una dimensión [7] . El complejo de cadenas de un espacio topológico de este tipo consta de sus espacios de vértice y borde conectados por un operador de límite que asigna 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értice). El grupo de homología consta de elementos del espacio de borde, que se traducen por el operador de límite en el elemento cero del espacio de vértice, es decir, de subgrafos de Euler. En consecuencia, la operación de grupo aquí es la diferencia simétrica de los gráficos de Euler.

La definición de un espacio cíclico se puede ampliar reemplazándolo con un anillo arbitrario , siendo el grupo de homología resultante un módulo sobre el anillo dado [8] . En particular, el grupo de homología se denomina espacio cíclico integral . En términos de teoría de grafos, dicho espacio se puede definir dando una orientación en el gráfico y definiendo un ciclo entero como un conjunto de números enteros asignados a los bordes del gráfico de tal manera que en cualquier vértice la suma de los números asignados a los bordes que entran en ella es igual a la suma de los números asignados a los bordes, que emanan de ella. En consecuencia, un espacio cíclico entero consta de todos los ciclos enteros, y la suma de vectores en este espacio corresponderá a la suma de los números asignados a cada arista por separado [9] .

Los elementos de o (de un módulo de espacio cíclico ) con la condición adicional de que todos los números asignados sean distintos de cero se denominan flujos de ninguna parte cero [10] .

Rango cíclico

La dimensión del espacio de ciclo de un gráfico con vértices, aristas y componentes conectados es [1] [2] [11] . Este número se puede interpretar topológicamente como el primer número de Betti del gráfico [7] . En teoría de grafos, también se conoce como rango cíclico y número ciclomático. Dado que el espacio de ciclos es un espacio vectorial sobre un campo de dos elementos, se deduce que el número total de elementos en el espacio de ciclos es .

Base de ciclos

Una base de espacio de ciclo es una familia de subgrafos de Euler tales que cualquier subgrafo de Euler puede representarse como una diferencia simétrica de algún conjunto de ciclos base.

Existencia

De acuerdo con el teorema de Veblen [12] , cualquier subgrafo de Euler se puede descomponer en una suma de ciclos simples  : subgrafos, todos cuyos bordes forman un componente conectado, todos cuyos vértices tienen grado . Así, siempre existe una base cuyos elementos son ciclos simples. Tal base se llama la base del ciclo del gráfico dado. Además, siempre es posible construir una base tal que todos sus elementos sean ciclos generados (es decir, ciclos sin cuerdas en el gráfico original) [13] .

Bases fundamentales y débilmente fundamentales

Para construir una base de ciclos, puede construir un bosque expansivo del gráfico y luego, para cada borde que no pertenezca al bosque, formar un ciclo que consiste en junto con un camino en el bosque expansivo que conecta los extremos del borde. El conjunto de ciclos así formado es linealmente independiente (ya que cada ciclo contiene una arista que no pertenece a otros ciclos) y consta de ciclos, por lo que se garantiza que es una base. La base así construida se denomina base fundamental de los ciclos [1] .

Se dice que una base es débilmente fundamental si se puede establecer un orden lineal en el conjunto de ciclos tal que cada ciclo contiene al menos una arista que no está contenida en ninguno de los ciclos anteriores. Cualquier base fundamental de ciclos es débilmente fundamental (para cualquier orden), lo contrario no es cierto. Hay grafos cuyas bases de ciclo no son débilmente fundamentales [14] .

Base de peso mínimo

Asigne a cada borde del gráfico un número real, llamado su peso, y el peso de cualquier subgráfico se define como la suma de los pesos de los bordes incluidos en él. La base de menor peso en el espacio del ciclo debe ser una base de ciclo y se puede construir en tiempo polinomial [9] . Además, tal base no tiene que ser débilmente fundamental, y el problema de encontrar una base débilmente fundamental del menor peso es NP-difícil [14] .

Grafos planos

Criterio de planaridad de McLane

El criterio de planaridad de MacLane caracteriza los gráficos planos en términos de espacio de ciclo y base de ciclo. El criterio establece que un gráfico no dirigido finito es plano si y solo si tiene una base de ciclo en la que cada borde del gráfico está contenido en dos ciclos como máximo. Tal base para un gráfico plano son los límites de las caras en su disposición , ya que cada borde está contenido solo en los límites de las dos caras que separa. En consecuencia, si el gráfico tiene una base de ciclo con esta propiedad, entonces sus elementos pueden usarse como los límites de las caras en la disposición del gráfico [15] [16] .

Dualidad

El espacio de ciclos de un grafo plano es el espacio de cortes de su grafo dual , y viceversa. La base del peso mínimo en un gráfico plano no coincide necesariamente con la base de los límites de sus caras, descritos anteriormente. Sin embargo, un gráfico plano siempre tiene una base de peso mínimo en la que no se cruzan dos ciclos de base. De la dualidad de espacios de ciclos y cortes se sigue que tal base de ciclos de un grafo plano corresponde al árbol Gomory-Hu de su grafo dual, que define la base de menor peso en su espacio de cortes [17] .

En ninguna parte cero fluye

En los gráficos planos , las coloraciones con distintos colores son flujos duales a ningún lugar cero sobre el campo de módulo de residuos . La diferencia entre los números de color de las caras vecinas en una dualidad dada está representada por el valor del flujo que fluye a lo largo del borde que separa estas caras. En particular, la existencia de un flujo de 4 ceros en ninguna parte en cualquier gráfico plano es equivalente al teorema de los cuatro colores . El teorema de snark generaliza este resultado a grafos no planos [18] .

Notas

1. ↑ 1 2 3 4 Gross, Jonathan L. & Yellen, Jay (2005), 4.6 Graphs and Vector Spaces , Graph Theory and Its Applications (2nd ed.), CRC Press, p. 197–207, ISBN 9781584885054 , < https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197 > Archivado el 2 de mayo de 2019 en Wayback Machine . 
2. ↑ 1 2 3 Diestel, Reinhard (2012), 1.9 Algo de álgebra lineal , Teoría de grafos , vol. 173, Textos de Posgrado en Matemáticas, Springer, p. 23–28 , < https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23 > Archivado el 2 de mayo de 2019 en Wayback Machine . 
3. ↑ Joshi, KD (1997), Estructuras discretas aplicadas , New Age International, p. 172, ISBN 9788122408263 , < https://books.google.com/books?id=lxIgGGJXacoC&pg=PA172 >  .
4. ↑ Wallis, W.D. (2010), Guía para principiantes de la teoría de grafos , Springer, p. 66, ISBN 9780817645809 , < https://books.google.com/books?id=240QO32GJOcC&pg=PA66 >  .
5. ↑ Aquí, un corte de un gráfico significa un conjunto de aristas tales que el conjunto de vértices se puede dividir en dos subconjuntos que no se intersecan y , tal que .
6. ↑ Eppstein, David (1996), On the Parity of Graph Spanning Tree Numbers , Technical Report 96-14, Department of Information and Computer Science, University of California, Irvine , < http://www.ics.uci.edu/~ eppstein/pubs/Epp-TR-96-14.pdf > Archivado el 5 de octubre de 2020 en Wayback Machine . 
7. ↑ 1 2 Serre, Jean-Pierre (2003), Trees , Springer Monographs in Mathematics, Springer, p. 23, ISBN 9783540442370 , < https://books.google.com/books?id=MOAqeoYlBMQC&pg=PA23 > 
8. ↑ Biggs, Norman (1993), Teoría de gráficos algebraicos , Biblioteca matemática de Cambridge, Cambridge University Press, p. 154, ISBN 9780521458979 , < https://books.google.com/books?id=6TasRmIFOxQC&pg=PA154 > 
9. ↑ 1 2 Berger, Franziska; Gritzmann, Peter & de Vries, Sven (2009), Bases de ciclos mínimos y sus aplicaciones , Algorithmics of Large and Complex Networks , vol. 5515, Lecture Notes in Computer Science, p. 34–49, ISBN 978-3-642-02093-3 
10. ↑ Seymour, PD (1995), Nowhere-zeroflows, Manual de combinatoria, vol. 1, 2 , Ámsterdam: Elsevier, pág. 289–299 
11. ↑ Berge, Claude (2001), Número ciclomático , The Theory of Graphs , Courier Dover Publications, p. 27–30, ISBN 9780486419756 , < https://books.google.com/books?id=h5BjnaoKyOwC&pg=PA27 > 
12. ↑ Veblen, Oswald (1912), Una aplicación de ecuaciones modulares en el análisis situs , Annals of Mathematics , Segunda serie Vol. 14 (1): 86–94 , DOI 10.2307/1967604 
13. ↑ Diestel (2012 ), págs. 32, 65.
14. ↑ 1 2 Rizzi, Romeo (2009), Las bases mínimas del ciclo fundamental débil son difíciles de encontrar , Algorithmica Vol. 53 (3): 402–424 , DOI 10.1007/s00453-007-9112-8 
15. ↑ Diestel (2012 ), págs. 105-106.
16. ↑ Mac Lane, S. (1937), Una condición combinatoria para grafos planos , Fundamenta Mathematicae T. 28: 22–32 , < http://matwbn.icm.edu.pl/ksiazki/fm/fm28/fm2814.pdf > Archivado el 20 de enero de 2022 en Wayback Machine . 
17. ↑ 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áficos planares , SIAM Journal on Discrete Mathematics Vol. 7 (3): 403–418 , DOI 10.1137/S0895480190177042 
18. ↑ Thomas, Robin (1999), Teoremas menores excluidos recientes para gráficos , Estudios en combinatoria, 1999 , Cambridge University Press, p. 201–222 , < http://people.math.gatech.edu/~thomas/PAP/bcc.pdf > Archivado el 3 de agosto de 2016 en Wayback Machine .