- Problema de los puentes de Königsberg
-
Problema de los puentes de Königsberg
Puentes de Königsberg.
El problema de los siete puentes de Königsberg es un célebre problema matemático que fue resuelto por Leonhard Euler en 1736 y dio origen a la teoría de los grafos. Königsberg es el antiguo nombre de la ciudad de Kaliningrado.
El problema consiste en lo siguiente:
Dos islas en el río Pregel que cruza Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?
Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos (nodo) que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo terminando en el punto de partida sin repetir las líneas?
Euler demostró que no era posible. La explicación es la siguiente: si un nodo tiene un número impar de líneas que inciden en él, necesariamente ha de ser el primer o último nodo del recorrido. Por lo tanto no se podrá encontrar una ruta que resuelva el problema si existen más de 2 nodos con número impar de líneas incidentes (ya que no puede haber más de un inicio y un final en una ruta continua). En el caso de los puentes de Kronisberg hay 4 nodos que tienen número de líneas incidentes impar, por lo que no se puede encontrar una solución al problema.
En teoría de los grafos esta idea se corresponde con la posibilidad de encontrar un Ciclo Euleriano en un grafo.
Mapa de Königsberg
Este mapa de Königsberg de la época de Euler muestra dónde se encontraban los siete puentes (en verde claro) y las ramas del río (en azul cielo).
Véase también
Enlaces externos
Wikimedia Commons alberga contenido multimedia sobre Problema de los puentes de Königsberg.- Puentes de Konigsberg: Interactivos.
- Mapas de Königsberg: Mapas de la época de Leonhard Euler y actuales.
- The Beginnings of Topology...: Página web sobre el problema matemático de los puentes de Königsberg
Categorías: Problemas matemáticos | Problemas computacionales | Teoría de grafos
Wikimedia foundation. 2010.
