Rutas Eulerianas: Königsberg a Hierholzer

Imagina que estás en un archipiélago, con islas unidas por puentes, y te planteas una pregunta aparentemente simple. ¿Puedes partir de un punto, cruzar cada puente exactamente una vez y regresar al inicio?

Este rompecabezas, formulado por primera vez en la ciudad de Königsberg, desconcertó a matemáticos durante años hasta que Euler propuso una solución revolucionaria. Su trabajo dio origen a los caminos de Euler y circuitos de Euler, conceptos fundamentales de la teoría de grafos.

Incidencia y grado

La idea de que un puente conecta con una masa de tierra es precisamente la noción de incidencia.

Definición Un borde o arista es incidente a un vértice si ese vértice es uno de sus extremos.

El número de formas de llegar a un vértice a través de sus aristas es su grado.

Definición El grado de un vértice es el número de aristas incidentes a él y se denota deg(v). Un bucle cuenta dos veces en el grado porque incide dos veces en el mismo vértice.

En un grafo dirigido distinguimos entre grado de salida y grado de entrada. El grado de entrada de un vértice cuenta cuántas aristas llegan a él y el grado de salida cuántas salen de él. Si sumamos los grados de entrada de todos los vértices, obtenemos el mismo total que al sumar los grados de salida, porque cada arista dirigida aporta una entrada en un vértice y una salida en otro.

Primer teorema de la teoría de grafos o lema del apretón de manos. En un grafo no dirigido, la suma de los grados de todos los vértices es igual al doble del número de aristas. Intuición. Cada arista tiene dos extremos y contribuye con dos al total de grados.

Caminos y circuitos

Un camino es una secuencia de vértices distintos unidos por aristas distintas, que representa una forma de recorrer el grafo. Un circuito es un camino que inicia y termina en el mismo vértice.

Definición Un camino de Euler es un camino que recorre cada arista exactamente una vez. Un circuito de Euler es un camino de Euler que empieza y termina en el mismo vértice.

Condiciones de existencia

Criterio 1 Conectividad. El grafo debe ser conexo cuando ignoramos la dirección de las aristas. Si existe un subgrafo aislado con aristas, no es posible recorrer todas las aristas en un único camino.

Criterio 2 Balance local en grafos dirigidos. Para que se pueda recorrer cada arista exactamente una vez, los vértices deben estar balanceados de entrada y salida salvo posibles vértices de inicio y fin. Si en algún vértice el desbalance absoluto entre deg+(v) y deg-(v) es dos o mayor, no se pueden cubrir todas sus aristas en un único recorrido.

Criterio 3 Regla completa para dirigidos. Para circuito de Euler se requiere deg+(v) igual a deg-(v) en todos los vértices y conectividad subyacente. Para camino de Euler se requiere exactamente un vértice con deg+(v) igual a deg-(v) mas uno que hará de inicio, exactamente un vértice con deg-(v) igual a deg+(v) mas uno que hará de final, y en todos los demás vértices deg+(v) igual a deg-(v), además de conectividad subyacente.

Versión para no dirigidos. Existe camino de Euler si y solo si hay exactamente dos vértices de grado impar. Existe circuito de Euler si y solo si todos los vértices tienen grado par.

Intuición rápida En cualquier vértice intermedio, cada vez que entras por una arista debes poder salir por otra. De ahí que los grados de entrada y salida deban igualar en todos los vértices salvo, como mucho, inicio y fin.

Algoritmo de Hierholzer

Idea básica. Construir paso a paso el recorrido euleriano uniendo ciclos disjuntos hasta usar todas las aristas.

Paso 1 Elige un vértice de inicio. Recorre aristas sin repetir hasta que no puedas continuar. Obtendrás un primer rastro que será un ciclo en el caso de circuito de Euler o un rastro abierto en el caso de camino de Euler.

Paso 2 Si quedan aristas sin usar, busca en el rastro actual un vértice con aristas pendientes, construye desde ahí un nuevo rastro y empálmalo en el rastro principal. Repite hasta agotar todas las aristas. La complejidad temporal es O(E), lineal en el número de aristas.

Aplicaciones y valor práctico

Los caminos y circuitos de Euler aparecen en planificación de rutas, logística, trazado de recorridos óptimos para minimizar desplazamientos, inspección de redes, cobertura completa de zonas y más. En entornos reales conviene combinarlos con heurísticas y restricciones adicionales como ventanas temporales o capacidades.

Cómo lo aplicamos en Q2BSTUDIO

En Q2BSTUDIO, empresa de desarrollo de software, integramos estas técnicas en soluciones de software a medida y aplicaciones a medida para optimizar operaciones, planificar rutas y automatizar procesos complejos. Nuestro equipo es especialista en inteligencia artificial, agentes IA, ia para empresas, ciberseguridad, servicios cloud aws y azure, servicios inteligencia de negocio y power bi. También diseñamos pipelines de datos y paneles analíticos para que la toma de decisiones sea inmediata y accionable. Si buscas incorporar modelos de optimización y aprendizaje en tu operativa, descubre nuestros servicios de inteligencia artificial.

Referencias y recursos

Puentes de Königsberg en Wikipedia. Historia y contexto

Lema del apretón de manos en Wikipedia. Definición y usos

Algoritmo de Hierholzer en Rosetta Code. Implementaciones en múltiples lenguajes