Para comenzar, hablemos un poco de Euler

Es casi una obligación comenzar este Blog sobre Redes Complejas hablando de Leonard Euler, ya que es considerado el padre de la Teoría de Grafos. Euler nació en Basilea en 1707 y fue, junto con Paul Erdös (del que hablaremos próximamente), uno de los matemáticos más prolíficos de la historia. Es de destacar que trabajara en casi todas las disciplinas de las matemáticas, desde geometría, cálculo o  trigonometría, hasta álgebra y teoría de números, realizando incluso diversas incursiones en el campo de la física.

Leonard Euler

Figura 1.- Leonard Euler (Basilea 1707, San Petersburgo 1783). Se puede observar en la imagen cómo uno de sus ojos ya le comenzaba a fallar. Acabaría perdiendo totalmente la visión, lo cual no le impidió seguir investigando y publicando trabajos de gran impacto científico.

Pero vayamos a la historia que, según cuenta la leyenda, dio lugar al origen de la Teoría de Grafos (y más adelante a lo que se conocería como Redes Complejas). A principios del siglo XVII, Königsberg (actualmente Kaliningrado, Rusia) era una tranquila ciudad de la Prusia Oriental. Como muchas otras ciudades europeas, estaba atravesada por un río, el Pregel, que dividía la ciudad en dos mitades, a las que había que sumar dos pequeñas islas debidas a una bifurcación del río.  Para facilitar el paso de una parte a otra de la ciudad, así como a cada una de las islas, se habían construido un total  de siete puentes. El problema de los puentes de Königsberg era sencillo en su planteamiento: ¿es posible visitar a pie todas las zonas de la ciudad, volviendo al punto de partida, pero pasando una única vez por cada puente?

La respuesta es sencilla si se dispone de tiempo y paciencia, ya que se pueden calcular todas las posibles combinaciones de paso por los puentes para llegar a la conclusión de que no es posible: siempre hay que pasar dos veces por uno de los puentes. Como digo, la solución ya era conocida, sin embargo, el mérito de Euler fue encontrar una solución sencilla y elegante, que resolvía no solo el dilema de los puentes de Königsberg, sino también casos mucho más generales. Solo había que transformar a la ciudad y sus puentes en una red.

como proyectar...

Figura 2.- Como proyectar el entramado de puentes de Königsberg en una red.

Si se considera cada una de las zonas de la ciudad como un nodo y cada uno de los puentes que las une como un enlace, es posible obtener una red de 4 nodos y 7 enlaces (ver Figura superior). A partir de ahí, es sencillo demostrar que si queremos iniciar y finalizar el camino en el mismo punto necesitamos dos requisitos: a) que los nodos por los que pasemos tengan un número par de enlaces y b) que en el caso de tener un nodo con un número impar de enlaces, este debía ser el inicio (y final) de nuestro camino. Desgraciadamente, Königsberg no cumplía el primer requisito.

Y fue con este ejemplo tan curioso como Euler creó, sin saberlo, lo que se conoce hoy en día como la Teoría de Grafos. Es interesante como, una vez más, se repite el mecanismo que permite a la ciencia dar saltos de gigante:  si tenemos un problema, ataquémoslo desde  nuevos puntos de vista.

Como curiosidad, Kaliningrado, la antigua Königsberg, conserva hoy en día solo cinco de sus puentes (es lo que tienen las guerras mundiales!). Sin embargo, todavía no es posible realizar lo que se conoce como un “ciclo euleriano”…

Etiquetas: ,

Si te gustó esta entrada anímate a escribir un comentario o suscribirte al feed y obtener los artículos futuros en tu lector de feeds.

Comentarios

Muy interesante, aunque me surge una duda, ¿no fue realmente Paul Erdös el iniciador del estudio de las redes complejas?

Yo que pensaba que los Suizos solo habian inventado el reloj de cuco..

En realidad el reloj de cuco lo inventaron los alemanes!
http://es.wikipedia.org/wiki/Reloj_de_Cuco
Así que si nos por Euler (que nadie sabe que es suizo), y el chocolate, de estos no se acuerda nadie… (tanta neutralidad es lo que tiene!)

De eso nada, Peter Sellers. De hecho, yo, cada vez que tengo un par de millones de euros disponibles me acuerdo de los suizos para meterlos en uno de sus bancos…

Curioso, pensaba contar este problema y su solución el viernes en la Open House de IMDEA Networks :-)

http://fourier.networks.imdea.org/events/openhouse2010/

Pues no. En realidad Erdös se especializó en un tipo de redes complejas, las aleatorias, de las cuales obtuvo la mayoría de sus propiedades. Hablaremos de él en detalle en próximas entradas

Tomo nota. Gracias por los links

¡Enhorabuena por el blog y por el post! Espero que haya muchos más :)

Una libro de divulgación clásico sobre este tema es Linked del mencionado A.-L. Barabási (Linked: The New Science of Networks, Perseus, Cambridge, MA, 2002) Es muy probable que lo conozcáis pero aquí lo dejo por si acaso. Para iniciarse en las redes complejas me parece muy ilustrativo, de rápida lectura, y muy ameno.

Un saludo

Gracias Pablo! Vamos a ver si conseguimos hacer un poco de divulgación sobre el tema de redes complejas y sus aplicaciones (que son muchas y muy variadas).
El libro de Barabási está muy bien, aunque me dio la sensación de que daba demasiada publicidad a sus trabajos. Déjame recomendarte el libro “Sync” de Steven Strogatz si no lo has leído todavía. Aunque no es de redes, me parece uno de los libros de divulgación científica más entretenidos que he leído en los últimos años.

Estoy de acuerdo contigo en que es un tanto propagandístico, pero bueno pasándole el filtro de “ego” creo que es una introducción muy recomendable al tema :) Sobre el trabajo de Barabasi, un artículo que lo resume muy bien, y en consecuencia también del libro es:

Barabasi, A.-L. The Architecture of Complexity. IEEE Control Systems. 27(4), pp. 33 – 42

El libro de “Sync” no lo conocía pero lo pongo en cola! muchas gracias.

Saludos

[...] la entrada de este blog, “Para comenzar, hablemos un poco de Euler”, se describe cómo Euler fue capaz de resolver el problema de los puentes de Königsberg [...]

(requerido)

(requerido)


*