Arxiu del dimecres, 26/09/2018

Les putes urnes i la teoria de grafs

dimecres, 26/09/2018

Donde estarán las putas urnas, hostia?” La frase pertany a un fragment d’un dels vídeos que han sortit a la llum on es veu l’actuació de la policia cercant les urnes el dia 1 d’Octubre de fa un any. Es pot veure com, després d’entrar als col·legis i d’anar obrint les portes, resulta que no poden localitzar les urnes. Sense entrar en el fons del que va passar (que aquí no toca), podem aprofitar el problema d’aquells nois per veure com ho haurien d’haver fet per revisar tot l’edifici de manera eficient.

En el fons no deixa de ser un problema topològic. La topologia és la branca de les matemàtiques que s’encarrega de l’estudi de les propietats espacials. Hi ha moltes especialitats, però una de les primeres aplicacions va ser investigar els algoritmes que permetien sortir d’un laberint.

El més conegut consisteix, simplement en triar un costat (dret o esquerra) i sempre anar seguint el mateix. Si hem triat la dreta, a cada cruïlla triar anirem cap a la dreta. Si arribem a finals de túnel, tornarem enrere i seguirem escollint la dreta. A la pràctica és com si poséssim la mà tocant la paret d’un costat i sempre anéssim enganxats a aquella paret. Abans o després arribarem a la sortida.

El que passa és que en aquest cas, el que volien no era sortir del laberint (és a dir de l’escola) sinó recórrer totes i cada una de les sales del laberint. Estrictament, els armaris i racons també els consideraríem sales a explorar. Essencialment la policia s’havia de comportar com un robotet aspirador, que ha de cobrir tota la zona del terreny. No hi ha problema! També per això s’han establert diferents algoritmes.

A finals del segle XIX, el matemàtic francès Gaston  Tarry ja va proposar un sistema que permet recórrer la totalitat del laberint. Un algoritme similar va ser proposat en la mateixa època per l’enginyer, també francès, Charles Trémaux. La idea és que cada vegada que arribes a un creuament pots fer tres coses: triar un passadís nou, triar un passadís que ja has explorat o tornar pel passadís d’on vens. El mètode de Trémaux consisteix en:

- No seguir el mateix camí dues vegades.

- Quan s’arriba a una cruïlla nova, tant se val quin camí agafis.

- Quan s’arriba a una cruïlla vella, o a un lloc sense sortida, retrocedir fins a l’entrada del camí.

- Si un camí vell porta a una cruïlla vella, triar un camí nou, i si no n’hi ha, agafar-ne qualsevol.

Amb això i paciència, acabes per recórrer tot el laberint.

Un altre sistema, proposat pel matemàtic americà Oysten Ore funciona a partir de nivells. Camines fins la primera cruïlla i la marques amb un 1. Després agafes qualsevol camí i en arribar a la següent cruïlla poses un 2 i tornes enrere. Fas el mateix per tots els camins.  A continuació vas fins la primera de les cruïlles marcades amb 2 i repeteixes el procés marcant amb un 3 totes les noves cruïlles. Amb paciència aniràs recorrent tots els nivells, encara que repetiràs molts camins moltes vegades.

Pels matemàtics, un laberint de seguida el veuen com un “graf”, una estructura matemàtica feta per un conjunt de vèrtex i arestes connectades de diferents maneres. Entenent aquestes connexions (d’això se n’encarrega la teoria de grafs) es poden fer estudis sobre coses tan diferents com la transmissió de malalties infeccioses, els resultats de les eleccions polítiques, la optimització del flux de dades per internet, l’anàlisi d’estructures lingüístiques o la predicció de reaccions químiques. I, és clar, sobre com sortir d’un laberint o sobre com recorre’l tot.

Qui ho sap? Potser un millor domini de les matemàtiques els hauria servit per trobar les urnes. Més que res perquè generalment és millor pensar una mica i aplicar els coneixements científics que aplicar la força bruta.