Els set ponts de Königsberg

Els set ponts de Königsberg és un famós problema matemàtic que va donar origen a la teoria de grafs. Königsberg, l'actual Kaliningrad, és una ciutat russa (que fou alemanya fins a la fi de la II Guerra Mundial) per la qual passa el riu Pregel. Enmig del riu, dues grans illes estaven connectades entre elles i a les ribes mitjançant una estructura de set ponts en total.

Mapa de Königsberg mostrant la disposició dels set ponts sobre el riu Pregolya.

Per a organitzar una desfilada, els habitants de la ciutat es van plantejar si era possible recórrer els set ponts de manera que només es passés per cadascun d'ells un sol cop.

Solució d'Euler

Article principal: Teoria de grafs de Leonhard Euler

El 1736, el matemàtic suís Leonhard Euler va demostrar que no era possible en Solutio problematis ad geometriam situs pertinentis.^[1] En la història de les matemàtiques, es considera que aquest problema és el que va donar origen a la teoria de grafs, el desenvolupament de la qual va permetre grans avenços en combinatòria i topologia.

Euler va trobar la solució fent abstracció dels elements rellevants en el problema: substituint les illes i riberes per punts (vèrtexs, nodes), i els ponts per camins (branques) que els enllaçaven. El resultat conforma l'estructura que, avui en dia, s'anomena graf.

→ →

Euler va adonar-se que el problema podia ser resolt en funció del grau dels nodes. En el problema dels set ponts, tres nodes tenen grau 3, i un té grau 5. Euler va provar que el circuit que es desitjava era possible si i només si hi havia exactament dos nodes o no cap de grau senar (imparell). Un camí d'aquest tipus s'anomena camí eulerià. A més, si dos nodes tenen grau senar, aquests han de ser el punt d'inici i final del camí eulerià. Per tant, com que el graf corresponent als ponts de Königsberg té quatre nodes de grau senar, no pot tenir un camí eulerià.

Una forma alternativa del problema demana un camí que passi per tots els ponts i també tingui el mateix punt d'inici i final. Un circuit d'aquesta mena s'anomena un circuit eulerià. Existeix un circuit eulerià si i només si no hi ha nodes de grau senar. Es pot veure que tots els circuits eulerians són també camins eulerians.

Referències

1. Euler, Leonhard «Solutio problematis ad geometriam situs pertinentis». Commentarii academiae scientiarum Petropolitanae, 8, 1741, pàg. 128-140.

Enllaços externs

• (castellà) Puentes de Konigsberg Arxivat 2013-11-13 a Wayback Machine.: Interactius.
• Mapes de Königsberg: Mapes de l'època de Leonhard Euler i actuals.
• (anglès) The Beginnings of Topology...: Web dedicada al problema dels ponts de Königsberg.