Grafo de Cayley

En matemática el grafo de Cayley es un grafo que muestra la estructura de un grupo. Su nombre honra al matemático británico Arthur Cayley, quien introdujo estos grafos en 1878.^[1] Los grafos de Cayley son fundamentales en la teoría geométrica de grupos.

Sea $G$ un grupo y $S\subseteq G$ un subconjunto.

El grafo de Cayley ${\mathcal {C}}$ cumple:

los vértices del grafo ${\mathcal {C}}$ son los elementos del grupo $G$ : $V({\mathcal {C}})\subseteq G$
el par ordenado (g,h) es una arista del grafo si existe s perteneciente a S tal que gs=h: $\exists s\in S:gs=h\implies (g,h)\in E({\mathcal {C}})$ o equivalentemente, si g^-1h pertenece a S: ${g^{-1}h}\in S$

El segundo punto es en ocasiones cambiado por lo siguiente: el par ordenado (g,h) es una arista del grafo si existe s perteneciente a S tal que sg=h (o, de forma equivalente, si hg^-1 pertenece a S).

En general se estudia el grafo de Cayley con S generador del grupo G (lo que hace al grafo conexo) y tal que el neutro del grupo no está en S (de esta manera no hay lazos en el grafo). Además, suele asumirse que el conjunto S es simétrico, es decir, si t pertenece a S entonces t^-1 también. Esta última propiedad hace al grafo de Cayley no orientado.

Ejemplos

Grafo de Cayley del grupo S3 con conjunto de generadores {(12), (123)}

Si el grupo es $\mathbb {Z}$ con la operación suma y tomamos como conjunto generador a S={1} entonces el grafo de Cayley resulta un camino infinito, con aristas uniendo cada entero con su consecutivo.
El grafo del grupo $(\mathbb {Z} _{n},+)$ con S={1,-1} es el grafo ciclo C_n.
Si G es un grupo cualquiera con n elementos y tomamos S=G-{e} entonces su grafo de Cayley será el grafo completo K_n.
Si A es un conjunto finito y tomamos el grupo libre F_A con $S=A\cup A^{-1}$ entonces su grafo de Cayley será un árbol infinito.^[1]

Ejemplos

Propiedades

Referencias

Related Articles