Embedded Files
La ciudad de Kaliningrado, antiguamente llamada Königsberg, es lugar situado en la desembocadura del río Pregolya, en la antigua Prusia Oriental. Su río atraviesa la ciudad, dividiendo la zona en varias partes. Para no perder la comunicación, ésta tenía un sistema de 7 puentes conectores. Aquí nace el problema sobre si es posible atravesar todos los puentes pasando por cada uno solamente una vez. El famoso matemático Euler entregó la respuesta.
¿Se pueden atravesar todos los puentes pasando sólo una vez por cada uno?
Extracto de letra
«La teoría de grafos
nació ese mismo día.
Los caminos y trayectos
ya son parte y poesía.»
Euler mostró que en el grafo asociado basta con identificar los vértices de grado impar, aquellos donde llegan impares aristas, verificando que no existan más de dos para poder cruzarlos. En este caso no podemos.
La idea de Euler yace en la observación de que cada zona de tierra aislada y cada puente pueden ser representados con un vértice y una arista respectivamente, generando lo que se conoce como grafo. Un grafo es simplemente una figura formada por vértices y aristas.
Euler se dio cuenta de que al viajar por los puentes en los vértices intermedios sólo se verán conectadas pares aristas, dado que no se puede volver por el mismo puente. Es decir no pueden existir más de dos vértices al cual le lleguen impares aristas (llamados de grado impar)
En este grafo hay 4 vértices de grado impar. Luego no se puede realizar lo establecido en la pregunta.
Después de la segunda guerra mundial han quedado sólo 5 puentes y actualmente si se pueden recorrer los puentes pasando sólo una vez por cada uno. La ciudad de Valdivia en Chile también es una ciudad de puentes, similar a Könisberg.
El problema de los puentes en Valdivia:
El problema de los puentes en Valdivia:
¿Qué ocurre si planteamos el problema de los puentes en Valdivia?
El grafo asociado es:
Aquí hay 4 vértices de grado impar. Luego no se puede realizar lo establecido en la pregunta. Sin embargo, está proyectado un nuevo puente (Puente Cochrane) que dejaría a Valdivia con 6 puentes. En esta nueva situación el nuevo grafo asociado tendría dos vértices de grado impar que permitiría recorrer los 6 puentes pasando sólo una vez por cada uno.
Page updated
Google Sites
Report abuse