Homología de grafos

En topología algebraica y teoría de grafos , la homología de grafos describe los grupos de homología de un grafo , donde el grafo se considera como un espacio topológico . Formaliza la idea del número de "agujeros" en el grafo. Es un caso especial de una homología simplicial , como un grafo es un caso especial de un complejo simplicial. Dado que un grafo finito es un 1-complejo (es decir, sus "caras" son los vértices, que son 0-dimensionales, y las aristas, que son unidimensionales), los únicos grupos de homología no triviales son el grupo 0-ésimo y el grupo 1-ésimo. ^[1]

El primer grupo de homología

La fórmula general para el primer grupo de homología de un espacio topológico X es: El siguiente ejemplo explica estos símbolos y conceptos con todo detalle en un gráfico. $${\displaystyle H_{1}(X):=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}}$$

Ejemplo

Sea X un grafo dirigido con 3 vértices {x,y,z} y 4 aristas {a: x→y, b: y→z, c: z→x, d: z→x}. Tiene varios ciclos :

• Un ciclo se representa mediante el bucle a+b+c. En este caso, el signo más representa el hecho de que todas las aristas recorren la misma dirección. Como la operación de suma es conmutativa, el signo + representa el hecho de que los bucles a+b+c, b+c+a y c+a+b representan el mismo ciclo.
• Un segundo ciclo está representado por el bucle a+b+d.
• Un tercer ciclo está representado por el bucle c−d. En este caso, el signo menos representa el hecho de que la arista d se recorre hacia atrás.

Si cortamos el plano por el bucle a+b+d, y luego cortamos en c y "pegamos" en d, obtenemos un corte por el bucle a+b+c. Esto se puede representar mediante la siguiente relación: (a+b+d) + (cd) = (a+b+c). Para definir formalmente esta relación, definimos los siguientes grupos conmutativos: ^{[2] : 6:00}

• C ₀ es el grupo abeliano libre generado por el conjunto de vértices {x,y,z}. Cada elemento de C ₀ se denomina cadena de dimensión 0 .
• C ₁ es el grupo abeliano libre generado por el conjunto de aristas dirigidas {a,b,c,d}. Cada elemento de C ₁ se denomina cadena unidimensional . Los tres ciclos mencionados anteriormente son cadenas unidimensionales y, de hecho, la relación (a+b+d) + (cd) = (a+b+c) se cumple en el grupo C ₁ .

La mayoría de los elementos de C ₁ no son ciclos, por ejemplo a+b, 2a+5b-c, etc. no son ciclos. Para definir formalmente un ciclo, primero definimos los límites . El límite de una arista se denota por el operador y se define como su objetivo menos su fuente, por lo que So es una aplicación del grupo C ₁ al grupo C ₀ . Dado que a,b,c,d son los generadores de C ₁ , esto se extiende naturalmente a un homomorfismo de grupo de C ₁ a C ₀ . En este homomorfismo, . De manera similar, asigna cualquier ciclo en C ₁ al elemento cero de C ₀ . En otras palabras, el conjunto de ciclos en C ₁ genera el espacio nulo (el núcleo) de . En este caso, el núcleo de tiene dos generadores: uno corresponde a a+b+c y el otro a a+b+d (el tercer ciclo, cd, es una combinación lineal de los dos primeros). Por lo que es isomorfo a Z ² . ${\displaystyle \partial _{1}}$ ${\displaystyle \partial _{1}(a)=y-x,~\partial _{1}(b)=z-y,~\partial _{1}(c)=\partial _{1}(d)=x-z.}$ ${\displaystyle \partial _{1}}$ ${\displaystyle \partial _{1}}$ ${\displaystyle \partial _{1}(a+b+c)=\partial _{1}(a)+\partial _{1}(b)+\partial _{1}(c)=(y-x)+(z-y)+(x-z)=0}$ ${\displaystyle \partial _{1}}$ ${\displaystyle \partial _{1}}$ ${\displaystyle \partial _{1}}$ ${\displaystyle \ker \partial _{1}}$

En un espacio topológico general, definiríamos cadenas de dimensiones superiores. En particular, C ₂ sería el grupo abeliano libre en el conjunto de objetos bidimensionales. Sin embargo, en un grafo no existen tales objetos, por lo que C ₂ es un grupo trivial. Por lo tanto, la imagen del segundo operador de frontera, , también es trivial. Por lo tanto: Esto corresponde al hecho intuitivo de que el grafo tiene dos "agujeros". El exponente es el número de agujeros. ${\displaystyle \partial _{2}}$ $${\displaystyle H_{1}(X)=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}\cong \mathbb {Z} ^{2}/\mathbb {Z} ^{0}=\mathbb {Z} ^{2}}$$

Caso general

El ejemplo anterior se puede generalizar a un grafo conexo arbitrario G = ( V , E ). Sea T un árbol de expansión de G . Cada arista en E \ T corresponde a un ciclo; estos son exactamente los ciclos linealmente independientes. Por lo tanto, el primer grupo de homología H ₁ de un grafo es el grupo abeliano libre con | E \ T | generadores. Este número es igual a | E |-| V |+1; por lo que: ^[1] En un grafo desconectado, cuando C es el conjunto de componentes conexos, un cálculo similar muestra: En particular, el primer grupo es trivial si y solo si X es un bosque . $${\displaystyle H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+1}.}$$ $${\displaystyle H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+|C|}.}$$

El grupo de homología 0-ésimo

La fórmula general para el grupo de homología 0-ésimo de un espacio topológico X es: $${\displaystyle H_{0}(X):=\ker \partial _{0}{\big /}\operatorname {im} \partial _{1}}$$

Ejemplo

Volvemos al grafo con 3 vértices {x,y,z} y 4 aristas {a: x→y, b: y→z, c: z→x, d: z→x}. Recordemos que el grupo C ₀ es generado por el conjunto de vértices. Como no hay elementos de dimensión (−1), el grupo C ₋₁ es trivial, y por lo tanto todo el grupo C ₀ es un núcleo del operador de frontera correspondiente: = el grupo abeliano libre generado por {x,y,z}. ^[3] ${\displaystyle \ker \partial _{0}=C_{0}}$

La imagen de contiene un elemento por cada par de vértices que son límites de una arista, es decir, es generada por las diferencias {y−x, z−y, x−z}. Para calcular el grupo cociente, es conveniente pensar en todos los elementos de como "equivalentes a cero". Esto significa que x, y y z son equivalentes - están en la misma clase de equivalencia del cociente. En otras palabras, es generada por un solo elemento (cualquier vértice puede generarla). Por lo que es isomorfa a Z . ${\displaystyle \partial _{1}}$ ${\displaystyle \operatorname {im} \partial _{1}}$ ${\displaystyle H_{0}(X)}$

Caso general

El ejemplo anterior se puede generalizar a cualquier grafo conexo . Partiendo de cualquier vértice, es posible llegar a cualquier otro vértice añadiéndole una o más expresiones correspondientes a aristas (p. ej., partiendo de x, se puede llegar a z añadiendo yx y zy). Puesto que los elementos de son todos equivalentes a cero, significa que todos los vértices del grafo están en una única clase de equivalencia y, por tanto, es isomorfo a Z. ${\displaystyle \operatorname {im} \partial _{1}}$ ${\displaystyle H_{0}(X)}$

En general, el grafo puede tener varios componentes conexos . Sea C el conjunto de componentes. Entonces, cada componente conexo es una clase de equivalencia en el grupo de cocientes. Por lo tanto: Puede generarse por cualquier | C |-tupla de vértices, uno de cada componente. $${\displaystyle H_{0}(X)\cong \mathbb {Z} ^{|C|}.}$$

Homología reducida

A menudo, es conveniente suponer que la homología 0-ésima de un grafo conexo es trivial (de modo que, si el grafo contiene un único punto, entonces todas sus homologías son triviales). Esto conduce a la definición de homología reducida . Para un grafo, la homología 0-ésima reducida es: Esta "reducción" afecta solo a la homología 0-ésima; las homologías reducidas de dimensiones superiores son iguales a las homologías estándar. $${\displaystyle {\tilde {H_{0}}}(X)\cong \mathbb {Z} ^{|C|-1}.}$$

Homologías de dimensiones superiores

Un grafo tiene solo vértices (elementos de dimensión 0) y aristas (elementos de dimensión 1). Podemos generalizar el grafo a un complejo simplicial abstracto agregando elementos de una dimensión superior. Entonces, el concepto de homología de grafos se generaliza mediante el concepto de homología simplicial .

Ejemplo

En el gráfico de ejemplo anterior, podemos añadir una "celda" bidimensional encerrada entre los bordes c y d; llamémosla A y supongamos que está orientada en el sentido de las agujas del reloj. Definamos C ₂ como el grupo abeliano libre generado por el conjunto de celdas bidimensionales, que en este caso es un singleton {A}. Cada elemento de C ₂ se denomina cadena bidimensional .

Al igual que el operador de contorno de C ₁ a C ₀ , que denotamos por , existe un operador de contorno de C ₂ a C ₁ , que denotamos por . En particular, el contorno de la celda bidimensional A son las aristas unidimensionales c y d, donde c está en la orientación "correcta" y d está en una orientación "inversa"; por lo tanto: . La secuencia de cadenas y operadores de contorno se puede presentar de la siguiente manera: ^[4] La adición de la celda bidimensional A implica que su contorno, cd, ya no representa un agujero (es homotópico a un único punto). Por lo tanto, el grupo de "agujeros" ahora tiene un único generador, a saber, a+b+c (es homotópico a a+b+d). El primer grupo de homología se define ahora como el grupo cociente : Aquí, es el grupo de ciclos unidimensionales, que es isomorfo a Z ² , y es el grupo de ciclos unidimensionales que son límites de celdas bidimensionales, que es isomorfo a Z . Por lo tanto, su cociente H ₁ es isomorfo a Z . Esto corresponde al hecho de que X ahora tiene un solo agujero. Anteriormente. la imagen de era el grupo trivial , por lo que el cociente era igual a . Supongamos ahora que agregamos otra celda bidimensional orientada B entre los bordes c y d, tal que . Ahora C ₂ es el grupo abeliano libre generado por {A,B}. Esto no cambia H ₁ - sigue siendo isomorfo a Z (X todavía tiene un solo agujero unidimensional). Pero ahora C ₂ contiene el ciclo bidimensional AB, por lo que tiene un núcleo no trivial. Este ciclo genera el segundo grupo de homología, correspondiente al hecho de que hay un solo agujero bidimensional: Podemos proceder y agregar una celda de 3 - un objeto sólido tridimensional (llamado C) delimitado por A y B. Definamos C ₃ como el grupo abeliano libre generado por {C}, y el operador de borde . Podemos orientar C de modo que ; note que el borde de C es un ciclo en C ₂ . Ahora el segundo grupo de homología es: correspondiente al hecho de que no hay agujeros bidimensionales (C "llena el agujero" entre A y B). ${\displaystyle \partial _{1}}$ ${\displaystyle \partial _{2}}$ ${\displaystyle \partial _{2}(A)=c-d}$ $${\displaystyle C_{2}\xrightarrow {\partial _{2}} C_{1}\xrightarrow {\partial _{1}} C_{0}}$$ $${\displaystyle H_{1}(X):=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}}$$ ${\displaystyle \ker \partial _{1}}$ ${\displaystyle \operatorname {im} \partial _{2}}$ ${\displaystyle \partial _{2}}$ ${\displaystyle \ker \partial _{1}}$ ${\displaystyle \partial _{2}(B)=\partial _{2}(A)=c-d}$ ${\displaystyle \partial _{2}}$ $${\displaystyle H_{2}(X):=\ker \partial _{2}\cong \mathbb {Z} }$$ ${\displaystyle \partial _{3}:C_{3}\to C_{2}}$ ${\displaystyle \partial _{3}(C)=A-B}$ $${\displaystyle H_{2}(X):=\ker \partial _{2}{\big /}\operatorname {im} \partial _{3}\cong {0}}$$

Caso general

En general, se pueden definir cadenas de cualquier dimensión. Si la dimensión máxima de una cadena es k , entonces obtenemos la siguiente secuencia de grupos: Se puede demostrar que cualquier límite de una celda de ( k +1) dimensión es un ciclo de k -dimensional. En otras palabras, para cualquier k , (el grupo de límites de k +1 elementos) está contenido en (el grupo de ciclos de k -dimensionales). Por lo tanto, el cociente está bien definido, y se define como el k -ésimo grupo de homología: $${\displaystyle C_{k}\xrightarrow {\partial _{k}} C_{k-1}\cdots C_{1}\xrightarrow {\partial _{1}} C_{0}}$$ ${\displaystyle \operatorname {im} \partial _{k+1}}$ ${\displaystyle \ker \partial _{k}}$ ${\displaystyle \ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}}$ $${\displaystyle H_{k}(X):=\ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}}$$

Referencias

1. Sunada, Toshikazu (2013), Sunada, Toshikazu (ed.), "Grupos de homología de grafos", Cristalografía topológica: con vistas al análisis geométrico discreto , Encuestas y tutoriales en las ciencias matemáticas aplicadas, Tokio: Springer Japón, págs. 37–51, doi :10.1007/978-4-431-54177-6_4, ISBN 978-4-431-54177-6
2. Wildberger, Norman J. (2012). "Introducción a la homología". YouTube .
3. Wildberger, Norman J. (2012). "Cálculo de grupos de homología". YouTube .
4. Wildberger, Norman J. (2012). "Introducción a la homología (cont.)". YouTube .