Els ponts de Königsberg

Traducción realizada por Mauri, traductor técnico Castellano – Catalán y colaborador de la agencia Ibidem Group.

Texto original escrito por Philip J. Erdelsky y publicado en
http://www.efgh.com/math/koenigsberg.htm

***

Un dels problemes clàssics de les matemàtiques es el dels Ponts de Königsberg, que va ser resolt al segle XVIII pel matemàtic suís Leonhard Euler. És fàcil d’plantejar i bastant fàcil de resoldre.

Un riu passa per la ciutat de Königsberg (actual Kalingrad). Al riu hi ha dues illes. Set ponts connectaven les illes i els bancs, tal com es mostra en aquest antic mapa:

Els dos canals fluvials s’ajunten en algun lloc del costat dret del mapa.

Molta gent va intentar caminar per Königsberg, creuant cada pont una vegada i només una vegada, però ningú va poder fer-ho. Euler va demostrar que la tasca és impossible. La seva demostració requereix només uns coneixements bàsics d’aritmètica i de les propietats dels nombres parells i senars.

La brillant visió d’Euler, si es pot anomenar així, va ser comptar el nombre d’extrems de pont connectats a cada tros de terra:

• 3 a la riba nord
• 3 a la riba sud
• 5 a l’illa al centre del mapa
• 3 a l’illa del costat dret del mapa

Un passeig que travessa cada pont una vegada i només una vegada s’anomena, prou adequadament, passeig d’Euler (o camí d’Euler).

Si una caminada d’Euler no comença o acaba en un tros de terra en concret, llavors hi ha d’haver un NOMBRE PARELL de ponts connectats a ella, perquè un caminant d’Euler que entra a la zona per un pont l’ha de sortir per un altre. Si una caminada d’Euler comença o acaba en un tros de terra en particular, aleshores el nombre de ponts connectats ha de ser PAR.

Com que cadascun dels quatre trossos de terra té un nombre imparell de ponts connectats, és obvi que un passeig d’Euler és impossible.

Els ponts de Königsberg són un exemple d’estructura matemàtica general anomenada gràfic .

Un gràfic consta d’un nombre finit de vèrtexs (també anomenats nodes), corresponents als trossos de terra dels Ponts de Königsberg, i d’un nombre finit d’arestes (també anomenades línies), corresponents als ponts. Els seguirem anomenant ponts. Així mateix, per evitar dificultats amb caminades inexistents, cal que hi hagi almenys un vèrtex.

Aquí hi ha una representació més abstracta del gràfic de Königsberg:

Un gràfic pot ser més general que els ponts de Königsberg. Per exemple, un pont pot connectar un vèrtex a si mateix i no cal que els vèrtexs estiguin confinats a un sol pla. També és possible un vèrtex aïllat, sense ponts de connexió.

El nombre de ponts que connecten un vèrtex concret s’anomena grau (o valència).

Els arguments d’Euler van mostrar que un passeig d’Euler només és possible si (1) tots els vèrtexs són de grau parell, en aquest cas el passeig comença i acaba al mateix vèrtex, o (2) dos vèrtexs, on comença i acaba el passeig, són de grau senar i tots els altres vèrtexs són de grau parell.

Dues propietats dels camins d’Euler són òbvies. El revers d’una caminada d’Euler és una caminada d’Euler, i si una caminada d’Euler comença i acaba en el mateix vèrtex, també es pot començar i acabar en qualsevol altre vèrtex.

Aquestes condicions també són suficients? Evidentment que no. El gràfic també ha d’estar connectat, és a dir, hi ha d’haver algun camí (no necessàriament un camí d’Euler) des de cada vèrtex fins a tots els altres.

Demostrar l’existència d’una caminada d’Euler per a un graf connectat sense vèrtexs de grau senar o dos vèrtexs de grau senar és una mica més difícil, però no implica cap matemàtica avançada.

Primer, considereu un gràfic connectat on tots els vèrtexs són de grau parell. Comenceu a caminar per un vèrtex, fent un seguiment dels ponts que heu creuat. Cada vegada que entres en un vèrtex, deixa’l per un pont que no hagis creuat anteriorment. Si no és el vèrtex inicial, aleshores si heu entrat per un pont sense creuar, sempre el podeu sortir per un altre. I després de marxar, el vèrtex encara té un nombre parell de ponts no creuats.

La caminada s’ha d’acabar quan torneu al vèrtex d’inici i no trobeu cap pont sense creuar per deixar-lo.

Si heu aconseguit travessar tots els ponts, la caminada està acabada.

Si encara hi ha almenys un pont sense creuar, s’ha d’augmentar el passeig.

Observeu, però, que cada vèrtex encara té un nombre parell de ponts no creuats.

Com que el gràfic està connectat, hi ha un camí des del vèrtex inicial fins a un vèrtex amb un pont sense creuar. Considereu el primer vèrtex d’aquest camí amb un pont sense creuar. Deu ser al passeig. Anomeneu-lo vèrtex A.

Ara comenceu pel vèrtex A i feu una segona caminada, travessant només ponts que encara no heu travessat, ja sigui en aquesta caminada o en la primera. Com abans, la caminada acaba només quan torneu al vèrtex A.

Ara combineu les dues caminades en una única caminada. La manera més senzilla de fer-ho és començar la primera caminada al vèrtex A. Quan torneu al vèrtex A, feu la segona caminada.

Si encara hi ha almenys un pont sense creuar, podeu continuar aquest procés fins que s’hagin creuat tots els ponts.

Us podríeu preguntar què passa si el gràfic només té un vèrtex i almenys un pont. És fàcil demostrar que el gràfic està connectat, el vèrtex té un grau parell i hi ha un passeig d’Euler. Un gràfic amb només un vèrtex i sense ponts no és necessàriament una excepció, tot i que els conceptes de connexió i caminades d’Euler són una mica buits en aquest cas.

Aquest és el resultat desitjat per a un graf connectat en el qual cada vèrtex és de grau parell. Considereu ara un gràfic amb dos vèrtexs B i C de grau senar. Creeu un gràfic una mica més gran inserint un pont que connecti els vèrtexs B i C. Tots els vèrtexs d’aquest gràfic són de grau parell, de manera que té una marxa d’Euler. Una part d’aquesta caminada consisteix a creuar el nou pont des del vèrtex B fins al vèrtex C, o viceversa.

És evident que aquesta caminada d’Euler, sense el nou encreuament entre els vèrtexs B i C, és una caminada d’Euler sobre la gràfica original.