Problema de los puentes de Königsberg

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?

Puentes Konigsberg.jpg

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?

Puentes Kronigsberg grafo.jpg

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

Konigsberg bridges.png

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

Commons

Obtenido de "Problema de los puentes de K%C3%B6nigsberg"

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Problema de los puentes de Königsberg — El problema de los siete puentes de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) fue resuelto por Leonhard Euler en 1736 y dio origen a la Teoría de los grafos. Consiste en lo siguiente: Dos islas en… …   Enciclopedia Universal

  • Königsberg — Bandera …   Wikipedia Español

  • Grafo — Para otros usos de este término, véase Grafo (desambiguación). Para la teoría en torno a este objeto matemático, véase Teoría de grafos. Grafo etiquetado con 6 vértices y 7 aristas. En matemáticas y ciencias de la computación, un grafo (del …   Wikipedia Español

  • Leonhard Euler — Retrato de Leonhard Euler, pintado por Johann Georg Bruck …   Wikipedia Español

  • Ciclo euleriano — Un ciclo euleriano es aquel camino que recorre todas las aristas de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde… …   Wikipedia Español

  • Kaliningrado — Калининград Kaliningrado Bandera …   Wikipedia Español

  • Topología — Para otros usos de este término, véase Topología (desambiguación). Ilustración del Teor …   Wikipedia Español

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

  • Wikipedia:Artículos buenos —   Artículos buenos   ¿Qué es un artículo bueno?   …   Wikipedia Español

  • Anexo:Episodios de Numb3rs — La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada (2005 2006) …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”