Tabla de Contenidos
1. ¿Qué es un Sendero Euleriano?
Un sendero euleriano (también llamado camino de Euler) es un recorrido por un grafo que usa cada arista exactamente una vez. Puedes pasar por el mismo vértice muchas veces, pero nunca recorrer la misma arista dos veces.
Responde a una pregunta sorprendentemente práctica: dada una red de carreteras, tuberías o cables, ¿puedo recorrerlas todas sin repetir ninguna conexión?
2. Sendero vs Circuito Euleriano
Los dos términos están relacionados pero no son idénticos:
- Un sendero euleriano usa cada arista una vez y puede empezar y terminar en vértices diferentes.
- Un circuito euleriano es un sendero euleriano cerrado: usa cada arista una vez y vuelve a su vértice de partida.
Todo circuito euleriano es también un sendero euleriano, pero no al revés. Qué admite cada grafo depende por completo de los grados de sus vértices.
3. Los Siete Puentes de Königsberg
La ciudad prusiana de Königsberg estaba dividida por un río en cuatro masas de tierra, unidas por siete puentes. Sus habitantes se preguntaban si era posible dar un paseo que cruzara cada puente exactamente una vez y volviera al inicio.
En 1736, Leonhard Euler demostró que tal paseo no existe. Modeló cada masa de tierra como un vértice y cada puente como una arista, y observó algo decisivo: cada vez que entras en una masa de tierra por un puente, debes salir por otro, así que todo vértice "de paso" necesita un número par de puentes. Los cuatro vértices de Königsberg tenían un número impar de puentes, lo que hacía imposible el paseo. Esta demostración se considera el nacimiento de la teoría de grafos. (Consulta nuestra historia de la teoría de grafos.)
4. La Regla de los Grados: ¿Cuándo Existe?
El grado de un vértice es el número de aristas que lo tocan. La idea de Euler da reglas simples y exactas para un grafo conexo:
- Existe un circuito euleriano si y solo si todos los vértices tienen grado par.
- Existe un sendero euleriano abierto si y solo si exactamente dos vértices tienen grado impar, y debe empezar en uno y terminar en el otro.
- Si más de dos vértices tienen grado impar, no existe ningún sendero euleriano.
El grafo también debe ser conexo. Por lo demás, basta con contar los vértices de grado impar.
Recorre el Grafo Tú Mismo
Construye una red y observa cómo un algoritmo traza un sendero euleriano arista por arista, y ve exactamente por qué los vértices de grado impar lo impiden.
Abrir el Visualizador5. Cómo Encontrarlo: Algoritmos de Fleury y Hierholzer
Una vez que sabes que existe un sendero, dos algoritmos clásicos lo construyen:
Algoritmo de Fleury
Recorre el grafo una arista a la vez y nunca cruces un puente (una arista cuya eliminación desconectaría el grafo) salvo que no tengas otra opción. Es fácil de entender, pero comprobar los puentes constantemente lo hace relativamente lento.
Algoritmo de Hierholzer
La opción eficiente, con tiempo O(E). Sigue aristas para formar un ciclo cerrado, luego busca repetidamente un vértice de tu camino actual que aún tenga aristas sin usar e inserta allí otro ciclo. Cuando no quedan aristas sin usar, los ciclos se fusionan en un único circuito euleriano.
6. Euler vs Hamilton
Se confunden constantemente, pero son problemas completamente distintos:
- Un camino euleriano visita cada arista una vez.
- Un camino hamiltoniano visita cada vértice una vez.
El giro es computacional: decidir si existe un sendero euleriano es fácil (basta contar grados impares), mientras que decidir si existe un camino hamiltoniano es NP-completo, de los problemas más difíciles en informática. El Problema del Viajante es un reto famoso de estilo hamiltoniano.
7. Aplicaciones del Mundo Real
- Inspección de rutas (problema del cartero chino): encontrar la ruta más corta que recorra cada calle: correo, recogida de basura, quitanieves, barrido de calles.
- Secuenciación de ADN: el ensamblaje moderno de genomas construye un grafo de De Bruijn a partir de lecturas cortas y halla un camino euleriano para reconstruir la secuencia.
- Mantenimiento de redes: inspeccionar o probar cada enlace de una red de telecomunicaciones o servicios exactamente una vez.
- Dibujos "de un solo trazo": el clásico acertijo de dibujar una figura sin levantar el lápiz es exactamente una pregunta de sendero euleriano.
Preguntas Frecuentes
¿Cuál es la diferencia entre un camino y un circuito euleriano?
Un camino (sendero) euleriano usa cada arista exactamente una vez y puede empezar y terminar en vértices diferentes. Un circuito euleriano también usa cada arista una vez, pero debe empezar y terminar en el mismo vértice.
¿Cómo sé si un grafo tiene un sendero euleriano?
En un grafo conexo, existe un circuito euleriano si todos los vértices tienen grado par, y un sendero euleriano abierto si exactamente dos vértices tienen grado impar. Si más de dos vértices tienen grado impar, no existe ningún sendero euleriano.
¿Cuál es la diferencia entre un camino euleriano y uno hamiltoniano?
Un camino euleriano visita cada arista una vez, mientras que un camino hamiltoniano visita cada vértice una vez. Comprobar un camino euleriano es fácil, pero comprobar uno hamiltoniano es NP-completo.
¿Por qué es imposible el problema de los Siete Puentes de Königsberg?
Las cuatro masas de tierra estaban unidas por un número impar de puentes. Un sendero euleriano admite como máximo dos vértices de grado impar, así que cruzar cada puente exactamente una vez es imposible.