Entradas etiquetadas como ‘Teoría de Gráficas’

Los amigos de mis amigos

Cada año la gripe recorre la Tierra y, aunque la llamamos igual, cada año es distinta: ataca a más población, es más dañina o más benigna. Naturalmente el virus que la produce no siempre es el mismo y detectar las distintas mutaciones lo antes posible puede ser importante para prevenir riesgos y decidir las medidas a tomar. En 2009 cuando se temió una grave epidemia de gripe producida por el virus H1N1, los científicos de Harvard Nicholas Christakis y James Fowler desarrollaron un método que permitió predecir el avance de la epidemia con dos semanas de anticipación, proporcionando un tiempo extra precioso que pudo ser bien aprovechado y que ayudo a controlar dicha epidemia que finalmente fue más benigna que otros años. La pregunta es: ¿en qué consistía la técnica de Christakis y Fowler? ¿Eran estos dos investigadores prestigiosos médicos, biólogos, farmacéuticos, …?

La respuesta es que la técnica desarrollada por los dos profesores de Harvard se basaba solo y exclusivamente en una propiedad de la Teoría de Grafos, rama de las matemáticas y es una propiedad que tiene que ver con el número de amigos en Facebook o de compañeros de relaciones sexuales que ha tenido cualquier persona y que se conoce como la paradoja de la amistad.

Dicha paradoja viene a decir que es muy  probable que nuestros amigos tengan más amigos de los que tenemos nosotros y esto vale tanto para Facebook como para cualquier grupo de personas real. La versión sexual de la paradoja es que es muy probable que las personas con las que hemos tenido relaciones sexuales hayan tenido más relaciones sexuales que nosotros (pero más de uno pensará, con cierta razón, que sus amigos no están tan enganchados a internet y por eso tienen más éxito en el mundo real).

Veamos lo que queremos decir con un ejemplo sencillo, supongamos que tenemos un grupo de cuatro personas y que las amistades entre ellos las representamos con el siguiente grafo (los vértices son las personas y existe una arista entre ellos si son amigos):
amigos

 

En este ejemplo A, tiene un amigo, mientras que este (B), tiene tres amigos. C tiene dos amigos mientras que sus amigos tienen una media de 2,5 amigos y lo mismo ocurre con D. Así solo B tiene más amigos que sus amigos. Por tanto, en este ejemplo simple, tenemos una probabilidad de tres entre cuatro de que los amigos de alguien tengan más amigos (de media) que ese alguien.

¿Ocurrirá lo mismo en cualquier red que muestre las interconexiones (ya sean de amistad, de Facebook o sexuales) entre distintos individuos? Se puede demostrar que en cualquier grafo en el que exista una cierta variedad en los grados (número de conexiones) de los vértices esto ocurre siempre. Por ejemplo, se ha estudiado qué ocurre en Facebook en este trabajo y se llega a la conclusión de que en el 93% de los casos, los amigos de un usuario tienen más amigos que él. Más sorprendente: el número de amigos medio es de 190, pero la media de amigos de sus amigos es de 635.

¿Por qué ocurre esto?

En primer lugar, no nos deprimamos: es una propiedad que se da por la variedad de los grados y existen vértices (individuos) que tienen muchos más amigos que la media y es muy probable que estemos conectados con uno de dichos vértices, lo cual hará que se incremente la media de los amigos de nuestros amigos: la existencia de gente muy popular es lo que hace que se dé esta propiedad. Este fenómeno fue observado por primera vez por el sociólogo Scott Feld en 1991.

En realidad, esta propiedad tiene que ver con otras muchas que hace que algunas encuestas estén mal condicionadas. Por ejemplo: si a la salida de un multicine preguntamos a algunos de los espectadores que salen que cómo de llena estaba su sala, la mayoría dirá que bastante llena, porque hay más gente que sale de las salas llenas que de las semivacías. O, un ejemplo extraído de una entrada del New York Times sobre esta paradoja de la cual hemos obtenido la mayoría de la información aquí reflejada, si vamos al gimnasio, nos parecerá que la mayoría de la gente está en mejor forma que nosotros, porque la muestra la estamos extrayendo entre aquellos que están en el gimnasio y entre ellos tendremos a muchos que sean muy asiduos del gimnasio, porque a los más perezosos será más difícil encontrarlos allí.

Pero y todo esto, ¿qué tiene que ver con la gripe?

Pues lo que Christakis y Fowler hicieron fue escoger una cierta población de estudiantes que les serviría como medida y cada uno de ellos nombró a unos cuantos amigos, previsiblemente el grupo de los amigos tendrían una mayor conectividad que la población aleatoria escogida inicialmente y así fue: en el grupo de amigos se desarrolló la enfermedad dos semanas antes de media. Ello también ha llevado a proponer un método de inmunización para cuando no se desee vacunar a toda la población de una ciudad (por razones económicas, por ejemplo),  se ha probado que una estrategia efectiva es escoger una cierta población inicial aleatoriamente y que los individuos de dicha población designen cada uno unos cuantos amigos: si vacunamos a estos amigos solo necesitamos vacunar a un 20%-40% de la población para evitar la difusión de la enfermedad, mientras que si no seguimos esta estrategia, necesitaríamos vacunar a un 80%-90% para alcanzar la misma efectividad.

Ya ven, a lo mejor resulta que al final los amigos de mis amigos no son mis amigos 😉

De rama en rama, pero por el camino más corto

–Ya hemos llegado –dijo Ven –. Esta es la librería Voronoi.

–El que reparte el bacalao –bromeó Sal.

–¡Toma! ¡Cómo mola el escaparate con nuestro libro! –añadió el pequeño.

–¡Guauu, guauuuu!

–Sí, está precioso –dijo Mati –, me encanta.

–Y hemos llegado rapidísimo gracias al itinerario que tú has preparado, Mati –dijo el gafotas.

Mati20Min_42p

–Bueno, es que la Teoría de Grafos es muy apañada para diseñar rutas de recorridos mínimos –respondió ella con un guiño.

–¿Nos enseñas a hacerlo, Mati? –pidió Sal.

–Con muchísimo gusto –respondió la pelirroja –. Antes de planear la ruta, he dibujado un grafo de la siguiente manera: un vértice, un punto rojo, que representa a nuestra casita. Después he puesto un vértice por cada una de las 10 librerías que queríamos visitar hoy: Celsius, Euler, Fahrenheit, Fibonacci, Gadner, Gauss, Hilbert, Könisberg, Richter y Voronoi.  A continuación, he dibujado aristas, segmentos azules, uniendo esas librerías indicando la distancia en metros de cada posible ruta  que las unía, mirad:

dijkstra_1

 

–Vamos a construir  los caminos de recorrido mínimo desde nuestra casita hasta cada una de las 10 librerías usando el algoritmo de Dijsktra –continuó Mati –El resultado de esta construcción será un árbol.

–¿Un árbol? –preguntó Ven con cara de sorpresa.

–Sí, un árbol –confirmó ella –Es decir, nos quedaremos solo con algunas de las aristas azules de este grafo que acabamos de dibujar de forma que todas las librerías  aparecen conectadas con esas aristas y se puede ir de uno a cualquier otro paseando por ellas. Además, no se forman ciclos de aristas, es decir, no hay ningún recorrido circular como el que aparece marcado con trazo rojo en la siguiente imagen.

dijkstra_2

 

–¿Y cómo sabemos qué aristas se quedan y qué aristas se van?–preguntó el gafotas.

–Eso es lo que  os voy a explicar ahora mismo –anunció Mati con una sonrisa –Para ello, vamos a hacer una tabla que nos ayude, como esta:

tabla_1

 

–En la primera columna  –continuó ella –ponemos el nombre de las librerías que queremos visitar. En la columna central, escribimos la longitud del camino más corto  desde casa a la librería correspondiente encontrado  hasta ese momento, y en la última columna el nombre de la última librería de ese camino que hemos visitado antes de llegar a la librería de esa fila.

Los niños asintieron con la cabeza y permanecieron muy atentos, Gauss se dedicó a mirar a las perritas que pasaban…

–Comenzamos desde el vértice que representa a nuestra casa –siguió la pelirroja –, ¿a cuántas librerías podemos llegar directamente desde Casita?

dijkstra_3

 

–A 5 –dijo Sal –: a la librerías Gauss, Euler, Voronoi, Fibonacci y Fahrenheit.

–Efectivamente –confirmó Mati –, vamos a pintar esas librerías de amarillo:

dijkstra_4

 

–Ahora miramos la distancia desde casa a cada una de esas 5 librerías –siguió ella –y la escribimos en la tabla, a las librerías que no están conectadas con nuestra casa le asignamos la distancia infinito, porque aún no podemos llegar a ellas. En esta primera tabla, la en la columna de la derecha solo puede estar nuestra casa porque salimos de allí.

tabla_2

 

–Nos fijamos ahora en la librería más cercana de las 5 conectadas a casa –les propuso Mati.

–Hay 2 –dijo Ven rápidamente –, Gauss y Fahrenheit.

–Tendremos que elegir una de ellas –dijo Mati, ¿cuál?

–¡¡Gauss!! –respondieron los niños al unísono.

–¡Guauuuuu, guauuuuu, guaauuuu! –dijo… bueno, ya sabéis quién.

–Muy bien, elegimos la librería Gauss. Pintamos de verde el vértice correspondiente y la arista que la une con nuestra casa.–continuó Mati –. Y ahora desde esta librería, podremos llegar a otras nuevas.

–¡Sí! –exclamó el pequeño — A Euler y a Könisberg.

–Las pintamos de amarillo –concluyó Mati.

dijkstra_5

 

–A continuación, actualizamos la tabla –les dijo –. Desde la librería Gauss podemos llegar a Euler, Fahrenheit, Richter y Könisberg. Calcularemos el recorrido de los 4 caminos que, pasando por la librería Gauss, van de casa a cada una de estas 4 librerías, y para cada una de ellas nos quedamos con el que pasa por Gauss solo si es menor que el que ya está en la tabla. Para la librería Euler, el camino que pasa por Gauss mide 180 (arista entre Casita-Gauss) más 230 (arista Gauss-Euler), esto es, 410. Lo descartamos porque en la tabla anterior Euler está a 330 de casa. Para la librería Fahrenheit, el camino que pasa por Gauss mide 180 (arista entre Casita-Gauss) más 314 (arista Gauss-Fahrenheit), esto es, 494. Lo descartamos porque en la tabla anterior Fahrenheit está a 180 de casa.  Para la librería Richter, el camino que pasa por Gauss mide 180 (arista entre Casita-Gauss) más 198 (arista Gauss-Richter), esto es, 378. Este sí lo cambiamos  porque en la tabla anterior Richter estaba distancia infinita de casa. Y por último, para la librería Könisberg, el camino que pasa por Gauss mide 180 (arista entre Casita-Gauss) más 275 (arista Gauss-Könisberg), esto es, 455. Este también  lo cambiamos  porque en la tabla anterior Könisberg estaba distancia infinita de casa. Solo tenemos que actualizar Richter y Könisberg:

tabla_3

 

–Qué chulo, Mati… –Sal estaba embobado.

–Lo es –dijo ella –. Ahora miramos, de nuevo, la columna central y buscamos a quién corresponde el número más pequeño…

–¡Fahrenheit! –gritó Ven — ¡El de los termómetros de Estados Unidos!

–¡Vamos para allá! –exclamó Mati –¡Fahrenheit en verde!

–¡Ahora pillamos a Celsius y a Hilbert! –añadió el gafotas –¡Que se vuelvan amarillos!

dijkstra_6

–¡Toma, toma, toma! ¡Cómo mola! –dijo Ven.

–Actualicemos nuestra tabla –sugirió ella –Desde Fahrenheit se puede llegar a Richter, Celsius, Hilbert y Fibonacci. Estudiemos esos caminos: Para la librería Richter, el camino que pasa por Fahrenheit mide 180 (arista entre Casita-Fahrenheit) más 267 (arista Fahrenheit-Richter), esto es, 447.   Lo descartamos  porque en la tabla anterior Richter estaba a distancia 378 de casa. Para la librería Celsius, el camino que pasa por Fahrenheit mide 180 (arista entre Casita-Fahrenheit) más 255 (arista Fahrenheit-Celsius), esto es, 435.   Este sí lo cambiamos  porque en la tabla anterior Celsius estaba distancia infinita de casa. Para la librería Hilbert, el camino que pasa por Fahrenheit mide 180 (arista entre Casita-Fahrenheit) más 230(arista Fahrenheit-Hilbert), esto es, 410.   Este también lo cambiamos  porque en la tabla anterior Hilbert estaba distancia infinita de casa. Para la librería Fibonacci, el camino que pasa por Fahrenheit mide 180 (arista entre Casita-Fahrenheit) más 450 (arista Fahrenheit-Fibonacci), esto es, 630.   Lo descartamos  porque en la tabla anterior Fibonacci  estaba a distancia 345 de casa. Solo cambiamos entonces Celsius y Hilbert:

tabla_4

 

–Como veis –dijo Mati –, estoy marcando en amarillo las librería que ya están en verde, porque esas ya están en nuestro árbol ¿Adónde vamos?

–¡A Voronoi! -gritaron los niños.

–Sí –dijo Mati –Desde Casita, como dice en la tabla. Pintamos de verde Voronoi y la arista que lo une con Casita.

–Y a Gadner de amarillo –añadió el gafotas –porque lo hemos pillado.

dijkstra_7

 

–¡Esto marcha! –dijo la gafotas –Vamos a actualizar la tabla –Desde Voronoi se puede llegar a Euler, Gadner y Fibonacci, veamos esas rutas. Para la librería Euler, el camino que pasa por Voronoi mide 190 (arista entre Casita-Voronoi) más 317 (arista Voronoi-Euler), esto es, 507.   Lo descartamos  porque en la tabla anterior Euler estaba a distancia 330 de casa. Para la librería Gadner, el camino que pasa por Voronoi mide 190 (arista entre Casita-Voronoi) más 170 (arista Voronoi-Gadner), esto es, 360.   Este lo cambiamos  porque en la tabla anterior Gadner estaba a distancia infinita de casa. Para la librería Fibonacci, el camino que pasa por Voronoi mide 190 (arista entre Casita-Voronoi) más 299 (arista Voronoi-Fibonacci), esto es, 489.   Lo descartamos  porque en la tabla anterior Fibonacci estaba a distancia 345 de casa. Solo cambiamos Gadner.

 

tabla_5

 

–¿Hacia dónde vamos, caballeros? –preguntó Mati.

–Hacia Euler –dijo el gafotas.

–El de los puentes de Könisberg –añadió Ven.

–Eso es –dijo ella –, vamos a Euler desde Casita según nuestra tabla. Pintamos de verde Euler y la arista Casita-Euler.

dijkstra_8

 

–Si miramos ahora las rutas que llegan a Gadner y a Könisberg pasando por Euler –continuó ella –, miden 745 y 630, respectivamente. son peores que las de la tabla que tenemos, así que no cambiamos nada. Y ahora, ¿adónde vamos?

tabla_6

 

–¡A Fibonacci! –dijo Sal.

–¡El de los conejos! –añadió su hermano.

–¡Allá vamos! –dijo Mati –¡A Fibonacci, desde Casita!

dijkstra_9

 

 

–Las rutas que llegan a Hilbert y a Gadner desde Casita pasando por Fibonacci –dijo Mati –, miden respectivamente, 595 y 655. Son peores que las de la tabla, tampoco cambiamos nada ahora.

tabla_7

–¡Nos vamos a Gadner! –gritó Sal.

–El bromista… –dijo Ven.

–Muy bien –dijo ella —A Gadner desde Voronoi.

dijkstra_10

 

 

–Desde Gadner –dijo Mati –no podemos llegar a ninguna librería en amarillo, así que no tenemos que cambiar la tabla.

tabla_8

 

 

–¿Siguiente? –preguntó Mati teatrera.

–¡Richter! –dijo el gafotas.

–¡El de los terremotos! –añadió su hermano.

–¡A Richter desde Gauss! –puntualizó la pelirroja.

dijkstra_11

 

–Tendremos que calcular ahora las rutas que llegan a Könisberg y a Celsius (en amarillo) pasando por Richter –propuso Mati –. Para Könisberg esa ruta mide 603, los 378 de Casita a Richter en nuestro árbol verde más los 225 de Richter a Könisberg; para Celsius, tendemos 658. Los dos son peores que los de la tabla, no cambiamos nada.

tabla_9

 

–¡Nos vamos a Hilbert desde Fahrenheit! –anunció el gafotas.

–¡Toma! –dijo Ven –¡A ver si nos lleva a su hotel infinito!

dijkstra_12

 

–Tampoco tenemos que cambiar la tabla –dijo Mati –porque Celsius está más cerca de Casita si vamos por Fahrenheit.

tabla_10

–¡Vamos que nos vamos! –exclamó el pequeño –¡A Celsius desde Fahrenheit!

dijkstra_13

 

–Pues ya está -dijo el gafotas –porque Könisberg está más lejos por Celsius, así que a Könisberg por Gauss como dice la tabla, ¿no, Mati?

–Perfecto –dijo Mati orgullosa de sus exploradores.

dijkstra_14

 

-Ya lo tenéis –anunció la pelirroja –Si nos quedamos solo con las aristas verdes, tenemos el árbol que nos proporciona los recorridos de longitud mínima desde casa hasta cualquiera de las librerías que venden nuestro libro.

dijkstra_final

 

–¡Toma, toma, toma!¡Mola infinito! –dijo Ven.

–¡Y más allá! –añadió su hermano.

–¡Guauuuuuuuuuu! –dijo Gauss poniendo una nota discordante…

 

 

«Gráfica» es nombre de mujer

Mati20Min_38pPues sí, como ya nos descubrieron Mati y sus amigos el miércoles pasado, gracias  a la nueva edición de 20minutos para México, este blog tendrá nuevos amigos, o así al menos lo esperamos, al otro lado del Atlántico. Les damos a todos ellos un cálido abrazo de bienvenida y les invitamos a compartir el gusto por las Matemáticas en este rincón de la red. Como dice mi santo cuando da una charla en aquel país, si en algún momento utilizo la expresión ‘coger’ en alguno de mis artículos, en realidad quise decir ‘agarrar’. Bueno, y también cuando digo charla, quiero decir plática, que es como le llaman por allá.

Son muchos los lazos personales y profesionales que me unen a México, es por ello por lo que me hace especialmente feliz poder asomarme por allí también desde esta ventana. No es éste el sitio para hablar de los motivos personales, esto es un blog de Matemáticas, pero déjenme que les cuente que tengo un montón de familiares en este maravilloso país. México  los acogió con calor cuando la madre patria no los quería por sus ideas políticas… Ya saben de qué hablo.

Víctor Neumann-Lara

Víctor Neumann-Lara

A nivel profesional, tengo la suerte de trabajar en una disciplina que tiene un gran auge en ese país, la Teoría de Grafos, gracias, entre otras razones al empuje de un gran matemático, Víctor Neumann-Lara, que supo intuir la importancia que esta disciplina iba a tener en el desarrollo de la Informática y apostó fuerte por ella, impartiendo cursos, organizando coloquios y preparando a investigadores en el área. Ops, perdón… Víctor Neumann no los llamaba  grafos, sino  gráficas. Y así le llaman todos los investigadores mexicanos del área que he tenido el placer de conocer y/o el honor de trabajar con ellos ¿Por qué? Pues lo pregunté una vez a un colega mexicano y me contó que Víctor decía que eran unos objetos de una belleza tal que debían tener un nombre femenino. Y, oye, me gustó, pero reconozco que no he conseguido ningún avance en mi intento de que la comunidad española los llame así 😉 Posiblemente, porque usamos la palabra gráfica para referirnos a la representación de funciones o de datos estadísticos.

Pero además de su labor como matemático, Víctor era un apasionado del lenguaje, amaba las palabras, afirmaba necesitar leer poesía cada día. escribió y publicó poesía… le gustaba vivir, amaba la vida y lo demostraba.

Como dijo de él otro gran amigo mexicano, Javier Bracho, conocido como Roli,

“Él se hizo solo, vivió y enseñó con la convicción de que la vida es más importante que la ciencia; de hecho, ésta se da sólo cuando hay vida y él era un amante de la vida, disfrutaba todo intensamente y de cualquier cosa sacaba algo humano, profundo, filosófico.”

Este amante de la vida murió durante una plática en el XIX Coloquio de Teoría de las Gráficas, Combinatoria, y sus Aplicaciones, que él organizaba cada año,  mientras se disponía a cambiar una transparencia (acetato) cayó desplomado, frente a una comunidad científica que lo adoraba, el 26 de Febrero de 2004. Desde 2005 dicho coloquio lleva oficialmente su nombre como reconocimiento a su ingente aportación en el área.

No quiero terminar con tristeza esta entrada, es por eso que os recomiendo que echéis un vistazo a estos vídeos maravillosos que Tito Eliatron nos trajo en su blog hace un tiempo, en el que miembros del Instituto de Matemáticas de la Universidad Autónoma de México nos explican qué hace hoy en día un matemático. Y como podréis ver, el espíritu de Neumann sigue en el aire, si escucháis en ese vídeo a Roli (Javier Bracho) o a Luis Montejano diciendo frases como ésta: