De Poliedros a Grafos
Todo poliedro tiene un esqueleto combinatorio. Cambiar de perspectiva abre herramientas nuevas y poderosas.
1. De la Geometria a la Combinatoria
En los modulos anteriores estudiamos los solidos platonicos desde la geometria euclidiana, la topologia y el algebra. Ahora cambiamos de paradigma: olvidamos las distancias, los angulos y las areas, y nos quedamos unicamente con la estructura de conexiones. Este es el punto de vista de la teoria de grafos.
Un grafo \(G = (V, E)\) consta de un conjunto finito de vertices \(V\) y un conjunto de aristas \(E\), donde cada arista es un par no ordenado \(\{u, v\}\) con \(u, v \in V\) y \(u \neq v\). La definicion es deliberadamente abstracta: no hay coordenadas, no hay forma.
Terminologia esencial. Dos vertices \(u\) y \(v\) son adyacentes si \(\{u,v\} \in E\). El grado de un vertice \(v\), escrito \(\deg(v)\), es el numero de aristas incidentes a \(v\). Un camino de longitud \(k\) es una sucesion de vertices \(v_0, v_1, \ldots, v_k\) donde cada par consecutivo es adyacente. Un ciclo es un camino cerrado (\(v_0 = v_k\)) sin vertices repetidos internos. Un grafo es conexo si entre cualquier par de vertices existe al menos un camino.
Esta abstraccion es poderosa: permite aplicar resultados de teoria de grafos (coloracion, hamiltonicidad, espectro) a cualquier poliedro, sin importar si sus caras son triangulos equilateros o pentagonos irregulares.
2. El Grafo Esqueleto \(G(P)\)
Dado un poliedro \(P\), su grafo esqueleto \(G(P)\) se construye tomando los vertices geometricos de \(P\) como vertices del grafo, y las aristas geometricas como aristas del grafo. Las caras de \(P\) se manifiestan como ciclos en \(G(P)\): cada cara \(p\)-gonal corresponde a un ciclo de longitud \(p\).
El ejemplo mas simple es el tetraedro. Sus 4 vertices estan todos conectados entre si (cada par de vertices comparte una arista), de modo que \(G(\text{tetraedro}) = K_4\), el grafo completo de 4 vertices. En un grafo completo \(K_n\), toda pareja de vertices es adyacente, y el numero de aristas es \(\binom{n}{2}\).
$$ |E(K_n)| = \binom{n}{2} = \frac{n(n-1)}{2} $$Para \(K_4\): \(\binom{4}{2} = 6\) aristas, que coincide con las 6 aristas del tetraedro.
El cubo tiene un grafo esqueleto que no es completo. Sus 8 vertices se conectan de modo que cada vertice tiene exactamente 3 vecinos. Este grafo coincide con el grafo del hipercubo \(Q_3\): los vertices son cadenas binarias de longitud 3, y dos vertices son adyacentes si difieren en exactamente un bit.
El octaedro tiene grafo \(K_{2,2,2}\), el grafo tripartito completo: tres pares de vertices antipodales, donde todo vertice es adyacente a todos excepto a su antipodal.
3. La Matriz de Adyacencia
La informacion combinatoria de un grafo puede codificarse en una matriz. Dado \(G = (V, E)\) con \(|V| = n\), la matriz de adyacencia \(A\) es la matriz \(n \times n\) definida por:
$$ A_{ij} = \begin{cases} 1 & \text{si } \{v_i, v_j\} \in E \\ 0 & \text{en otro caso} \end{cases} $$Como las aristas no tienen direccion, \(A\) es simetrica: \(A^T = A\). No hay lazos (aristas de un vertice a si mismo), asi que \(A_{ii} = 0\) y la traza \(\operatorname{tr}(A) = 0\).
Una propiedad fundamental: la entrada \((A^2)_{ij}\) cuenta el numero de caminos de longitud 2 entre \(v_i\) y \(v_j\). En particular, \((A^2)_{ii} = \deg(v_i)\), pues un camino de longitud 2 que empieza y termina en \(v_i\) pasa por un vecino de \(v_i\).
Para el tetraedro \(K_4\), con vertices \(\{0,1,2,3\}\):
$$ A = \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}, \qquad A^2 = \begin{pmatrix} 3 & 2 & 2 & 2 \\ 2 & 3 & 2 & 2 \\ 2 & 2 & 3 & 2 \\ 2 & 2 & 2 & 3 \end{pmatrix} $$La diagonal de \(A^2\) vale 3 (el grado de cada vertice). Las entradas fuera de la diagonal valen 2: entre cualquier par de vertices de \(K_4\) hay exactamente 2 caminos de longitud 2 (pasando por cada uno de los otros dos vertices). En notacion compacta: \(A = J - I\) y \(A^2 = 2J + I\), donde \(J\) es la matriz de unos e \(I\) la identidad.
Matriz de adyacencia del tetraedro: violeta = 1 (adyacente), oscuro = 0
4. Handshaking y Conteo
El lema del apretón de manos (handshaking lemma) es el resultado mas basico y mas util de teoria de grafos. Cada arista tiene dos extremos, asi que al sumar los grados de todos los vertices, cada arista se cuenta exactamente dos veces:
$$ \sum_{v \in V} \deg(v) = 2|E| $$Para un poliedro con simbolo de Schlafli \(\{p, q\}\), cada vertice tiene grado \(q\) y cada cara es un \(p\)-gono. Entonces:
$$ Vq = 2E \quad \text{(handshaking)} \qquad Fp = 2E \quad \text{(cada arista bordea 2 caras)} $$Combinando con la formula de Euler \(V - E + F = 2\), sustituimos \(V = 2E/q\) y \(F = 2E/p\):
$$ \frac{2E}{q} - E + \frac{2E}{p} = 2 \implies E\left(\frac{2}{q} + \frac{2}{p} - 1\right) = 2 $$Esto nos da una formula cerrada para \(E\), y con ella \(V\) y \(F\):
$$ E = \frac{2pq}{2p + 2q - pq}, \qquad V = \frac{4p}{2p + 2q - pq}, \qquad F = \frac{4q}{2p + 2q - pq} $$La condicion para que existan soluciones positivas es \(2p + 2q - pq > 0\), equivalente a \((p-2)(q-2) < 4\). Esta es precisamente la desigualdad que clasifica los cinco solidos platonicos.
Verificacion para el cubo \(\{4, 3\}\):
E = 2(4)(3) / (8 + 6 - 12) = 24/2 = 12 V = 4(4)/2 = 8 F = 4(3)/2 = 6 8 - 12 + 6 = 2 ✓
5. Los Cinco Grafos Platonicos
La siguiente tabla resume las propiedades combinatorias de los cinco grafos esqueleto. El diametro es la maxima distancia (camino mas corto) entre cualquier par de vertices. La cintura (girth) es la longitud del ciclo mas corto.
| Solido \(\{p,q\}\) | V | E | F | Grado | Diam. | Cintura | Grafo |
|---|---|---|---|---|---|---|---|
| Tetraedro \(\{3,3\}\) | 4 | 6 | 4 | 3 | 1 | 3 | \(K_4\) |
| Cubo \(\{4,3\}\) | 8 | 12 | 6 | 3 | 3 | 4 | \(Q_3\) |
| Octaedro \(\{3,4\}\) | 6 | 12 | 8 | 4 | 2 | 3 | \(K_{2,2,2}\) |
| Dodecaedro \(\{5,3\}\) | 20 | 30 | 12 | 3 | 5 | 5 | 3-regular |
| Icosaedro \(\{3,5\}\) | 12 | 30 | 20 | 5 | 3 | 3 | 5-regular |
Observaciones. El tetraedro tiene diametro 1 porque es completo (todo par de vertices es adyacente). El cubo y el dodecaedro son 3-regulares pero con diametros muy distintos (3 vs. 5), lo que refleja la diferencia de tamanio. El cubo y el octaedro comparten \(E = 12\) pero con distribuciones distintas de grado (3 vs. 4).
Los cinco grafos platonicos en disposicion circular: tetraedro, cubo, octaedro, dodecaedro, icosaedro
6. Grafo Dual
Todo grafo planar tiene un grafo dual \(G^*\), construido colocando un vertice en cada cara de \(G\) y conectando dos vertices de \(G^*\) cuando las caras correspondientes comparten una arista en \(G\). Para poliedros, esto equivale a la dualidad clasica de Modulo 3.
El tetraedro \(\{3,3\}\) es autodual: su dual es otro tetraedro. Formalmente, \(G^*(\text{tetraedro}) \cong K_4 = G(\text{tetraedro})\). Esto refleja que intercambiar \(p \leftrightarrow q\) en \(\{3,3\}\) produce el mismo simbolo.
Los demas forman pares duales: el dual del cubo \(\{4,3\}\) es el octaedro \(\{3,4\}\), y el dual del dodecaedro \(\{5,3\}\) es el icosaedro \(\{3,5\}\). En terminos de grafos:
$$ G^*(\text{cubo}) \cong G(\text{octaedro}), \qquad G^*(\text{dodecaedro}) \cong G(\text{icosaedro}) $$La correspondencia explicita para cubo-octaedro es: las 6 caras del cubo se convierten en los 6 vertices del octaedro, y dos caras del cubo que comparten una arista producen una arista en el octaedro. Las 12 aristas del cubo generan 12 aristas en el octaedro.
A nivel de grafos, la dualidad intercambia \(V \leftrightarrow F\) mientras preserva \(E\). Esto es consistente con la formula de Euler: si \(V - E + F = 2\) para \(G\), entonces \(F - E + V = 2\) para \(G^*\), que es la misma ecuacion.
Ejercicios
1. Escribe la matriz de adyacencia \(A\) del octaedro (6 vertices, con los pares antipodales \(\{0,5\}, \{1,3\}, \{2,4\}\) no conectados). Calcula \(A^2\) y verifica que las entradas diagonales son 4 (el grado de cada vertice).
2. Verifica el lema del apreton de manos \(\sum \deg(v) = 2|E|\) para los cinco solidos platonicos. En cada caso, calcula \(V \cdot q\) y comprueba que coincide con \(2E\).
3. Determina el diametro del dodecaedro. Identifica un par de vertices a distancia 5 y demuestra que no existe un camino mas corto entre ellos. Pista: el dodecaedro tiene 20 vertices y es 3-regular.
4. Construye explicitamente la correspondencia entre el dual del cubo y el grafo del octaedro. Etiqueta las 6 caras del cubo como \(f_1, \ldots, f_6\) y muestra que las adyacencias entre caras reproducen exactamente las aristas del octaedro.
5. El cubo es bipartito: sus 8 vertices se pueden dividir en dos conjuntos de 4 tal que toda arista conecta un vertice de cada conjunto. Exhibe la biparticion explicitamente usando la representacion binaria de los vertices y demuestra que ningun otro solido platonico es bipartito.
LAB: Explorador de Grafos Platonicos
Selecciona un grafo platonico para visualizarlo. Arrastra vertices para reorganizar la disposicion. Haz clic en un vertice para resaltar sus vecinos.