Königsberg, Euler i dibuixos en un sol traç

Amb relativa freqüència, es poden trobar endevinalles que proposen decidir si en certa composició de línies i punts es poden recórrer, començant per un d'aquests punts, totes les línies, passant exactament un cop per cadascuna d'elles. Es a dir, si es pot replicar el dibuix amb un sol traç sense repetir línies.
El sobre tancat i el sobre obert son dos exemples típics:

Sobre tancat (esquerra) i sobre obert (dreta)

Es pot sempre? I, en cas que la resposta sigui negativa, quan es pot? Aquest tema està molt relacionat amb els començaments d'una de les branques de les matemàtiques més importants i amb més aplicacions: la teoria de grafs.
La ciutat russa de Königsberg (actual Kaliningrad ) va ser testimoni dels primers passos importants que es van donar en relació amb els grafs. I els seus set ponts van ser els culpables. La pregunta era si es podien recórrer tots aquests set ponts passant per cadascun d'ells exactament una vegada, sent la situació dels mateixos com es mostra en la següent imatge. Els ponts estan envoltats amb cercles blaus i les quatre regions etiquetades amb les lletres A, B, C i D:

Königsberg i els seus set ponts

Va ser Leonhard Euler qui va donar resposta a aquesta pregunta. Va assignar a cada porció de terra un punt, i a cada pont una línia, convertint el problema dels ponts en un problema de teoria de grafs.
El graf que va obtenir és el següent:

Grafo que modelitza la situació dels ponts de Königsberg

Com que cal començar en un vèrtex i acabar en un altre (podria ser el mateix en el qual es comença), Euler va observar que en els vèrtexs intermedis han de concórrer un nombre parell d'arestes, perquè per cadascuna amb la qual vam arribar a aquest vèrtex n'hi hagi una altra per la qual sortim d'ell. Com en el graf dels ponts de Königsberg tots els vèrtexs tenen un nombre imparell d'arestes, la conclusió és que no es pot trobar un camí que recorri tots els ponts passant per cadascun d'ells exactament un cop.

Teoria de grafs
Un graf és un conjunt de punts, anomenats vèrtexs, i un conjunt de línies, anomenades arestes, que connecten un parell de punts. Una construcció tan simple, en primera instància, té multitud d'aplicacions, donada la potència que tenen els grafs per modelitzar situacions reals.
És interessant destacar que la teoria de grafs no s'ocupa de les propietats geomètriques del graf (com la forma o la mida), sinó per les seves propietats topològiques (més generals), com la connexió.
La qüestió ara és determinar quines condicions ha de complir un graf per si es pot trobar un camí com el que estem buscant. Encara que amb el que s'ha dit fins ara, ja es pot intuir.
En tot el que s'ha comentat fins ara, s'està tractant amb grafs no dirigits, que són grafs en els quals es pot recórrer cada aresta en els dos sentits (en els grafs dirigits, les arestes es representen amb fletxes i només es poden recórrer en el sentit que estigui indicat per cada fletxa), i amb grafs connexos, que són grafs en els quals cada vèrtex sempre pot connectar-se amb qualsevol altre mitjançant un camí d'arestes. En aquest tipus de grafs, el grau d'un vèrtex és el nombre d'arestes que concorren en ell. Després d'aquesta definició, a continuació detallem el teorema que diu quan es pot fer el que es busca:

Teorema
En un graf no dirigit i connex, podem trobar un camí que recorri totes les arestes passant per cadascuna d'elles exactament una vegada si es dóna alguna de les següents situacions:

1. Tots els vèrtexs tenen grau parell. En aquest cas, podem començar en qualsevol d'aquests, i acabarem en aquest mateix vèrtex.
2. Dos dels seus vèrtexs tenen grau senar i la resta té grau parell. Llavors, el camí buscat començarà en un dels vèrtexs de grau imparell i acabarà en l'altre. El primer s'anomena circuit eulerià (perquè comença i acaba en el mateix vèrtex) i el segon, camí eulerià.

Amb aquest resultat ja podem respondre al que preguntàvem al principi de l'article: no podem trobar un camí d'aquest tipus que recorri el sobre tancat (té quatre vèrtexs amb grau imparell) i si podem trobar aquest camí en el sobre obert (té dos vèrtexs amb grau imparell).
Ara que es te el quan, l'interessant seria saber el com. És cert que en un graf amb pocs vèrtexs i poques arestes no és difícil trobar el camí (o el cicle) a ull, però quan el nombre de vèrtexs i el nombre d'arestes creix, la cosa es complica. Per això, cal veure un mètode, atribuït a Carl Hierholzer, per trobar un circuit eulerià (en grafs els vèrtexs tenen tots grau parell) que després usarem també, per trobar un camí eulerià en grafs amb exactament dos vèrtexs de grau senar.

Com trobar un circuit eulerià? Com tots els vèrtexs han de tenir grau parell, es pot començar pel que es vulgui. Es pren un vèrtex qualsevol, per exemple l'A, com a començament, i se segueixen els següents passos:

1. Buscar un camí d'arestes (sense repetir cap) que comenci a A i acabi també a A. Cal apuntar llavors la seqüència de vèrtexs que s'ha recorregut (que, evidentment, començarà a A i acabarà també a A).
2. Es treuen les arestes que s'han recorregut i els vèrtexs aïllats (vèrtexs als quals no arriba cap aresta), si és que va quedar algun.
3. Si encara queda alguna cosa del graf, es pren un vèrtex pel qual ja s'hagi passat i es torna a fer el mateix que en el pas 1: buscar un camí d'arestes que hi comenci i hi acabi, i apuntar la seqüència de vèrtexs recorreguts.
4. Inserir aquesta seqüència en l'anterior. Per exemple, si la primera era (A, B, C, E, D) i la segona és (B, J, L, B), quedaria (A, B, J, L, B, C, E, D ). Després, treure arestes recorregudes i vèrtexs aïllats.
5. Repetir els passos 3 i 4 les vegades que sigui necessari, i anar inserint les seqüències de vèrtexs obtingudes. El camí que queda al final és un camí que passa per totes les arestes exactament un cop.

Veure un exemple amb un graf concret. Cal trobar un circuit eulerià en el graf que Lewis Carroll li va enviar per carta a una de les seves amigues al 1869 i que Carlo Frabetti ens ensenyava a El sobre màgic de Lewis Carroll :

Königsberg, Euler i dibuixos en un sol traç

Es pot comprovar que tots els seus vèrtexs tenen grau parell, de manera que es pot trobar el nostre eulerià. Es tria un vèrtex per començar, per exemple l'A i s'aplica el pas 1. Com que és igual el camí tancat que es tria, es prenen el (A, E, F, I, G, B, A). Treure les arestes recorregudes i els vèrtexs aïllats, com indica el pas 2. Queda el següent graf:

 Königsberg, Euler i dibuixos en un sol traç

Pas 3: prendre un vèrtex del graf resultant pel qual ja s'hagui passat i buscar un camí tancat com en el primer pas. Per exemple, triar el B i recórrer el camí (B, R, Q, M, L, J, H, C, B). I ara, com comenta el pas 4, inserir aquesta seqüència de vèrtexs a la primera. Queda la seqüència següent:

(A, E, F, I, G, B, R, Q, M, L, J, H, C, B, A)

Traiem arestes ja recorregudes i els vèrtexs que queden aïllats i ens queda el següent graf:

 Königsberg, Euler i dibuixos en un sol traç

I com es pot veure, aplicant el procediment un cop més, ja s'ha acabat. Treure, per exemple, el vèrtex Q i prendre el camí (Q, C, D, J, I, K, L, N, O, P, Q). Amb això, ja s'han recorregut totes les arestes del graf exactament una vegada. Inserir aquesta seqüència en l'anterior i ja es disposa del circuit eulerià:

(A, E, F, I, G, B, R, Q, C, D, J, I, K, L, N, O, P, Q, M, L, J, H, C, B, A )

Possiblement, sigui interessant dibuixar el graf en un paper i seguir el camí obtingut ratllant les arestes que es van recorrent, per comprovar que en realitat es tracta d'un circuit eulerià. També es poden buscar altres possibles circuits eulerians, ja que, evidentment, aquesta no és la única opció possible.
Però, com trobar un camí eulerià en un graf que tingui exactament dos vèrtexs de grau senar?. Si s'anomenen A i B a aquests dos vèrtexs, la clau és dibuixar una nova aresta que una A amb B (tot i que ja hi hagués una). Amb això s'aconsegueix un graf els vèrtexs del qual tenen tots grau parell, i es pot aplicar el procés descrit anteriorment. Només cal anar amb compte amb un parell de coses. La primera és que el vèrtex triat per començar sigui un dels dos que tenen grau senar al principi, l'A o el B. I la segona és que, durant el procés, cal anar triant camins que no continguin a l'aresta que s'ha afegit. El més convenient és que aquesta aresta quedi per al final, que sigui l'última aresta recorreguda. Així, quan es tingui la seqüència de vèrtexs del circuit eulerià, simplement s'ha d'eliminar l'últim vèrtex (que serà el vèrtex amb el qual es va començar) i ja es te el camí eulerià.
Veure el cas del sobre obert com a exemple. Partint del graf inicial, afegir l'aresta que fa que tots els vèrtexs siguin de grau parell i aplicar el procés començant amb el vèrtex A. Al final s'obté el camí eulerià resultant, amb les arestes numerades segons l'ordre en què les s'ha recorregut:

Font: Gaussianos