Los puentes de Königsberg

Leyendo un post de Tirando Líneas me vino una duda que me resolvió Jacobo sin problemas. El tema me hizo recordar el problema de los puentes de Königsberg. Cuenta la leyenda que un ciudadano se propuso dar un paseo por todos los puentes del río Pregel sin pasar dos veces por el mismo. Los puentes tenían la siguiente disposición:

Durante años se fue extendiendo el rumor y la gente del pueblo se dedicaba a intentar dar un paseo sin cruzar dos veces por el mismo puente. Si intentáis hacer con papel y lápiz, equivale a dibujar una línea pasando por todos los puentes una sola vez. Nadie consiguió realizar tal proeza, y si no comprobadlo vosotros mismos 😉

Pero en 1736, el gran matemático suizo Leonard Euler publicó que era imposible dar tal paseo. Veamos como se puede demostrar matemáticamente. Podemos representar los puentes mediante lo que los matemáticos llaman Grafo. Veamos como se obtiene el grafo a partir de los puentes:

En el grafo las aristas representan los puentes y los vértices tierra firme. Si pensamos en como dibujar el grafo sin levantar el lápiz y sin pasar dos veces por la misma arista se ve que cada vez que «llegamos» a un vértice necesitamos una arista para «salir», es decir, que si a un vértice llegan 2 aristas podremos entrar por una y salir por la otra. Pero si un vértice tiene 3 aristas llegaremos por una, saldremos por otra, pero la siguiente vez al llegar ya no tendremos salida.

• Concluimos que todo los vértices del grafo deben de tener grado (Numero de aristas que inciden en el vértice) par para poderse dibujar sin levantar el lápiz empezando y terminando en el mismo punto.
• En el caso de haber dos vértices con grado impar también se puede solucionar el problema pero empezando y terminando en diferentes puntos.

El grafo de los puentes de Königsberg tiene los vértices A,C y D con grado impar, por lo que es imposible dar un paseo si pasar dos veces por el mismo puente.

Dibujad vuestros propios grafos con vértices de grado par y vértices de grado impar para hacer las pruebas. Un ejemplo típico y cotidiano es el de la casita con la cruz dentro en la cual todos los vértices tienen grado par. También podéis resolver fácilmente usando grafos el problema de Tio Petrus que acabo de encontrar. Ya es casualidad que hablemos de lo mismo 🙂