Problema das pontes de Königsberg

Na Galipedia, a Wikipedia en galego.
Saltar ata a navegación Saltar á procura
Mapa de Königsberg na época de Leonhard Euler, que mostra onde se atopaban as sete pontes (en verde claro) e as ramas do río (en celeste).

O problema das pontes de Königsberg, tamén chamado máis especificamente problema das sete pontes de Königsberg, é un soado problema matemático, resolto por Leonhard Euler en 1736 e cuxa resolución deu orixe á teoría de grafos.[1] O seu nome débese a Königsberg, a cidade de Prusia Oriental e logo de Alemaña que en 1945 se converteu na cidade rusa de Kaliningrado.

Esta cidade está atravesada polo río Pregel (en ruso Pregolya) que se bifurca para rodear cos seus brazos a illa Kneiphof,[2] dividindo o terreo en catro rexións distintas, que entón estaban unidas mediante sete pontes chamadas Ponte do ferreiro, Ponte conectora, Ponte verde, Ponte do mercado, Ponte de madeira, Ponte alta e Ponte do mel.[3] O problema foi formulado no século XVIII e consistía en atopar un percorrido para cruzar a pé toda a cidade, pasando só unha vez por cada unha das pontes, e regresando ao mesmo punto de inicio.[4]

Contexto[editar | editar a fonte]

Leonhard Euler chegou a Prusia en 1741, á idade de 34 anos, onde viviu até 1766 para logo regresar a San Petersburgo. Durante eses anos traballou na Academia Prusiana das Ciencias, onde desenvolveu unha prolífica carreira como investigador.[5] Euler foi contemporáneo de varios outros famosos matemáticos e pensadores procedentes daquela cidade, tales como Immanuel Kant, Johann Georg Hamann e Christian Goldbach, polo que Königsberg foi nese tempo un importante epicentro científico.

Foi así como xurdiu a formulación do problema das pontes de Königsberg, propagándose a modo de xogo matemático entre os intelectuais da época.

Análise e solución[editar | editar a fonte]

Leonhard Euler (1707 - 1783), matemático que resolveu o problema en 1736, dando orixe á teoría de grafos. Retrato de 1753.

O problema, formulado orixinalmente de maneira informal, consistía en responder a seguinte pregunta:

A resposta é negativa, é dicir, non existe unha ruta con estas características. O problema pode resolverse aplicando un método de forza bruta, o que implica probar todos os posibles percorridos existentes. Con todo, Euler en 1736 na súa publicación Solutio problematis ad geometriam situs pertinentis demostrou unha solución xeneralizada do problema, que pode aplicarse a calquera territorio en que certos accesos estean restrinxidos a certas conexións, tales como as pontes de Königsberg.

Para dita demostración, Euler recorreu a unha abstracción do mapa, enfocándose exclusivamente nas rexións terrestres e as conexións entre elas. Representou cada ponte mediante unha liña que unía dous puntos, cada un dos cales representaba unha rexión diferente. Así, o problema redúcese a decidir se existe ou non un camiño que comece por un dos puntos azuis, transite por todas as liñas unha única vez, e regrese ao mesmo punto de partida.

Konigsberg bridges.png7 bridges.svgKönigsberg graph.svg

Solución de Euler[editar | editar a fonte]

Euler determinou, no contexto do problema, que os puntos intermedios dun percorrido posible necesariamente han estar conectados a un número par de liñas. En efecto, se se chega a un punto dende algunha liña, entón o único modo de saír dese punto é por unha liña diferente. Isto significa que tanto o punto inicial como o final serían os únicos que poderían estar conectados cun número impar de liñas. Con todo, o requisito adicional do problema di que o punto inicial debe ser igual ao final, polo que non podería existir ningún punto conectado cun número impar de liñas.[6]

En particular, como neste diagrama os catro puntos posúen un número impar de liñas incidentes (tres deles inciden en tres liñas, e o restante incide en cinco), entón conclúese que é imposible definir un camiño coas características buscadas que son as sete pontes de Königsberg.

Repercusións[editar | editar a fonte]

Esta abstracción do problema ideada por Euler deu pé á primeira noción de grafo, que é un tipo de estrutura de datos utilizada amplamente en matemática discreta e en ciencias da computación. Aos puntos chámaselles vértices e ás liñas arestas. Ao número de arestas incidentes a un vértice chámaselle grao de devandito vértice. Especificamente, un diagrama como o da abstracción do mapa de Königsberg representa un multigrafo non dirixido sen bucles.

Na teoría de grafos, existe un concepto chamado ciclo euleriano, chamado así xustamente en honra a Leonhard Euler, que representa calquera camiño dentro dun grafo particular, capaz de percorrer todas as arestas unha única vez, regresando finalmente ao mesmo vértice orixinal. En coloración de grafos, unha subárea da teoría de grafos, a resolución deste problema constitúe ademais o primeiro teorema dos grafos planares.[7]

Por outra banda, a publicación de Euler é a primeira que fai alusión a unha xeometría en que só interesan as propiedades estruturais dos obxectos, e non as súas medidas, como tradicionalmente se fai. O matemático chama a esta nova maneira de ver os obxectos xeométricos geometriam situs, expresión que hoxe se traduce como topoloxía, cuxa orixe directa pode situarse na resolución deste problema.[8]

O problema na actualidade[editar | editar a fonte]

Ponte do Mel sobre o río Pregolya en Kaliningrado.

Dúas das sete pontes orixinais foron destruídas polo bombardeo de Königsberg durante a segunda guerra mundial. Outras dúas foron posteriormente demolidas e substituídas por estradas modernas. As tres pontes restantes aínda permanecen en pé, aínda que só dúas delas dende a época de Euler, pois unha foi reconstruída en 1935.[9]

Polo tanto, na actualidade só existen cinco pontes en Kaliningrado, distribuídas de tal xeito que é posible definir un camiño euleriano, é dicir, unha ruta que comeza nunha illa e termina noutra; pero non un ciclo euleriano, é dicir, que a ruta comece e termine no mesmo lugar, o cal era necesario para cumprir coas condicións iniciais do problema.[10]

Notas[editar | editar a fonte]

  1. "Solutio problematis ad geometriam situs pertinentis" (PDF). Reimpreso en Opera Omnia Series Prima, Vol. 7. pp. 1-10, 1766. 
  2. Astrocosmo (2001-2002). "El Problema de los Puentes de Königsberg" (en castelán). Arquivado dende o orixinal o 06 de xaneiro de 2010. Consultado o 28 de abril de 2010. 
  3. MathDL. "Leonard Euler's Solution to the Konigsberg Bridge Problem" (en inglés). Arquivado dende o orixinal o 22 de maio de 2011. Consultado o 11 de abril de 2010. 
  4. Königsberg Bridge Problem (en inglés)
  5. Dunham, William (1999). Euler: The Master of Us All. The Mathematical Association of America. pp. xxiv–xxv. 
  6. En realidade, nestes percorridos, chamados ciclos eulerianos, non poden existir puntos cun número impar de liñas incidentes. Só no caso dos camiños eulerianos, onde se acepta que o punto inicial e o final sexan distintos, pode darse que unicamente estes teñan un número impar de liñas incidentes. Euler só caracterizou formalmente os camiños eulerianos; a caracterización formal de ciclo euleriano fíxoa Carl Hierholzer máis tarde, en 1873, o que non impide que a demostración de Euler sexa xeral e correcta.
  7. Alexanderson, Gerald (xullo de 2006). "Euler and Königsberg's bridges: a historical view". Bulletin of the American Mathematical Society. 
  8. Pappas, T. "Königsberg Bridge Problem & Topology." The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 124-125, 1989.
  9. Taylor, Peter (decembro de 2000). Australian Mathematics Trust, ed. "What Ever Happened to Those Bridges?". Arquivado dende o orixinal o 19 de marzo de 2012. Consultado o 12 de abril de 2010. 
  10. Stallmann, Matthias (xullo de 2006). "The 7/5 Bridges of Koenigsberg/Kaliningrad". Consultado o 12 de abril de 2010. 

Véxase tamén[editar | editar a fonte]

Bibliografía[editar | editar a fonte]

  • Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976). Graph Theory 1736-1936 (en inglés). Oxford: Clarendon Press. p. 239. 

Outros artigos[editar | editar a fonte]

Ligazóns externas[editar | editar a fonte]