Formalización del problema
La teoría de gráficas
El matemático suizo Leonard Euler se interesó en el problema de los puentes de Königsberg, y en 1736 presentó un trabajo en la Academia de Ciencias de San Petersburgo en el que daba una solución. Para resolver el problema Euler utilizó un esquema con puntos y líneas. Usó puntos para representar los lechos del río y las islas, marcados con las letras A, B, C y D; los siete puentes los representó mediante líneas.

La obra de Euler es considerada como el comienzo de la teoría de gráficas, que forma parte de la topología. El esquema anterior es llamado gráfica (o grafo), los puntos se llaman vértices (o nodos) y las líneas se llaman aristas (o lados).
En el siguiente espacio interactivo podrás explorar nuevamente diversos caminos para recorrer los puentes, pero esta vez hazlo uniendo los puntos como se muestra en la gráfica de Euler. Puedes cambiar el número de puentes, de manera que explorarás recorridos como los de la sección anterior, pero esta vez, al hacerlo, estarás trazando las aristas de una gráfica cuyos vértices son los puntos A, B, C y D.
A continuación se muestra un recorrido tal como lo pudiste haber trazado para (tratar de) reproducir la gráfica propuesta por Euler.

Como habrás notado, los recorridos que has trazado forman gráficas. Algunas de estas gráficas inician en el mismo punto, mientras que otras tienen un punto final distinto al punto de inicio.
El problema de los puentes de Königsberg se reduce a dibujar la gráfica que usó Euler partiendo de un punto con un único trazo, es decir, sin despegar el lápiz del papel (o, en este caso, sin dejar de pulsar sobre el cursor), y sin recorrer la misma línea dos veces.
A un recorrido con estas características se le llama camino euleriano. Cuando el punto de inicio y el punto final coinciden, el recorrido es un ciclo euleriano.