El
matemático húngaro Endre Szemerédi ha sido galardonado con el Premio Abel
correspondiente a este año de 2012. El Premio Abel, considerado el Nobel de las
matemáticas, lo concede anualmente la Academia Noruega de las Ciencias y las
Letras y está dotado con casi 800.000 euros.
Szemerédi recibe la alta distinción “por sus contribuciones fundamentales en matemática discreta y en teoría de las ciencias de la computación, así como en reconocimiento del profundo y duradero impacto de estas contribuciones a la teoría aditiva de números y la teoría ergódica”. El matemático húngaro recibirá el premio el 22 de mayo en justo reconocimiento a un autor cuya influencia sobre la matemática actual es notable.
Szemerédi recibe la alta distinción “por sus contribuciones fundamentales en matemática discreta y en teoría de las ciencias de la computación, así como en reconocimiento del profundo y duradero impacto de estas contribuciones a la teoría aditiva de números y la teoría ergódica”. El matemático húngaro recibirá el premio el 22 de mayo en justo reconocimiento a un autor cuya influencia sobre la matemática actual es notable.
La
matemática discreta es el estudio de estructuras como los grafos, las
secuencias, las permutaciones y las configuraciones geométricas, según explica
el comité que ha elegido este año a Szemerédi. Las matemáticas de tales
estructuras forman los cimientos de la ciencia de computación teórica y el húngaro
ahora galardonado fue uno de los primeros en darse cuenta de su importancia.
Fijémonos en el asunto de los grafos,
para ello hemos de remontarnos al matemático Leonard Euler, al que se considera
el pionero de esta materia. Un grafo es
un conjunto no vacío de objetos llamados vértices (o nodos) y una selección de
pares de vértices, llamados aristas (edges en inglés), que pueden ser
orientados o no. Típicamente, un grafo se representa mediante una serie de
puntos (los vértices) conectados por líneas (las aristas).
Al parecer, en 1735 un grupo
de jóvenes de la ciudad de Königsberg visitó al matemático suizo Leonhard Euler
para pedirle que resolviera una cuestión
sobre la que no se ponían de acuerdo, averiguar si era posible encontrar un
camino que atravesase las cuatro zonas de la ciudad en las que ésta quedaba
dividida como consecuencia del paso del Río Pregel por la misma, pasando una y
sólo una vez por cada uno de los siete puentes que existían para cruzarlo.
 |
| Los puentes de Königsberg |
Sobre este asunto el matemático
suizo comentó lo siguiente: “Se me ha informado que, mientras unos dudaban la
posibilidad de hacerlo y otros lo negaban, nadie sostenía que fuese posible
realmente. El problema podría resolverse haciendo cuidadosamente una tabla de
todos los recorridos posibles, asegurándose así, por inspección, de cuál de
todos ellos, si es que alguno hay, satisface lo requerido. Este método de
solución, sin embargo, es demasiado tedioso y difícil a causa del gran número
de combinaciones posibles…Por tanto, lo descarté y traté de buscar otro que
mostrase solamente si se puede descubrir un camino que satisfaga la condición
prescrita”.
Euler trató de resolver el
problema de una forma más precisa y metódica que por la simple experimentación
de todos los casos posibles. Para ello, modelizó en primer lugar la situación
prescindiendo de la naturaleza física del problema y sustituyendo las cuatro
zonas habitadas de la ciudad por puntos y los siete puentes
por líneas entre esos puntos, con lo cual creó un
diagrama geométrico que constituyó el germen de lo que actualmente conocemos
como un grafo. De hecho, esta resolución del problema por Euler, que dio además
una solución general al problema independientemente del número de zonas o de
puentes que hubiese en la ciudad, supuso el nacimiento de una nueva rama de las
matemáticas, la teoría de grafos, distinta
de las tradicionales conocidas hasta el momento. Otros pioneros de la materia
fueron Kirchhoff (problemas de redes eléctricas), Guthrie (problema de los
cuatro colores) o Cayley (teoría de árboles).
Pero la teoría de grafos también
se aplica a la informática y la economía. El famoso algoritmo de Google, el
PageRank, es una mezcla de teoría de grafos, probabilidad y álgebra lineal. Internet
puede describirse mediante un grafo donde cada página, Pi de la red
es un vértice del grafo, y hay una arista dirigida entre los vértices Pi y Pj si desde la página Pi hay
un enlace a la página Pj. Así
comienza a configurarse un grafo gigantesco cuya estructura real abruma por su
tamaño. No obstante, a los grafos se les asocian modelos matriciales que
funcionan con códigos numéricos binarios, de unos y ceros. El elemento clave
para el buen desarrollo y funcionamiento de un buscador de Internet es la matemática,
el uso adecuado de ciertos teoremas (por ejemplo, el de Perron-Frobenius) y el
análisis cuidadoso de la convergencia de los algoritmos.
La teoría de grafos también
se aplica a la economía y a los procesos productivos industriales, la
comprensión de las relaciones intersectoriales entendidas como flujos de producción ha constituido uno
de los pilares en los estudios de localización de ejes de crecimiento
necesarios en la planificación de las
políticas industriales coordinadas. La teoría de grafos y redes aplicada en un
amplio conjunto de materias como la sociología, psicología o geografía ha
resultado de gran utilidad como análisis de análisis estructural de economía.
