Los puentes de Königsberg

El problema de los puentes de Königsberg pregunta si se puede dar un paseo por la ciudad cruzando cada uno de sus siete puentes exactamente una vez. Leonhard Euler demostró en 1736 que no, y la manera en que lo demostró —olvidándose de la ciudad y quedándose solo con qué está conectado con qué— es el acta de nacimiento de la teoría de grafos, la rama de las matemáticas con la que hoy se describen las redes sociales, las rutas de internet, las cadenas de contagio y los mapas de carreteras.

Königsberg, hoy Kaliningrado, estaba partida por el río Pregel en cuatro trozos de tierra: la orilla norte, la orilla sur, la isla de Kneiphof en medio y la isla de Lomse al este, donde el río se bifurca. Siete puentes las unían: dos entre Kneiphof y cada orilla, uno entre Kneiphof y Lomse, y uno entre Lomse y cada orilla. Los vecinos se preguntaban desde hacía tiempo si existía un recorrido que pasara por los siete sin repetir ninguno, y en 1735 el alcalde de Danzig, Carl Ehler, se lo planteó por carta a Euler, que tenía entonces veintiocho años y trabajaba en la Academia de San Petersburgo. Euler respondió al principio que el problema «apenas tenía que ver con las matemáticas», pero lo resolvió, lo presentó ante la Academia el 26 de agosto de 1736 y lo publicó, con el título Solución de un problema relativo a la geometría de posición, en 1741.

Lo primero que hizo Euler fue tirar el mapa. Da igual la forma de las islas, la longitud de los puentes o por qué calle se vaya: lo único que cuenta es qué trozo de tierra está unido con cuál y por cuántos puentes. Llamó A, B, C y D a los cuatro trozos y describió un paseo como una secuencia de letras, una por cada vez que se pisa un trozo de tierra: cruzar siete puentes son ocho letras. Después contó. Cada vez que un paseo entra en un trozo de tierra y vuelve a salir gasta dos puentes; por eso un trozo con un número impar de puentes tiene que ser el principio o el final del paseo, porque el puente sobrante solo puede usarse para llegar o para irse. Y un paseo solo tiene un principio y un final. En Königsberg, los cuatro trozos de tierra tenían un número impar de puentes: cinco la isla de Kneiphof, tres cada uno de los otros. Cuatro candidatos a extremo para un paseo que solo tiene dos. Imposible, sin necesidad de probar recorridos.

La figura deja comprobarlo por la vía lenta: se puede cruzar cinco puentes con facilidad, seis con suerte, y el séptimo siempre queda al otro lado del río. Cuando uno se atasca, la lectura dice dónde y por qué, y la cuenta de grados —así se llama al número de aristas que tocan un vértice— muestra los cuatro impares. La condición de Euler no depende del mapa: cualquier grafo con más de dos vértices de grado impar es imposible de recorrer así. Con exactamente dos, si el recorrido existe tiene que empezar en uno y terminar en el otro; con ninguno, puede empezar en cualquier sitio y acabar donde empezó. Euler afirmó también el recíproco —que si hay como mucho dos vértices impares y el grafo está conectado, el paseo siempre existe—, pero lo dio por evidente y no lo demostró. Lo hizo Carl Hierholzer en 1873, en un artículo publicado tras su muerte y reconstruido de memoria por un colega, y su prueba es además un procedimiento para construir el recorrido, el que usan hoy los algoritmos que planifican rutas de reparto de correo o de recogida de basura, donde hay que pasar por todas las calles una vez.

La ciudad no se quedó quieta. En 1905 se construyó un octavo puente, el Kaiserbrücke, entre la isla de Lomse y la orilla sur, y con él los grados pasaron a ser tres, cinco, cuatro y cuatro: solo dos impares, así que el paseo por fin era posible, siempre que empezara en la orilla norte y terminara en Kneiphof, o al revés. El segundo botón de la figura permite encontrarlo. Los bombardeos de 1944 destruyeron dos de los puentes originales, otros dos fueron sustituidos después por una autovía, y el Kaiserbrücke se reconstruyó en 2005; el grafo de la Kaliningrado actual, con cinco puentes, tiene dos vértices impares y admite un paseo de Euler, aunque no un circuito que vuelva al inicio. El problema de los vecinos de 1735 se resolvió en dos ocasiones: una en el papel, en 1736, y otra en el terreno, en 1905.

El tercer botón, «tu propio grafo», es la parte que Euler no pudo ofrecer a sus lectores: seis vértices y quince aristas posibles que se encienden y se apagan pulsándolas. Sirve para comprobar que la regla de los grados no tiene excepciones —añadir una sola arista cambia la paridad de dos vértices a la vez, así que el número de vértices impares siempre es par— y para ver que la condición necesita también que el grafo esté conectado. Con eso, la pregunta de un paseo dominical se convierte en la primera pregunta de una disciplina: dado un conjunto de cosas y de conexiones entre ellas, qué se puede saber sin mirar las cosas y mirando solo las conexiones. El resto de este itinerario —el mundo pequeño, el umbral de Granovetter, la conexión preferencial, la epidemia en una red, el algoritmo de Dijkstra, PageRank— son respuestas a esa pregunta.