Puentes de Konigsberg

El Team Mask les trae información acerca de unos puentes muy famosos, Los Puentes de Konigsberg que originaron un problema clásico pero no por ello falto de interés. Clásico porque es un problema muy conocido y estudiado; interesante porque está considerado como el comienzo de la topología, y, en particular, de la teoría de grafos.

Konigsberg (actualmente Kaliningrado, Rusia), era una ciudad de Prusia del siglo XVIII. El problema que nos ocupa tiene como protagonista a un río, el río Pregel, que cruzaba la ciudad, a dos islas que se encontraban en el mismo y a siete puentes que comunicaban las dos partes de la ciudad con las mismas. Concretamente la situación era como se describe en la imagen ( A y B son las dos partes de la ciudad y C y D las dos islas).

El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Antes de seguir leyendo podéis intentarlo vosotros mismos, aunque os recomiendo que no le dediquéis demasiado tiempo.

Análisis y solución del problema

El problema, formulado originalmente de manera informal, consistía en responder a la siguiente pregunta:

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. Sin embargo, Euler en 1736 en su publicación «Solutio problematis ad geometriam situs pertinentis» 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. Cada puente lo representó mediante una línea que unía a dos puntos, cada uno de los cuales representaba una región diferente. Así el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos azules, transite por todas las líneas una única vez, y regrese al mismo punto de partida.

Demostración

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. Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no podría existir más de un único punto conectado con un número impar de líneas.

En particular, como en este diagrama los cuatro puntos poseen un número impar de líneas incidentes (tres de ellos inciden en tres líneas, y el restante incide en cinco), entonces se concluye que es imposible definir un camino con las características buscadas.

Y así el Team Mask les ha traído información acerca de los orígenes de la Teoría de Grafos y de la Topología.

Anuncios

Publicado el 10 noviembre, 2011 en Archivos y etiquetado en , , , , , . Guarda el enlace permanente. 1 comentario.

  1. Este problema se lo aplique a un curso en mi colegio, uff se quebraron la cabeza y encontraban soluciones y cuando les decia q estaba mala empezaban a hacer de nuevo el problema excelente como Euler lo soluciona…

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

A %d blogueros les gusta esto: