Leccion 29: Espectros, Arboles y Sintesis

1. Arboles de Expansion

Un arbol es un grafo conexo sin ciclos. Un arbol con $n$ vertices tiene exactamente $n - 1$ aristas. Dado un grafo conexo $G$, un arbol de expansion (spanning tree) es un subgrafo que es arbol y contiene todos los vertices de $G$. Se obtiene eliminando aristas hasta suprimir todos los ciclos, sin desconectar el grafo.

Todo grafo conexo tiene al menos un arbol de expansion. Notamos $\tau(G)$ al numero de arboles de expansion de $G$. Este numero puede ser enorme: para el grafo completo $K_n$, la formula de Cayley establece:

$$ \tau(K_n) = n^{n-2} $$

Verificacion directa: $\tau(K_3) = 3^1 = 3$ (los tres arboles se obtienen eliminando una de las tres aristas), y $\tau(K_4) = 4^2 = 16$.

Para un poliedro con $V$ vertices y $E$ aristas, cada arbol de expansion tiene exactamente $V - 1$ aristas, asi que se eliminan $E - V + 1$ aristas. Por la formula de Euler, $E - V + 1 = F - 1$, donde $F$ es el numero de caras. El numero de aristas eliminadas es exactamente $F - 1$.

Arbol de expansion del cubo: 7 aristas en cyan (arbol), 5 aristas en gris (eliminadas)

2. El Teorema de Kirchhoff (Matrix-Tree)

La matriz laplaciana de un grafo $G$ es $L = D - A$, donde $D$ es la matriz diagonal de grados y $A$ es la matriz de adyacencia. Explicitamente:

$$ L_{ij} = \begin{cases} \deg(v_i) & \text{si } i = j \\ -1 & \text{si } \{v_i, v_j\} \in E \\ 0 & \text{en otro caso} \end{cases} $$

El teorema de Kirchhoff (Matrix-Tree theorem) proporciona una formula exacta para contar arboles de expansion: $\tau(G)$ es igual a cualquier cofactor de $L$ (todos los cofactores son iguales):

$$ \tau(G) = \det(L_{11}) $$

donde $L_{11}$ es la matriz $L$ con la primera fila y la primera columna eliminadas.

Ejemplo: Tetraedro ($K_4$)

D = diag(3,3,3,3), A = J - I

La laplaciana es $L = D - A = 4I - J$:

$$ L = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{pmatrix} $$

Eliminando fila 0 y columna 0:

$$ L_{11} = \begin{pmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{pmatrix} $$

det(L₁₁) = 3(9-1) - (-1)(-3-1) + (-1)(1+3) = 24 - 4 - 4 = 16

Resultado: $\tau(K_4) = 16$, que coincide con Cayley: $4^2 = 16$.

Ejemplo: Cubo

Aplicando el mismo procedimiento al cubo (8 vertices, 3-regular), se obtiene $\tau(\text{cubo}) = 384$. La verificacion completa requiere calcular el determinante de una matriz $7 \times 7$, pero el resultado puede confirmarse computacionalmente.

3. Espectro del Laplaciano

Los autovalores de $L$ se denominan el espectro laplaciano del grafo: $0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$. La matriz $L$ es positiva semidefinida, asi que todos los autovalores son no negativos.

El autovalor $\lambda_1 = 0$ siempre existe, con autovector el vector de unos $\mathbf{1} = (1, 1, \ldots, 1)^T$. Esto es inmediato: cada fila de $L$ suma cero, asi que $L\mathbf{1} = \mathbf{0}$.

Propiedades fundamentales del espectro:

La multiplicidad del autovalor 0 es igual al numero de componentes conexas del grafo.
El segundo autovalor $\lambda_2$ se llama conectividad algebraica (valor de Fiedler). Se cumple $\lambda_2 > 0$ si y solo si $G$ es conexo.
Un valor mayor de $\lambda_2$ indica un grafo "mas conectado": mas dificil de desconectar eliminando aristas.

Los espectros laplacianos de los grafos platonicos revelan su estructura. Los autovalores de la adyacencia se obtienen de la teoria de grafos fuertemente regulares y grafos multipartitos completos. Como $L = D - A$, los autovalores laplacianos son $\lambda_i^{(L)} = q - \lambda_i^{(A)}$, donde $q$ es el grado.

Grafo	$\lambda_2$	Espectro laplaciano
Tetraedro	4	{0, 4, 4, 4}
Cubo	2	{0, 2, 2, 2, 4, 4, 4, 6}
Octaedro	4	{0, 4, 4, 6, 6, 6}
Dodecaedro	≈ 0.764	$3 - \sqrt{5} \approx 0.764$
Icosaedro	≈ 2.764	$5 - \sqrt{5} \approx 2.764$

El tetraedro y el octaedro comparten $\lambda_2 = 4$, la mayor conectividad algebraica entre los platonicos. El dodecaedro tiene la menor ($\lambda_2 \approx 0.764$), reflejando que es el "menos conectado" en proporcion a su tamanio: 20 vertices con grado apenas 3.

Espectro laplaciano del tetraedro: autovalores {0, 4, 4, 4}

4. Conjuntos Independientes y Cliques

Un conjunto independiente es un conjunto de vertices mutuamente no adyacentes. El numero de independencia $\alpha(G)$ es el tamanio maximo de un conjunto independiente. Un clique es un conjunto de vertices mutuamente adyacentes. El numero de clique $\omega(G)$ es el tamanio maximo de un clique.

Grafo	$\alpha(G)$	$\omega(G)$	Observacion
Tetraedro	1	4	Completo: todo par es adyacente
Cubo	4	2	Bipartito, sin triangulos (cintura 4)
Octaedro	2	3	Un par antipodal; triangulos presentes
Dodecaedro	8	2	Sin triangulos (cintura 5)
Icosaedro	3	3	Tiene triangulos como caras

Estos invariantes se relacionan con la coloracion. Si $\chi(G)$ es el numero cromatico, el principio del palomar garantiza:

$$ \alpha(G) \cdot \chi(G) \geq |V| $$

Verificacion para el cubo: $\alpha = 4$, $\chi = 2$, $|V| = 8$, y $4 \cdot 2 = 8 \geq 8$. Para el dodecaedro: $\alpha = 8$, $\chi = 3$, $|V| = 20$, y $8 \cdot 3 = 24 \geq 20$.

5. Numero de Dominacion

Un conjunto dominante es un subconjunto $S \subseteq V$ tal que todo vertice de $G$ esta en $S$ o es adyacente a algun vertice de $S$. El numero de dominacion $\gamma(G)$ es el tamanio minimo de un conjunto dominante.

Cada vertice de grado $q$ "domina" a lo sumo $q + 1$ vertices (si mismo y sus vecinos), lo que da la cota inferior $\gamma(G) \geq \lceil V / (q + 1) \rceil$.

Grafo	$\gamma(G)$	Justificacion
Tetraedro	1	Cualquier vertice es adyacente a todos los demas
Cubo	2	Dos vertices diagonalmente opuestos dominan los 8
Octaedro	2	Un vertice cubre 5 de 6; se necesitan al menos 2
Dodecaedro	4	Cada vertice cubre 4; se requieren al menos $\lceil 20/4 \rceil = 5$, alcanzable con 4
Icosaedro	2	Dos vertices antipodales cubren los 12

El icosaedro admite $\gamma = 2$ porque cada vertice tiene grado 5, dominando 6 vertices. Dos vertices sin vecinos comunes cubren $6 + 6 = 12$ vertices, la totalidad del grafo. El dodecaedro, con grado 3, necesita mas vertices dominantes para cubrir sus 20 vertices.

6. Sintesis del Modulo 5

Este modulo ha explorado los solidos platonicos desde la perspectiva de la teoria de grafos. Recapitulamos las cinco lecciones:

L25 -- De Poliedros a Grafos. El grafo esqueleto $G(P)$, la matriz de adyacencia, el lema del apreton de manos. Los cinco grafos platonicos como objetos combinatorios.
L26 -- Grafos Planares y Steinitz. Planaridad, la formula de Euler $V - E + F = 2$ para grafos planares, los teoremas de Kuratowski y Steinitz. Cada grafo platonico es 3-conexo y planar.
L27 -- Coloracion de Grafos. Numeros cromaticos, el teorema de los cuatro colores, el polinomio cromatico. Los cinco grafos platonicos como banco de pruebas.
L28 -- Recorridos: Euler y Hamilton. Circuitos eulerianos (ninguno de los platonicos los tiene), circuitos hamiltonianos (todos los platonicos los tienen). El contraste P vs. NP.
L29 -- Espectros, Arboles y Sintesis. El laplaciano, el teorema de Kirchhoff, conectividad algebraica, conjuntos independientes, cliques y dominacion.

Los cinco grafos platonicos funcionan como un banco de pruebas ideal: son lo bastante simples para calcular a mano, pero lo bastante ricos para ilustrar todos los conceptos fundamentales de teoria de grafos.

7. El Gran Arco

Con esta leccion se cierra el arco principal del curso. Revisamos la trayectoria completa:

Modulo 1: Los cinco solidos platonicos -- geometria euclidiana, la formula de Euler, la clasificacion completa mediante $(p-2)(q-2) < 4$.
Modulo 2: Grupos de simetria -- rotaciones, reflexiones, el teorema orbita-estabilizador, los grupos de los poliedros.
Modulo 3: Dualidad y simbolos de Schlafli -- la notacion $\{p, q\}$, los pares duales, el tetraedro autodual.
Modulo 4: Dimensiones superiores -- el teseracto, los politopos regulares en 4D, la formula de Euler-Poincare.
Modulo 5: Teoria de grafos -- planaridad, coloracion, hamiltonicidad, espectros laplacianos.

Los solidos platonicos se situan en la interseccion de la geometria, el algebra, la topologia, la combinatoria y la computacion. Son un microcosmos de las matematicas: un punto de partida simple --cinco objetos que un ninio puede construir con papel-- que conecta con teoria profunda.

Desde la clasificacion geometrica de Euclides hasta el espectro del laplaciano, desde los grupos de simetria hasta los circuitos hamiltonianos, cada perspectiva revela una capa nueva de estructura. Esa es la naturaleza de las matematicas: un objeto simple, mirado desde angulos distintos, genera un universo de conexiones.

Ejercicios

1. Construye la matriz laplaciana $L$ del tetraedro ($K_4$). Verifica que el vector de unos $\mathbf{1} = (1,1,1,1)^T$ es un autovector con autovalor 0, es decir, que $L\mathbf{1} = \mathbf{0}$.

2. Usa el teorema de Kirchhoff para calcular $\tau(K_4)$. Elimina la primera fila y columna de $L$ y calcula el determinante de la matriz $3 \times 3$ resultante. Verifica que el resultado coincide con la formula de Cayley $4^2 = 16$.

3. Para el cubo, determina $\alpha(G)$ y $\omega(G)$. Exhibe explicitamente un conjunto independiente maximo y un clique maximo. Verifica la desigualdad $\alpha \cdot \chi \geq V$.

4. Encuentra un arbol de expansion del dodecaedro. Cuantas aristas tiene? Cuantas aristas deben eliminarse del grafo original? Relaciona este ultimo numero con el numero de caras.

5. La conectividad algebraica $\lambda_2$ del tetraedro es 4, mientras que para el dodecaedro es aproximadamente 0.76. Explica intuitivamente por que el tetraedro es "mas conectado" a pesar de tener menos vertices.

LAB: Explorador Espectral

Selecciona un grafo platonico para visualizar su estructura y su espectro laplaciano. El panel inferior muestra los invariantes espectrales y combinatorios.

τ(G)=16 λ₂=4 α(G)=1 ω(G)=4 γ(G)=1