Homología de grafos

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 está representado por el bucle a+b+c. Aquí, el signo más indica que todos los bordes se recorren en la misma dirección. Dado que la suma es conmutativa, el signo + indica 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. Aquí, el signo menos representa que la arista d se recorre hacia atrás.

Si cortamos el plano a lo largo del bucle a + b + d, y luego cortamos en c y "pegamos" en d, obtenemos un corte a lo largo del bucle a + b + c. Esto se puede representar mediante la siguiente relación: (a + b + d) + (c − d) = (a + b + c). Para definir formalmente esta relación, definimos los siguientes grupos conmutativos:

• 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) + (c − d) = (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${\displaystyle \partial _{1}}$operador y definido como su objetivo menos su fuente, por lo que${\displaystyle \partial _{1}(a)=yx,~\partial _{1}(b)=zy,~\partial _{1}(c)=\partial _{1}(d)=xz.}$Entonces${\displaystyle \partial _{1}}$es una aplicación del grupo C ₁ al grupo C ₀ . Dado que a, b, c, d son los generadores de C ₁ , esto${\displaystyle \partial _{1}}$naturalmente se extiende a un homomorfismo de grupo de C ₁ a C ₀ . En este homomorfismo,${\displaystyle \partial _{1}(a+b+c)=\partial _{1}(a)+\partial _{1}(b)+\partial _{1}(c)=(yx)+(zy)+(xz)=0}$. Similarmente,${\displaystyle \partial _{1}}$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${\displaystyle \partial _{1}}$En este caso, el núcleo de${\displaystyle \partial _{1}}$tiene dos generadores: uno corresponde a a + b + c y el otro a a + b + d (el tercer ciclo, c − d, es una combinación lineal de los dos primeros). Así pues,${\displaystyle \ker \partial _{1}}$es isomorfo a Z ² .

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, ${\displaystyle \partial _{2}}$, también es trivial. Por lo tanto:$${\displaystyle H_{1}(X)=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}\cong \mathbb {Z} ^{2}/\mathbb {Z} ^{0}=\mathbb {Z} ^{2}}$$Esto corresponde al hecho intuitivo de que la gráfica tiene dos "agujeros". El exponente es el número de agujeros.

El ejemplo anterior se puede generalizar a un grafo conexo arbitrario G = ( V , E ). Sea T un árbol generador de G . Cada arista en E \ T corresponde a un ciclo; estos son precisamente 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 tanto: ^{[ 1 ]}$${\displaystyle H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+1}.}$$En un grafo desconectado, cuando C es el conjunto de componentes conexas, un cálculo similar muestra:$${\displaystyle H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+|C|}.}$$En particular, el primer grupo es trivial si y solo si X es un bosque .

Volviendo 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 ₀ está generado por el conjunto de vértices. Dado que 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:${\displaystyle \ker \partial _{0}=C_{0}}$= el grupo abeliano libre generado por {x, y, z} .

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

El ejemplo anterior se puede generalizar a cualquier grafo conexo . Partiendo de cualquier vértice, es posible llegar a cualquier otro vértice sumándole una o más expresiones correspondientes a las aristas (por ejemplo, partiendo de x, se puede llegar a z sumando y − x y z − y). Dado que los elementos de${\displaystyle \operatorname {soy} \partial _ {1}}$son todos equivalentes a cero, significa que todos los vértices del grafo están en una sola clase de equivalencia y, por lo tanto,${\displaystyle H_{0}(X)}$es isomorfo a Z.

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 cociente. Por lo tanto:$${\displaystyle H_{0}(X)\cong \mathbb {Z} ^{|C|}.}$$Puede ser generado por cualquier | C | -tupla de vértices, uno de cada componente.

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

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

Al igual que el operador de frontera de C ₁ a C ₀ , que denotamos por${\displaystyle \partial _{1}}$, existe un operador de frontera de C ₂ a C ₁ , que denotamos por${\displaystyle \partial _{2}}$. En particular, el límite de la celda bidimensional A son las aristas unidimensionales c y d, donde c está en la orientación "correcta" y d en una orientación "inversa"; por lo tanto:${\displaystyle \partial _{2}(A)=cd}$La secuencia de cadenas y operadores de frontera se puede presentar de la siguiente manera:$${\displaystyle C_{2}\xrightarrow {\partial _{2}} C_{1}\xrightarrow {\partial _{1}} C_{0}}$$La adición de la celda bidimensional A implica que su frontera, c − d, ya no representa un agujero (es homotópica a un solo 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 :$${\displaystyle H_{1}(X):=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}}$$Aquí,${\displaystyle \ker \partial _{1}}$es el grupo de ciclos unidimensionales, que es isomorfo a Z ² , y${\displaystyle \operatorname {soy} \partial _ {2}}$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${\displaystyle \partial _{2}}$era el grupo trivial , por lo que el cociente era igual a${\displaystyle \ker \partial _{1}}$Supongamos ahora que añadimos otra celda bidimensional orientada B entre los bordes c y d, de tal manera que${\displaystyle \partial _{2}(\mathrm {B} )=\partial _{2}(\mathrm {A} )=cd}$. 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 único agujero unidimensional). Pero ahora C ₂ contiene el ciclo bidimensional A − B, por lo que${\displaystyle \partial _{2}}$tiene un núcleo no trivial. Este ciclo genera el segundo grupo de homología, que corresponde al hecho de que hay un único agujero bidimensional:$${\displaystyle H_{2}(X):=\ker \partial _{2}\cong \mathbb {Z} }$$Podemos continuar y agregar una 3-celda: un objeto sólido tridimensional (llamado C) delimitado por A y B. Definimos C ₃ como el grupo abeliano libre generado por {C} y el operador de frontera.${\displaystyle \partial _{3}:C_{3}\to C_{2}}$Podemos orientar C de tal manera que${\displaystyle \partial _{3}(\mathrm {C} )=\mathrm {A} -\mathrm {B} }$; observe que el límite de C es un ciclo en C ₂ . Ahora el segundo grupo de homología es:$${\displaystyle H_{2}(X):=\ker \partial _{2}{\big /}\operatorname {im} \partial _{3}\cong {0}}$$lo cual corresponde al hecho de que no hay agujeros bidimensionales (C "llena el agujero" entre A y B).

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:$${\displaystyle C_{k}\xrightarrow {\partial _{k}} C_{k-1}\cdots C_{1}\xrightarrow {\partial _{1}} C_{0}}$$Se puede demostrar que cualquier límite de una celda ( k + 1)-dimensional es un ciclo k -dimensional. En otras palabras, para cualquier k ,${\displaystyle \operatorname {soy} \partial _ {k+1}}$(el grupo de límites de k + 1 elementos) está contenido en${\displaystyle \ker \partial _{k}}$(el grupo de ciclos k -dimensionales). Por lo tanto, el cociente${\displaystyle \ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}}$está bien definido, y se define como el k- ésimo grupo de homología:$${\displaystyle H_{k}(X):=\ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}}$$