Introducción
La teoría de grafos es una rama fundamental de las matemáticas discretas con aplicaciones en computación, física, biología y más. Sin embargo, su conexión con el álgebra abre nuevas perspectivas para analizar propiedades estructurales mediante herramientas algebraicas como matrices, grupos y polinomios. En este artículo, exploraremos cómo conceptos algebraicos pueden enriquecer nuestro entendimiento de grafos, desde la representación matricial hasta invariantes algebraicos como el polinomio cromático.
Representación Matricial de Grafos
Un grafo $G = (V, E)$ con $n$ vértices puede representarse mediante matrices que capturan su estructura:
Ejemplo 1: Matriz de Adyacencia
Para el grafo $G$ con vértices $V = \{1, 2, 3\}$ y aristas $E = \{(1,2), (2,3)\}$, su matriz de adyacencia $A$ es:
$$
A = \begin{pmatrix}
0 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 0
\end{pmatrix}
$$
Observa que $A$ es simétrica y los valores $A_{ij}$ indican la presencia de aristas entre los vértices $i$ y $j$.
Teorema 1: Traza de $A^k$ y Caminos
El número de caminos cerrados de longitud $k$ en $G$ es igual a la traza de $A^k$.
Demostración:
Por inducción: para $k=1$, $tr(A)$ cuenta bucles (caminos de longitud 1). Para $k > 1$, $A^k_{ii}$ suma productos de adyacencias que corresponden a caminos cerrados.
Polinomio Cromático y Álgebra
El polinomio cromático $P(G, k)$ cuenta las coloraciones propias de $G$ con $k$ colores y satisface relaciones algebraicas profundas.
Teorema 2: Recurrencia del Polinomio Cromático
Para cualquier arista $e$ en $G$, $P(G, k) = P(G – e, k) – P(G/e, k)$, donde $G – e$ es la eliminación de $e$ y $G/e$ es la contracción de $e$.
Demostración:
Las coloraciones de $G – e$ se dividen en aquellas donde los extremos de $e$ tienen colores distintos (contadas en $P(G, k)$) o iguales (contadas en $P(G/e, k)$).
Ejercicio 1: Calcular $P(G, k)$ para un árbol
Para un árbol $T$ con $n$ vértices, demuestra que $P(T, k) = k(k-1)^{n-1}$.
Solución:
Usa inducción: el primer vértice tiene $k$ opciones, y cada vértice sucesivo tiene $k-1$ opciones para evitar repeticiones con su padre.
Grupo de Automorfismos
El grupo de automorfismos $\text{Aut}(G)$ consiste en las permutaciones de vértices que preservan adyacencias, relacionando grafos con teoría de grupos.
Ejemplo 2: $\text{Aut}(K_n)$
Para el grafo completo $K_n$, $\text{Aut}(K_n) \cong S_n$ (grupo simétrico), ya que cualquier permutación de vértices es un automorfismo.
Ejercicio 2: Automorfismos de $C_4$
Describe $\text{Aut}(C_4)$ para el ciclo de 4 vértices.
Solución:
$\text{Aut}(C_4)$ es el grupo diédrico $D_4$, generado por rotaciones y reflexiones, con 8 elementos.
Teorema de Kirchhoff y Árboles Generadores
La matriz Laplaciana $L = D – A$ (donde $D$ es la matriz de grados) conecta con el número de árboles generadores.
Teorema 3: Teorema de Kirchhoff
El número de árboles generadores de $G$ es igual a cualquier cofactor de $L$.
Demostración:
Usa inducción y propiedades de determinantes, mostrando que los cofactores de $L$ cuentan combinaciones de aristas que forman árboles.
Ejercicio 3: Árboles en $K_3$
Calcula el número de árboles generadores de $K_3$ usando el teorema de Kirchhoff.
Solución:
La Laplaciana es $L = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{pmatrix}$. Un cofactor es $\det(L_{11}) = 3$, lo que coincide con los 3 árboles posibles.
Aplicaciones Prácticas
- Redes: La matriz Laplaciana modela flujos en redes eléctricas o de datos.
- Química: Los grafos moleculares usan polinomios cromáticos para predecir propiedades de compuestos.
- Machine Learning: Los métodos espectrales de clustering utilizan autovalores de $A$ o $L$.
Conclusión
La intersección entre teoría de grafos y álgebra ofrece herramientas poderosas para analizar estructuras discretas. Desde matrices hasta grupos algebraicos, estos enfoques no solo enriquecen la teoría pura, sino que también impulsan aplicaciones en ciencia e ingeniería. Invitamos al lector a explorar cómo otras áreas del álgebra, como los anillos de polinomios, pueden seguir ampliando este fascinante campo.
Ejercicios Adicionales
Ejercicio 4: Polinomio Cromático de $C_4$
Calcula $P(C_4, k)$ usando el teorema de recurrencia.
Solución:
Aplicando recurrencia: $P(C_4, k) = P(P_4, k) – P(C_3, k) = k(k-1)^3 – [k(k-1)(k-2)] = k(k-1)(k^2-3k+3)$.
Ejercicio 5: Automorfismos de un Grafo Estrella
Describe $\text{Aut}(S_n)$ para el grafo estrella con $n$ hojas.
Solución:
$\text{Aut}(S_n) \cong S_{n-1}$, permutando las hojas y fijando el centro.
«`