Los siete puentes de Königsberg y el nacimiento de los grafos

Hay problemas que nacen como un entretenimiento y acaban cambiando una disciplina entera. Este es uno de ellos: ¿puede alguien pasear por una ciudad cruzando cada uno de sus siete puentes exactamente una vez? Suena a acertijo de sobremesa, y el propio Euler, que lo resolvió, lo veía poco más que así. Sin embargo, la forma en que lo miró inauguró una manera nueva de hacer matemáticas.

Una ciudad con un río y siete puentes

Königsberg estaba en Prusia, a orillas del río Pregel, que allí se bifurca y rodea dos islas, Kneiphof y Lomse. Hoy la ciudad se llama Kaliningrado y es rusa. En tiempos de Euler, siete puentes unían las orillas y las islas entre sí. Él mismo cuenta que el problema era, según le habían dicho, ampliamente conocido: unos lo daban por imposible, otros dudaban, y nadie afirmaba que se pudiera lograr.

Un problema que llegó por carta

Primer matiz a la versión de manual: Euler, hasta donde se sabe, nunca visitó Königsberg, y no se sabe con certeza cuándo ni por quién conoció el problema. Lo más plausible es que fuera por correspondencia. Karl Leonhard Gottlieb Ehler, matemático aficionado y alcalde de Danzig entre 1740 y 1753, hacía de intermediario con Heinrich Kühn, y una carta suya del 9 de marzo de 1736 incluye un dibujo de la ciudad.

Pocos días después, el 13 de marzo de 1736, Euler esbozaba su solución en una carta a Giovanni Marinoni, y el 3 de abril lo hacía en otra a Ehler. Se nota su actitud. En la carta a Marinoni dice que la cuestión es banal, pero digna de atención porque ni la geometría, ni el álgebra, ni siquiera el arte de contar bastaban para resolverla, según la traducción de Sachs, Stiebitz y Wilson.

Las fechas del artículo tampoco son una sola. De la memoria de Euler, Solutio problematis ad geometriam situs pertinentis, las actas de la Academia dicen que se presentó el 26 de agosto de 1735, aunque hay quien cree que esa fecha es una errata, y Grötschel y Yuan señalan que Euler probablemente conoció el problema por la carta de Ehler de marzo de 1736. El volumen de las actas lleva el año 1736, pero no apareció hasta 1741. De ahí que se oiga hablar de 1735, 1736 y 1741, y las tres tienen su motivo.

La geometría de la posición

Euler abre el artículo con una declaración de intenciones: además de la geometría de siempre existe otra rama casi desconocida, que Leibniz llamó geometria situs, geometría de la posición, y que no usa medidas ni cálculos. Leibniz ya había escrito a Huygens en 1679 que hacía falta otro tipo de análisis, geométrico o lineal, que tratara directamente la posición como el álgebra trata la magnitud.

La idea clave consiste en tirar casi toda la información. No importa cuánto miden los puentes ni qué forma tienen las islas. Solo importa qué zonas de tierra hay y cuántos puentes unen cada par.

Eso es lo que hoy llamamos un grafo: unos puntos y unas líneas que los unen. Pero sin anticiparse: Euler no usa las palabras grafo, vértice, arista ni grado, que no existían aún. Él habla de zonas, de puentes y de sucesiones de letras.

Por qué no sirve probar a ciegas

La salida ingenua es enumerar recorridos. Solo ordenar los siete puentes de todas las maneras posibles da $7! = 5040$ posibilidades, antes de ver si cada una es un paseo real. Euler lo descarta por laborioso y porque no se generaliza.

Su alternativa es describir un recorrido por la sucesión de letras de las zonas que visita. Un paseo que cruza siete puentes se escribe con ocho letras: la de partida y una más por cada puente.

El argumento, paso a paso

Llamemos A a Kneiphof, B y C a las orillas norte y sur, y D a la isla oriental, Lomse. A tiene cinco puentes y B, C y D tienen tres. Fíjate en que $5 + 3 + 3 + 3 = 14$, el doble de siete: cada puente tiene dos extremos, y al sumar los de todas las zonas se cuenta cada puente dos veces. Euler demostró esto en general, y de ahí que el número de zonas con puentes impares sea siempre par. Son, en la práctica, los dos primeros teoremas de la teoría de grafos.

Ahora, la clave. Cada vez que el paseante pasa por una zona sin ser ni su inicio ni su final, gasta dos puentes: uno para entrar y otro para salir. Si una zona tiene $k$ puentes y $k$ es impar, forzosamente el paseo empieza o acaba en ella, y la zona figurará $\frac{k+1}{2}$ veces en la sucesión de letras. En Königsberg las cuatro zonas son impares, así que cada una pide esas apariciones: 3 para A y 2 para cada una de B, C y D. Hacen falta

$$3 + 2 + 2 + 2 = 9$$

letras, pero un recorrido de siete puentes solo tiene ocho. Sobra una, y el paseo no puede existir.

La regla general

Euler dio un criterio para cualquier disposición de puentes. Con más de dos zonas impares, el recorrido es imposible; con exactamente dos, es posible empezando en una de ellas; y con ninguna, es posible desde cualquier zona. Lo ilustró con quince puentes y seis zonas, de las que solo D y E eran impares, y escribió una ruta completa: EaFbBcFdAeFfCgAhCiDkAmEnApBoElD.

Observó además que en Königsberg sí se puede cruzar cada puente exactamente dos veces, porque basta pensar cada puente como si estuviera partido en dos. Es fácil comprobarlo: con catorce, A tendría diez y B, C y D seis cada una, todas pares.

Un aviso contra confusiones frecuentes. El problema original pide cruzar cada puente una vez, sin exigir que se vuelva al punto de partida: es un camino euleriano. Si se exige además regresar al inicio, es un circuito euleriano y todas las zonas deben ser pares. Y nada de esto es el ciclo hamiltoniano, que visita cada zona una vez y es un problema muy distinto, y bastante más difícil.

Lo que Euler no demostró

Euler demostró con rigor que, con más de dos zonas impares, el recorrido es imposible. Para el recíproco, que si se cumple la condición el recorrido existe, dio un argumento convincente pero no una prueba formal. Tampoco menciona la conexión, es decir, que el mapa esté de una pieza, y la da por supuesta.

Según Grötschel y Yuan, hicieron falta unos 140 años. La prueba se debe a Carl Hierholzer (1840-1871), que se la expuso a unos amigos en 1871 y murió, con treinta años, antes de escribirla. Christian Wiener la reconstruyó de memoria con ayuda de Jacob Lüroth, y apareció en Mathematische Annalen en 1873.

Un artículo que tardó en brillar

Euler no volvió a este tema en su investigación, y su memoria tardó en recibir atención. Él mismo escribió a Ehler que este tipo de solución guarda poca relación con la matemática, porque se basa solo en el razonamiento. Un resultado que su autor veía así era el germen de un campo enorme, el de los grafos.

La versión de optimización, qué hacer cuando no hay recorrido perfecto y hay que repetir puentes al menor coste, la planteó Mei-Ko Kwan en 1960; más tarde Jack Edmonds la bautizó como problema del cartero chino. Euler no la abordó.

Qué fue de los puentes

En agosto de 1944 la RAF bombardeó Königsberg en dos incursiones, del 26 al 27 y del 29 al 30. Kneiphof quedó casi destruida y la catedral, reducida a un cascarón. Cuando entraron las tropas soviéticas, en abril de 1945, más del 90 % de la ciudad estaba en ruinas. La población alemana fue expulsada y la ciudad se reconstruyó como Kaliningrado.

Los puentes no desaparecieron del todo. El del Herrero (Schmiedebrücke, de Kneiphof a la orilla norte) y el de los Menudillos (Köttelbrücke, de Kneiphof a la orilla sur) no sobrevivieron a la guerra y no se reconstruyeron. Otros dos, el de los Tenderos (Krämerbrücke, hacia el norte) y el Verde (Grüne Brücke, hacia el sur), desaparecieron en los años setenta bajo el paso elevado de la avenida Leninski, que cruza Kneiphof de orilla a orilla. Sobreviven tres: el de la Miel (Honigbrücke), entre Kneiphof y Lomse; el de Madera (Holzbrücke), entre Lomse y la orilla norte, y el Alto (Hohe Brücke), entre Lomse y la orilla sur, que no es el original, porque se reconstruyó en los años treinta. Con los dos tramos del paso elevado, hoy hay cinco puentes en el esquema.

Con esos cinco puentes, dos zonas tienen tres y dos tienen dos. Hay exactamente dos zonas impares, luego existe un camino euleriano (lo garantiza el teorema de Euler y Hierholzer), pero debe empezar en una isla y terminar en la otra. Con K = Kneiphof, L = Lomse y N, S las orillas, los puentes son K-N y K-S (el paso elevado), K-L (la Miel), L-N (Madera) y L-S (el Alto), y el paseo K, N, L, S, K, L cruza los cinco una vez, sin volver al punto de partida.

Practica: calcula cuántas ordenaciones de los siete puentes hay con la calculadora de combinatoria.

Fuentes

• Martin Grötschel y Ya-xiang Yuan, Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman, Documenta Mathematica, Extra Volume ISMP, 2012.
• Janet Heine Barnett, Early Writings on Graph Theory: Euler Circuits and The Königsberg Bridge Problem (incluye la traducción de Biggs, Lloyd y Wilson del artículo de Euler), Colorado State University-Pueblo, 2005; copia alojada en la Universidad de Minnesota.
• Horst Sachs, Michael Stiebitz y Robin J. Wilson, An Historical Note: Euler’s Königsberg Letters, Journal of Graph Theory 12 (1), 1988, pp. 133-139.
• Leonhard Euler, Solutio problematis ad geometriam situs pertinentis (E53), The Euler Archive.
• Carl Hierholzer, Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, Mathematische Annalen 6, EuDML, 1873.
• Seven Bridges of Königsberg, Wikipedia.
• Bombing of Königsberg in World War II, Wikipedia.
• The Seven Bridges of Königsberg, In Your Pocket Kaliningrad.