Recorridos: Euler y Hamilton
Recorrer aristas es polinomial, recorrer vertices es NP-completo. Los cinco solidos como banco de pruebas.
1. Los Puentes de Konigsberg (1736)
El primer teorema de la teoria de grafos nacio de un problema recreativo. La ciudad de Konigsberg (hoy Kaliningrado) estaba dividida por el rio Pregel en cuatro zonas de tierra conectadas por siete puentes. Los habitantes se preguntaban: es posible pasear cruzando cada puente exactamente una vez y regresar al punto de partida?
En 1736, Leonhard Euler abstrajo el problema: reemplazo las zonas de tierra por vertices y los puentes por aristas, creando un multigrafo con 4 vertices y 7 aristas. Euler demostro que el paseo era imposible porque mas de dos vertices tenian grado impar. Este argumento fundo la teoria de grafos como disciplina matematica.
La idea clave de Euler fue que la geometria exacta del problema era irrelevante: solo importaba la estructura de conexiones. No interesaba la longitud de los puentes ni la forma de las islas, sino unicamente que vertices estaban conectados. Esta abstraccion es el corazon de la teoria de grafos.
2. Circuitos Eulerianos
Un circuito euleriano en un grafo conexo es un recorrido cerrado que atraviesa cada arista exactamente una vez. Un camino euleriano (no cerrado) atraviesa cada arista exactamente una vez pero puede empezar y terminar en vertices distintos.
El teorema de Euler proporciona una caracterizacion completa:
$$ \text{G tiene circuito euleriano} \iff \forall v \in V: \deg(v) \equiv 0 \pmod{2} $$Es decir, un grafo conexo admite un circuito euleriano si y solo si todos sus vertices tienen grado par. Para un camino euleriano (sin retorno al inicio), la condicion es que exactamente 0 o 2 vertices tengan grado impar.
Apliquemos este criterio a los cinco grafos platonicos. Cada solido platonico es \(q\)-regular, asi que basta verificar la paridad de \(q\):
| Solido | Grado \(q\) | Paridad | Euleriano? |
|---|---|---|---|
| Tetraedro | 3 | impar | No |
| Cubo | 3 | impar | No |
| Octaedro | 4 | par | Si |
| Dodecaedro | 3 | impar | No |
| Icosaedro | 5 | impar | No |
El octaedro es el unico grafo platonico euleriano. Con 6 vertices de grado 4 y 12 aristas, admite un circuito que recorre las 12 aristas sin repetir ninguna. Un circuito euleriano explicito es:
0 → 1 → 2 → 3 → 4 → 1 → 5 → 3 → 0 → 4 → 5 → 2 → 0
12 aristas recorridas, regreso al vertice inicial. Cada arista usada exactamente una vez.
Circuito euleriano del octaedro: las 12 aristas numeradas en orden de recorrido
3. Hamilton y el Icosian Game
En 1857, William Rowan Hamilton invento el Icosian Game, un rompecabezas comercial basado en el grafo del dodecaedro. El desafio consistia en encontrar un ciclo que visitara cada uno de los 20 vertices exactamente una vez, recorriendo aristas del dodecaedro, y regresara al punto de partida.
Un ciclo hamiltoniano en un grafo \(G\) es un ciclo que visita cada vertice exactamente una vez y regresa al vertice inicial. Un camino hamiltoniano visita cada vertice exactamente una vez sin necesidad de regresar. La diferencia con los recorridos eulerianos es fundamental: Euler recorre aristas, Hamilton recorre vertices.
A diferencia del teorema de Euler, que da una condicion necesaria y suficiente elegante, no existe una caracterizacion simple de los grafos hamiltonianos. No hay un criterio basado unicamente en los grados de los vertices que determine si un grafo tiene un ciclo hamiltoniano. Esta asimetria entre los problemas euleriano y hamiltoniano es una de las mas notables en matematicas discretas.
4. Los Cinco Platonicos son Hamiltonianos
Los cinco solidos platonicos admiten ciclos hamiltonianos. A continuacion exhibimos un ciclo explicito para cada uno, verificando que cada arista consecutiva existe en el grafo y que todos los vertices son visitados exactamente una vez.
Tetraedro (4 vertices, \(K_4\))
0 → 1 → 2 → 3 → 0
Trivial: en \(K_4\) toda permutacion de vertices forma un ciclo hamiltoniano.
Cubo (8 vertices, \(Q_3\))
0 → 1 → 3 → 2 → 6 → 7 → 5 → 4 → 0
Codigo Gray de 3 bits: cada paso cambia exactamente un bit.
Octaedro (6 vertices, \(K_{2,2,2}\))
0 → 1 → 5 → 4 → 3 → 2 → 0
Evita los tres pares antipodales \(\{0,5\}, \{1,3\}, \{2,4\}\).
Dodecaedro (20 vertices)
0 → 1 → 6 → 10 → 5 → 14 → 19 → 15 → 16 → 11 → 7 → 2 → 3 → 8 → 12 → 17 → 18 → 13 → 9 → 4 → 0
El Icosian Game original de Hamilton. Los 20 vertices visitados en orden.
Icosaedro (12 vertices)
0 → 1 → 10 → 6 → 2 → 7 → 11 → 8 → 3 → 4 → 9 → 5 → 0
Zigzag entre polo norte (0), anillo superior, anillo inferior y polo sur (11).
La siguiente tabla resume la situacion. El numero de ciclos hamiltonianos distintos (considerando etiquetas de vertices, modulo direccion) da una medida de la riqueza combinatoria de cada grafo.
| Solido | \(V\) | \(E\) | Euleriano | Hamiltoniano | Ciclos Ham. |
|---|---|---|---|---|---|
| Tetraedro | 4 | 6 | No | Si | 3 |
| Cubo | 8 | 12 | No | Si | 6 |
| Octaedro | 6 | 12 | Si | Si | 32 |
| Dodecaedro | 20 | 30 | No | Si | 60 |
| Icosaedro | 12 | 30 | No | Si | 2560 |
Ciclo hamiltoniano del dodecaedro: 20 vertices visitados en orden, aristas del ciclo en cyan
5. Condiciones Suficientes
Aunque no existe una caracterizacion completa, hay condiciones suficientes clasicas que garantizan la existencia de ciclos hamiltonianos. La mas conocida es el teorema de Dirac (1952):
$$ \delta(G) \geq \frac{n}{2} \implies G \text{ es hamiltoniano} $$donde \(\delta(G)\) es el grado minimo del grafo y \(n = |V|\) es el numero de vertices (con \(n \geq 3\)). Dirac exige que cada vertice tenga al menos \(n/2\) vecinos.
El teorema de Ore (1960) generaliza a Dirac: si para todo par de vertices no adyacentes \(\{u,v\}\) se cumple \(\deg(u) + \deg(v) \geq n\), entonces \(G\) es hamiltoniano. Dirac es un caso particular de Ore (si \(\delta \geq n/2\), entonces toda suma de grados de no-adyacentes es al menos \(n\)).
Veamos que dice Dirac sobre los grafos platonicos:
| Solido | \(n\) | \(\delta\) | \(n/2\) | Dirac aplica? |
|---|---|---|---|---|
| Tetraedro \(K_4\) | 4 | 3 | 2 | Si (\(3 \geq 2\)) |
| Cubo | 8 | 3 | 4 | No (\(3 < 4\)) |
| Octaedro | 6 | 4 | 3 | Si (\(4 \geq 3\)) |
| Dodecaedro | 20 | 3 | 10 | No (\(3 < 10\)) |
| Icosaedro | 12 | 5 | 6 | No (\(5 < 6\)) |
Dirac garantiza hamiltonicidad solo para el tetraedro y el octaedro. Sin embargo, el cubo, el dodecaedro y el icosaedro son hamiltonianos a pesar de no satisfacer la condicion de Dirac. Esto ilustra que estas condiciones son suficientes pero no necesarias: un grafo puede ser hamiltoniano sin cumplirlas.
6. Complejidad: P vs NP-completo
El contraste computacional entre los problemas euleriano y hamiltoniano es uno de los mas llamativos en ciencias de la computacion. Determinar si un grafo tiene un circuito euleriano es trivial algoritmicamente: basta verificar que el grafo es conexo y que todos los grados son pares. Esto se resuelve en tiempo \(O(V + E)\), lineal en el tamanio del grafo.
$$ \text{EULER} \in \mathbf{P} \quad \text{vs.} \quad \text{HAMILTON} \in \mathbf{NP\text{-completo}} $$En cambio, determinar si un grafo tiene un ciclo hamiltoniano es NP-completo. No se conoce ningun algoritmo polinomial para este problema, y si existiera, implicaria que \(\mathbf{P} = \mathbf{NP}\). Los mejores algoritmos exactos tienen complejidad exponencial.
El problema del viajante (TSP, Traveling Salesman Problem) es la version de optimizacion: encontrar el ciclo hamiltoniano de peso minimo en un grafo con pesos en las aristas. TSP es NP-duro. Para los grafos platonicos con aristas de peso unitario, todos los ciclos hamiltonianos tienen la misma longitud (igual al numero de vertices), asi que la optimizacion es trivial una vez que se encuentra un ciclo.
Esta asimetria entre Euler y Hamilton emerge de una diferencia estructural profunda. La condicion euleriana es local (depende solo de los grados de los vertices), mientras que la hamiltoniana es global (depende de la estructura completa del grafo). Esta distincion local/global es recurrente en la frontera entre P y NP.
Ejercicios
1. Verifica que el octaedro es el unico solido platonico euleriano comprobando la paridad del grado de los vertices para los cinco grafos. Explica por que un grafo \(q\)-regular con \(q\) impar nunca puede ser euleriano.
2. Encuentra un ciclo hamiltoniano para el cubo distinto al dado en el texto (0-1-3-2-6-7-5-4-0). Cuantos ciclos hamiltonianos distintos tiene el cubo? (Dos ciclos son iguales si recorren los mismos vertices en el mismo orden ciclico, ignorando la direccion.)
3. Comprueba si la condicion de Dirac \(\delta(G) \geq n/2\) se satisface para cada grafo platonico. Para cuales de ellos Dirac garantiza la existencia de un ciclo hamiltoniano?
4. El grafo de Petersen tiene 10 vertices y es 3-regular. No es hamiltoniano. Explica por que el teorema de Dirac no aplica a este grafo y por que esto no contradice el teorema.
5. Considera un grafo donde cada vertice tiene grado exactamente 2 (una union de ciclos disjuntos). Es este grafo necesariamente hamiltoniano? Que condicion adicional se necesita?
LAB: Route Finder
Selecciona un grafo y un modo (Euler o Hamilton). En modo Euler, haz clic en aristas para construir un circuito euleriano. En modo Hamilton, haz clic en vertices para construir un ciclo hamiltoniano. Usa "Mostrar solucion" para revelar un recorrido conocido.