Els set ponts de Königsberg

De Viquipèdia

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

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 Pregolya. Enmig del riu, dues grans illes estaven connectades entre elles i a les voreres mitjançant una estructura de set ponts en total.

Per tal d'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.

[edita] Solució d'Euler

El 1736, el matemàtic suís Leonhard Euler va demostrar que no era possible en Solutio problematis ad geometriam situs pertinentis. 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: substituïnt 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 s'anomena avui en dia 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 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.