Ciudades con puentes
El comienzo de la teoría de
grafos se inicia con la discusión de un pasatiempo, el llamado problema de
los puentes de Königsber: La ciudad de Königsber, en Prusia Oriental, está
situada a las orillas del río Pregel.
Las diversas partes de la ciudad se conectan entre sí por medio de siete
puentes. Cuentan que en la época de Euler, los habitantes de la ciudad
acostumbraban a pasear por la ciudad de tal manera que, partiendo de una casa,
pudieran regresar a ella habiendo pasado por todos los puentes una sola vez.
Piensa qué características
tiene este problema. ¿Hay aspectos irrelevantes? ¿Interesa la longitud de los
puentes? ¿Es necesario considerar el tamaño de la ciudad, del río? ¿Hasta donde podemos
simplificar-esquematizar el problema anterior? Tenemos
así el siguiente diagrama topológico o grafo que reúne toda la información
necesaria para resolver la cuestión.
El problema
inicial puede plantearse ahora en los siguientes términos: ¿Es posible recorrer
el grafo anterior sin levantar el lápiz del papel comenzando y terminando en el
mismo punto, sin pasar dos veces por algún camino?
** Haz un grafo
de las ciudades de Cuenca y San Petersburgo y estudia cómo puedes pasear por
ellas pasando por todos sus puentes una sola vez
No hay comentarios:
Publicar un comentario