Page 12 - Encantador

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. 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.

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:
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.