Problema dels ponts de Königsberg

Plantilla:Coord/display/title</noinclude>

Archiu:Konigsberg bridges.png

Mapa de Königsberg en l'época de Leonhard Euler, que mostra on es trobaven els sèt ponts (en vert clar) i les branques del riu (en celest).

El problema dels ponts de Königsberg, també cridat més específicament problema dels sèt ponts de Königsberg, és un célebre problema matemàtic resolt per Leonhard Euler en 1736 i la resolució del qual va donar orige a la teoria de grafos. El seu nom es deu a Königsberg, la ciutat de Prusia Oriental i després d'Alemània que des de 1945 es va convertir en la ciutat russa de Kaliningrado.

Esta ciutat està travessada pel riu Pregolia. Este es bifurca i rodeja en els seus braços a l'illa Kneiphof, de manera que el terreny queda dividit en quatre regions distintes, que llavors estaven unides per mig de sèt ponts cridats pont del ferrer, Pont Conector, Pont Vert, Pont del Mercat, Pont de Fusta, Pont Alt i Pont de la Mel. El problema es va formular en el XVIII i consistia en trobar un recorregut per a creuar a peu tota la ciutat passant solament una volta per cada u dels ponts i retornant al mateix punt d'inici.

Contextualización del problema

Leonhard Euler va aplegar a Prusia en 1741, a l'edat de 34 anys, a on va viure fins a 1766 i després va retornar a San Petersburgo. Durant eixos anys va treballar en l'Acadèmia Prusiana de les Ciències, a on va desenrollar una prolífica carrera com a investigador. Euler va ser contemporàneu de varis atres famosos matemàtics i pensadors procedents d'aquella ciutat, com Immanuel Kant, Johann Georg Hamann i Christian Goldbach, per lo que Königsberg va ser en eixe temps un important centre científic.

Va ser aixina com va sorgir la formulació del problema dels ponts de Königsberg, que es va propagar a modo de joc i de problema matemàtic entre els intelectuals de l'época.

Anàlisis i solució del problema

Archiu:Leonhard Euler.jpg

Leonhard Euler (1707-1783), famós matemàtic que va resoldre el problema en 1736, donant orige a la teoria de grafos. Retrat de 1753.

El problema, formulat originalment de manera informal, consistia en respondre a la següent pregunta:

Donat el mapa de Königsberg, en el riu Pregel dividint el pla en quatre regions distintes, que estan unides a través dels sèt ponts, ¿és possible donar una passejada començant des de qualsevol d'estes regions, passant per tots els ponts, recorrent solament una volta cada u, i retornant al mateix punt de partida?

La resposta és negativa, és dir, no existix una ruta en estes característiques. El problema pot resoldre's aplicant un método de força bruta, lo que implica provar tots els possibles recorreguts existents. No obstant, Euler, en 1736, en la seua publicació «Solutio problematis ad geometriam situs pertinentis», demostra una solució generalisada del problema, que pot aplicar-se a qualsevol territori en el que certs accessos estiguen restringits a certes conexions, com el dels ponts de Königsberg.

Per a dita demostració, Euler recorre a una abstracció del mapa i s'enfoca exclusivament en les regions terrestres i les conexions entre elles. Cada pont va quedar representat per mig d'una llínea que unia a dos punts, i cada u d'estos punts representava una regió diferent. Aixina, el problema es reduïx a decidir si existix o no un camí que comence per un dels punts, recórrega totes les llínees una sola volta i retorne al mateix punt de partida.

Archiu:Konigsberg bridges.png → Archiu:7 bridges.svg → Archiu:Königsberg graph.svg

Solució de Euler

Euler va determinar, en el context del problema, que els punts intermijos d'un recorregut possible necessàriament han d'estar conectats a un número par de llínees. En efecte, si apleguem a un punt des d'alguna llínea, llavors l'únic modo d'eixir d'eixe punt és per una llínea diferent. Açò significa que tant el punt inicial com el final serien els únics que podrien estar conectats en un número impar de llínees. No obstant, el requisit adicional del problema diu que el punt inicial deu ser igual al final, per lo que no podria existir cap punt conectat en un número impar de llínees.

En particular, com es veu en este diagrama, els quatre punts tenen un número impar de llínees (tres d'ells tenen tres llínees i el restant té cinc). Per lo tant, es conclou que és impossible definir un camí en les característiques buscades que són els sèt ponts de Königsberg.

Vore també

• Cicle euleriano
• Teoria de grafos