Problema das pontes de Königsberg

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]

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.

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.

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.

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]

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]

Wikimedia Commons ten máis contidos multimedia na categoría:  Problema das pontes de Königsberg

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

• Ciclo euleriano
• Teoría de grafos
• Problema do viaxeiro

• Sitio interactivo.