dimarts, 18 d’octubre de 2011

Els ponts d’Euler


Una recança em va quedar de les vacances del passat estiu. Va ser la de no poder visitar Kaliningrad, la falca russa que s’obre pas cap al Bàltic, inserida entre Polònia i Lituània. No sé com ho tenen els ciutadans russos per viatjar a occident, però, per a nosaltres, visitar-los encara representa una veritable peripècia burocràtica. Fins i tot per obtenir el que anomenen un “visat exprés” de 72 hores, cal presentar fotocòpia del passaport, carta de l’hotel on t’allotjaràs, pagar uns 70 euros i entrar al país per punts molt determinats i a hores limitades. I si arribes en avió, cal afegir 25 euros per pagar el desplaçament del funcionari que et segellarà el visat. Amb aquestes condicions (i unes comunicacions nefastes amb Lituània com a afegitó), és lògic que ho deixéssim córrer.

La ciutat i la regió de Kaliningrad reben aquest nom tan sols des de 1946, en honor del líder soviètic Mikhail Kalinin; però abans de la guerra la capital rebia el nom de Königsberg i era una de les ciutats més cultes i reputades de Prússia. Potser el seu fill més cèlebre és el filòsof Immanuel Kant, seguit de prop per l’escriptor romàntic E. T. A. Hoffmann, el dels contes. Tot i que els científics sempre són menys populars, també eren d’allí el físic Gustav Robert Kirchhoff i els importants matemàtics David Hilbert, Hermann Minkovsky i Christian Goldbach (famós per una conjectura). Afegiu-hi el músic Carl Otto Nicolai, l’artista Käthe Kollwitz, la pensadora Hannah Arendt i (si voleu) la model Veruschka.

Però pels matemàtics el primer que ens suggerirà la paraula Königsberg seran els seus ponts, gràcies a un problema que el gran matemàtic suís Leonhard Euler resolgué l’any 1735. La ciutat, creuada pel riu Pregel, compta amb dues illes al seu centre. En aquella època hi havia 7 ponts que comunicaven les illes amb les dues ribes així com entre elles. Algun desenfeinat va preguntar-se si seria possible fer un itinerari que passés per tots els ponts sense repetir-ne cap. Euler va demostrar que això era impossible.

Per resoldre el problema, Euler va reduir el mapa de la ciutat a quatre punts (un per cadascuna de les dues illes, més els corresponents a les dues ribes) i va traçar tantes línies entre punts com ponts hi havia que els comuniquessin. Aquest tipus de figures formades per nodes i arestes, on no es tenen en compte les distàncies sinó només el nombre de punts i la configuració de les connexions, actualment s’anomena “graf” i, per tant, es considera Euler un dels fundadors de la teoria de grafs (les xarxes de metro són un exemple de graf que tots coneixem).


Doncs bé, Euler va demostrar que per poder fer el recorregut proposat calia que de tots els nodes sortís un nombre parell de “ponts” o bé que hi hagués dos (i només dos) nodes amb un nombre imparell de connexions. Com que el graf que correspon als ponts de Koënigsberg té tres nodes dels que surten tres línies, és impossible creuar tots els ponts sense incórrer en repeticions.

Però quina és la situació en l’actualitat? Atès que els russos no afavoriren la nostra visita, he hagut d’acudir a Google Earth per descobrir que els dos ponts més orientals que unien l’illa petita amb terra ferma han desaparegut. Amb aquesta nova configuració sí que és possible passar per tots els ponts de la ciutat sense repetir-ne cap, tot traçant el que s’anomenà un camí eulerià. El que no es pot aconseguir és fer un itinerari que et retorni al punt de partida, per poder-ho fer el graf equivalent hauria de tenir tots els seus nodes amb un nombre parell d’arestes, que no és el cas. Per cert, aquest tipus de recorreguts per la totalitat d’un graf fins retornar a l’inici s’anomena un cicle eulerià.


Sí, Leonhard Euler fou un matemàtic tan fecund que literalment desenes de termes matemàtics porten el seu nom, un fet que condueix a freqüents confusions. Una vella broma de matemàtics proposa que tots aquests termes haurien de dur el nom de la primera persona que les va descobrir després d’Euler. Tanmateix és possible que algunes expressions que duen el nom del matemàtic suís fossin obra d’algun investigador anterior.

Això ens duria a la “Llei de l’Eponímia” de l’estadístic de Chicago Stephen Stigler, segons el qual “Cap descobriment científic porta el nom del seu descobridor”. Per demostrar el que ja es coneix com a “Llei de l’Eponímia de Stigler”, aquest nomena el sociòleg Robert K. Merton com el primer en enunciar-la. Res, crec que m’he allunyat molt de Königsberg.

13 comentaris:

  1. Tartarín de Königsberg! Això és històric: entre tu i el departament d'obres públiques de Königsberg heu resolt el problema.

    ResponElimina
  2. Nunca dejas de sorprenderme (favorablemente). ¡Quién me iba a decir que iba a encontrar una exposición tan elegante de la teoría de grafos en un blog literario! Genial :-)

    ResponElimina
  3. Precisament ahir vaig fer una passejadeta pel Königsberg de Strange Maps que tens enllaçat aquí a la dreta: el títol Walk Like an Eulerian era irresistible!
    (de la foto aèria es dedueix que les guerres i els plans quinquennals han estat devastadors per a la pobra Königsberg)

    ResponElimina
  4. Puig, res que no puguin resoldre unes quantes demolicions.

    ResponElimina
  5. Sufur, la exposición no es nada conexa, pues he saltado de aquí a allí de manera muy poco euleriana.

    ResponElimina
  6. Santi, els plans quinquenals deuen haver fet molt de mal: només cal veure l'autopista que travessa l'illa petita.

    ResponElimina
  7. És una llàstima, perquè m'agrada més Königsberg que Kaliningrad (i, si m'apures, Prússia que URSS). Afortunadament Allen Stewart Konigsberg (Woody Allen pels amics) no va haver de canviar-se a "Allen Stewart Kaliningrad".

    ResponElimina
  8. Brian, em temo que serà difícil que torni el nom antic i mira que fins l'Allen el va repudiar.

    ResponElimina
  9. Qué interessant, Allau, Euler grafero. M'has fet tafanejar més coses d'Euler i em trobo que és l'inventor del número "e"..
    i quants il.lustres fills koningburgesos. La propera has d'anar.

    ResponElimina
  10. Va descobrir un fotimer de coses, Kalamar, però jo a Königsberg no hi vaig si els russos no m'ho posen més fàcil.

    ResponElimina
  11. Tanta fecunditat només pot provenir d'una ciutat amb riu, i si el riu té illes més, sempre s'aguditza l'ingeni, fins i tot dels que no hi poden arribar per culpa de la burocràcia :)

    ResponElimina
  12. Clídice, la teva teoria falla perquè Euler no era d'allí, que era suís, i em sembla que ni tan sols va visitar Königsberg. És clar que a Suissa també en tenen, de rius.

    ResponElimina
  13. Com és que no havia llegit les teves notes topològiques sobre Königsberg?
    Deixa'm recordar una conferència (llegida) que em va obrir els ulls de jovenet. La va dictar fa unes dècades l'alpinista Michel Serres a la Sorbona, i en ella relligava els emblemes topològics del joc de l'oca (l'Eulerià "De pont a pont") i el lacanià "On-Off" (de permès-prohibit), amb l'esquema subjacent en un munt de hits literaris universals. Amb l'Euler i els seus ponts per entremig, mai més he tornat a llegir com llegia de petit. Ara em plau la recerca de les possibles connexions entre illes fluvials.

    ResponElimina