Caminos y circuitos eulerianos explicados

Algunas figuras se pueden dibujar de un solo trazo, sin levantar el lápiz y sin repasar ninguna línea, y otras no, por mucho que se intente. No hace falta intentarlo: cuenta las líneas de cada esquina. Si como mucho dos esquinas tienen un número impar de líneas, la figura se puede dibujar, y en esas esquinas debe empezar y terminar el trazo. Leonhard Euler encontró esta regla en 1736, y con ella fundó la teoría de grafos.

Los siete puentes de Königsberg dibujados como un grafo: cuatro zonas de tierra como vértices, las cuatro con un número impar de puentes, a ambos lados de un río
Los siete puentes de Königsberg dibujados como un grafo: cuatro zonas de tierra como vértices, las cuatro con un número impar de puentes, a ambos lados de un río

Los siete puentes de Königsberg

La ciudad prusiana de Königsberg, hoy Kaliningrado, se extendía por las dos orillas del río Pregel y por dos islas, el Kneiphof y la Lomse. Siete puentes unían las cuatro partes: dos del Kneiphof a cada orilla, uno entre las dos islas y uno de la Lomse a cada orilla. Los vecinos se preguntaban si un paseo podía cruzar cada puente exactamente una vez. Euler respondió en un trabajo que presentó a la Academia de San Petersburgo en 1735 y que se imprimió en 1741: no se puede. Su paso clave fue descartarlo todo salvo las partes de la ciudad y los puentes entre ellas, que es lo que hace un grafo: un vértice por cada zona de tierra y una arista por cada puente, con dos aristas donde dos puentes unen los mismos lugares.

Retrato de Leonhard Euler
Retrato de Leonhard Euler
Portrait of Leonhard Euler
Portrait of Leonhard Euler

La regla de los grados

El grado de un vértice es el número de aristas que llegan a él. Un trazo que pasa por un vértice entra por una arista y sale por otra, así que gasta las aristas de ese vértice por parejas. Solo el primer vértice y el último del trazo pueden quedarse con una arista sin pareja. Por eso un vértice de grado impar tiene que ser el principio o el final del trazo. El Kneiphof tenía cinco puentes y las otras tres partes tres cada una: cuatro vértices impares, dos de más. En general, un grafo conexo tiene un circuito euleriano, un trazo que termina donde empezó, cuando todos los grados son pares, y un camino euleriano cuando exactamente dos grados son impares, de uno al otro. El número de vértices impares nunca es uno, ni ningún otro número impar: cada arista suma 2 al total de los grados, así que el total es par. Euler también lo vio, y hoy se llama lema del apretón de manos.

Por qué basta con la regla

Euler mostró que una figura con más de dos vértices impares no se puede trazar y afirmó, sin demostrarlo, que cualquier otra figura conexa sí. La demostración llegó de Carl Hierholzer, un matemático alemán que murió joven en 1871; su artículo apareció en 1873. Empieza en un vértice impar si lo hay, y si no en cualquiera, y camina por aristas sin usar mientras puedas. Como todos los demás vértices tienen grado par, solo puedes atascarte en el vértice final. Si quedan aristas, algunas tocan el recorrido hecho, porque la figura es conexa. Desde uno de esos vértices camina otra vez hasta atascarte, lo que ahora ocurre al volver a ese vértice, e inserta ahí el bucle en el recorrido. Repite hasta que no quede ninguna arista. La demostración es también el algoritmo más rápido: cada arista se mira un número fijo de veces.

El algoritmo de Fleury: no quemes los puentes

Un trazo puede fallar incluso en una figura que se puede dibujar. Toma dos triángulos unidos por una sola arista y empieza en una esquina del primero: si cruzas al segundo triángulo antes de terminar el primero, ya no podrás volver. La arista de unión es un puente: quitarla parte la figura en dos. El algoritmo de Fleury, de 1883, da una regla: en cada vértice toma una arista que no sea un puente de las aristas restantes, salvo que no haya otra. Siguiéndola siempre se termina. Comprobar si algo es un puente lleva tiempo, así que el algoritmo de Fleury es más lento que el de Hierholzer, pero es el que se puede seguir con un lápiz, y la pista de la aplicación lo usa.

Arreglar una figura

Una figura con k vértices impares necesita k/2 trazos. Para dibujarla de uno solo, añade aristas que unan los vértices impares por parejas: cada arista nueva vuelve pares dos vértices impares. Con k/2 − 1 aristas quedan dos vértices impares y se obtiene un camino; con k/2 no queda ninguno y se obtiene un circuito. Un puente más en Königsberg, entre dos cualesquiera de las cuatro partes, habría hecho posible el paseo, y dos habrían permitido un recorrido de ida y vuelta. La historia hizo algo parecido: dos puentes se perdieron en la Segunda Guerra Mundial y dos fueron sustituidos por una carretera moderna, y los cinco puentes que hoy están en los lugares antiguos se pueden cruzar una vez cada uno, de una isla a la otra.

Contar las formas

La casa de San Nicolás, un cuadrado con sus dos diagonales y un tejado, es la versión del acertijo de los niños alemanes: «Das ist das Haus vom Ni-ko-laus» tiene ocho sílabas, una por cada línea. Sus dos esquinas de abajo son los únicos vértices impares, y hay exactamente 44 formas de dibujarla desde cada una, 88 en total. Para los grafos dirigidos, el número de circuitos eulerianos tiene una fórmula, el teorema BEST, por de Bruijn, van Aardenne-Ehrenfest, Smith y Tutte. Para los grafos ordinarios no se conoce ninguna fórmula así y contar se considera difícil en general, por lo que la aplicación cuenta las figuras pequeñas probando todas las formas y saltándose los pasos que partirían la figura en dos.

Dónde se usan los caminos eulerianos

Un quitanieves, una barredora o un cartero quiere recorrer cada calle una vez y volver. Si en cada cruce hay un número par de calles, basta un circuito euleriano; si no, algunas calles hay que recorrerlas dos veces, y elegir las más baratas es el problema del cartero chino, planteado por Meigu Guan en 1962. Un plóter de plumilla o una cortadora láser ahorra tiempo trazando tantas líneas como pueda sin levantar la herramienta. En la secuenciación de genomas se ensamblan millones de fragmentos cortos de ADN buscando un camino euleriano en un grafo de De Bruijn, en el que cada fragmento es una arista. Y la misma regla dice qué dibujos de un libro de pasatiempos merece la pena intentar.

Pruébalo

Abre el buscador de caminos eulerianos para trazar tú mismo doce figuras, desde Königsberg en 1736 y hoy hasta estrellas, cuadrados anidados y un cubo, o dibuja las tuyas con aristas paralelas. Los vértices impares están rellenos, cada vértice muestra su grado y la regla de los grados bajo la figura dice qué es posible y qué aristas la arreglarían. Si te atascas, la aplicación dice si empezaste en el vértice equivocado o cruzaste un puente demasiado pronto, y en qué paso. Pista da una arista segura, y Resolver dibuja la figura con el algoritmo de Fleury, mostrando la prueba del puente, o con el de Hierholzer, mostrando cada inserción.

Preguntas frecuentes

¿Un camino euleriano es lo mismo que un camino hamiltoniano?

No. Un camino euleriano usa cada arista una vez y puede pasar varias veces por un vértice; un camino hamiltoniano visita cada vértice una vez y no tiene por qué usar todas las aristas. Contar los vértices impares dice enseguida si un grafo tiene un camino euleriano, pero para los caminos hamiltonianos no se conoce ninguna prueba rápida, y encontrar uno es uno de los problemas difíciles clásicos de la informática.

¿Vale la regla de los grados cuando dos vértices están unidos por más de una arista?

Sí. Cada arista cuenta en el grado de sus dos extremos, haya o no otra arista entre los mismos dos vértices. Königsberg es un multigrafo así, con dos puentes del Kneiphof a cada orilla. Una arista de un vértice a sí mismo, un lazo, suma 2 a su grado y nunca cambia si es impar.

¿Y con calles de sentido único?

En un grafo dirigido cada arista tiene un sentido, y la regla compara las aristas que entran en cada vértice con las que salen. Hay un circuito euleriano cuando en cada vértice entran tantas aristas como salen y las aristas forman una sola pieza, y un camino euleriano cuando un vértice tiene una arista más de salida, otro una más de entrada y todos los demás están equilibrados. El camino va entonces del primero al segundo.

¿Puede existir una figura con exactamente un vértice impar?

No. Los grados de todos los vértices suman el doble del número de aristas, porque cada arista tiene dos extremos. Esa suma es par, así que el número de grados impares que contiene también debe ser par: 0, 2, 4 y así sucesivamente, nunca 1 ni 3.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Abrir el buscador de caminos eulerianos