L'any 1254 l'Orde dels Cavallers Teutons va fundar la ciutat de Königsberg, que literalment es tradueix com "La muntanya del rei". Degut a la seva bona posició estratègica sobre el riu Pregel, va esdevenir un punt d'intercanvi i important ciutat medieval. El riu dividia la ciutat en 4 regions connectades per 7 ponts: el Pont de Blacksmith, el Pont Enllaç, el Pont Alt, el Pont Verd, el Pont de Mel, el Pont del Comerciant i el Pont de Llana.
Mapa de Königsberg al segle XVII
Es diu que els habitants de Königsberg passaven les tardes de Diumenge passejant per la ciutat. El problema que els mateixos ciutadants es van plantejar és si era possible creuar exactament una vegada per tots i cada un dels ponts.
El 1727 Leonhard Euler treballava per l'Acadèmia de Ciències de Sant Petersburg. El 1736 Euler va escriure la solució en un article amb el títol 'Solutio problematis ad geometriam situs pertinentis'
Tot i que no està clar com Euler va arribar a conéixer aquest problema, s'han trobat un seguit de cartes que s'escrivia amb Carl Leonhard Gottlieb Ehler, alcalde de Danzig, a 80 milles de Königsberg, on es parlava d'aquest problema.
El mateix Euler, en una carta a un matemàtic italià, el 13 de Març de 1736, escriu:
M'han proposat un problema sobre l'illa de la ciutat de Königsberg, envoltada per un riu travessat per 7 ponts, i se m'ha plantejat si algú podia travessar els ponts en un camí que els enllaci de tal manera que cada pont només sigui creuat una vegada.
Diagrama del problema dels ponts de Königsberg de l'article de Euler de 1736
Euler, en la mateixa carta, considera que la qüestió és "banal", però la considera d'interés pel fet que no es pot resoldre ni amb geometria, ni algebra ni amb l'art de comptar. Associa el problema a la geometria de posició, introduïda per Leibniz recentment.
En l'article de 1736 Euler descriu el problema, resol el cas particular de Königsberg i finalment, generalitza el problema. Euler es pregunta:
Sigui quina sigui la distribució i divisió del riu en branques i el número de ponts que el trevessen, es pot saber si és possible creuar tots els ponts exactament una vegada?
Tot i que es pot anar provant totes les possibilitats, Euler ho descarta, ja que seria pesat de fer i impossible si hi hagués més ponts i illes.
Euler usa les lletres en majúscula A, B, C i D per referir-se a les illes i les lletres en minúscula a, b, c, d, e, f i g per referir-se als ponts. Si un caminant va des de A a B pel pont a o b, ho escriu AB - on la primera lletra representa la regió d'on surt el caminant i la segona lletra, la regió cap a on es dirigeix.
D'aquesta manera, si un camí consta de n lletres, per tal que tingui solució, cal que estigui unit per n-1 ponts. En el cas dels ponts de Königsberg, el problema té 7 ponts i, per tant, requereix d'un camí de 8 lletres (que es poden repetir).
Quina és la relació entre el número de ponts que uneixen dues regions amb el número de lletres corresponents a aquest camí? Mirem l'exemple senzill proposat per Euler:
Cas senzill unint 2 zones per 6 ponts (número parell)
En el cas anterior la seqüència començant per A és:
AaBbAcBdAeBfA
o bé, ometent els ponts:
AB-BA-AB-BA-AB-BA
Euler dedueix que si el nombre de ponts és imparell, aleshores el nombre de lletres A que hi ha d’haver a la seqüència seria la meitat d’aquest nombre de ponts més un i si el nombre de ponts és parell és directament la meitat.
Amb això és suficient per determinar la impossibilitat del camí buscat. Una de les illes, A, està connectada per 5 ponts; per tant, el camí ha de contenir 3 lletres A. De manera similar, ha d'haver 2 lletres B, 2 lletres C i 2 lletres C.
Diagrama del problema dels ponts de Königsberg de l'article de Euler de 1736
Regió
A
B
C
D
Ponts
5
3
3
3
Freqüència
3
2
2
2
Sumant la fila de freqüències de totes les lletres, que representen les repeticions de cada lletra en el camí, veiem que faria falta 9 lletres, però el camí usant 7 ponts només en necessita 8. Per tant, no existeix el camí que busquem.
Generalitzant, la freqüència de cada lletra depenent del nombre de ponts, si aquest és imparell és . Si és parell és o si comença per aquesta regió.
Podem escriure la taula de freqüències en aquest cas, marcant amb un asterisc les illes amb un nombre senar de ponts
Un exemple més complicat: 2 illes, 4 rius i 15 ponts
Regió
A
B
C
D*
E*
F
Ponts
8
4
4
3
5
6
Freqüència
4
2
2
2
3
3
Si la suma de freqüències és el nombre de lletres necessaries menys u, donat el nombre de ponts, el camí que busquem existirà. En aquest cas, la fila de freqüències suma 16, que és exactament el nombre de lletres necessaries per un camí amb 15 ponts, tal com és. Euler va mostrar un possible camí:
Aquest tipus de problemes es poden resoldre molt més fàcilment si ho representem en forma de graf, tal com es va començar a fer a partir del segle XIX. L'objectiu és determinar si una figura es pot dibuixar sense aixecar el llapis i sense repetir cap aresta (Camí Eulerià). Podem transformar els dibuixos que hem vist en grafs:
Graf del problema dels ponts de KönigsbergGraf del problema ampliat proposat i solucionat per Euler
Si hi ha més de dos nodes amb grau senar, aleshores el camí Eulerià no és possible
Si hi ha exactament dos nodes amb grau senar, aleshores el camí Eulerià existeix si comença en un dels dos nodes
Si no hi ha cap node amb grau senar, el camí Eulerià existeix començant per qualsevol node.
\[n_{44}=3\]
D → g → g → D D → e → e → D D → f → f → D
Com trobem el número de camins?
Per trobar el número de camins que surten de C i arriben a D buscarem quants ponts surten de C i arriben a una altra illa que està també connectada al punt final, D. Veurem com multipliquem totes les possibilitats.
Si elevem al cub la matriu d'adjacència obtindrem els camins de longitud 3 entre dos nodes. Els termes de la diagonal representen quants triangles es poden recórrer començant i acabant per un dels nodes.
Si sumem els elements de la diagonal obtindrem 6 vegades el nombre de triangles totals. Hem comptat dues vegades els triangles degut als dos possibles sentits (horari i anti-horari) i 3 vegades més ja que hem comptat un triangle per cada node (3 nodes en un triangle)
Camins de + passos
Podem seguir el mateix procediment per calcular el nombre de camins de longituds diferents d'una illa a una altra. L'element \[A^l_{ij}\] ens diu quants camins de longitud l entre els nodes i i j hi ha. Cal tenir en compte que s'inclouen els camins que repeteixen arestes i camins en les dues direccions.