Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Problema de los puentes de Konigsberg

No description
by

Sergio Lugo Gutiérrez

on 22 November 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Problema de los puentes de Konigsberg

Puentes De Konigsberg Solucion El problema El problema de los siete puentes de Königsberg, es un célebre problema matemático, resuelto por Leonhard Euler en 1736 y cuya resolución dio origen a la teoría de grafos Su nombre se debe a Königsberg, el antiguo nombre que recibía la ciudad rusa de Kaliningrado Esta ciudad es atravesada por el río Pregolya, el cual se bifurca para rodear con sus brazos a la isla Kneiphof, dividiendo el terreno en cuatro
regiones distintas... ...las que entonces estaban unidas mediante siete puentes llamados Puente del herrero, Puente conector, Puente verde, Puente del mercado, Puente de madera, Puente alto y Puente de la miel. Dado el mapa de Königsberg, con el río Pregolya dividiendo el plano en cuatro regiones distintas, que están unidas a través de los siete puentes, ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo sólo una vez cada uno, y regresando al mismo punto de partida? La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes. Euler en 1736 en su publicación demuestra una solución generalizada del problema, que puede aplicarse a cualquier territorio en que ciertos accesos estén restringidos a ciertas conexiones, tales como los puentes de Königsberg. Para dicha demostración, Euler recurre a una abstracción del mapa, enfocándose exclusivamente en las regiones terrestres y las conexiones entre ellas. Demostracion Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible necesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto inicial
como el final serían los únicos
que podrían estar conectados
con un número impar de líneas. Esta abstracción del problema ideada
por Euler dio pie a la primera noción de grafo,
que es un tipo de estructura de datos
utilizada ampliamente en matemática
discreta y en ciencias de la computación. En la teoría de grafos, existe un concepto llamado ciclo euleriano, llamado así justamente en honor a Leonhard Euler, que representa cualquier camino dentro de un grafo particular, capaz de recorrer todas las aristas una única vez, regresando finalmente al mismo vértice original. Sin embargo,
Full transcript