Entradas etiquetadas como ‘Teoría de Grafos’

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:

 

 

¡Unamos los pueblos!

Hoy os quisiera plantear un problema de los llamado de optimización, uno de esos problemas que puede parecer, a primera vista, más simple de lo que en realidad es.

Supongamos que tenemos cuatro pueblos cercanos que, por alguna razón, aún no están comunicados entre sí: igual ha pasado un huracán y ha destruido las carreteras que existían o, peor aún, un banco las ha expropiado y se las ha quedado sin saber qué hacer con ellas. Da igual, el caso es que queremos construir carreteras que las unan y estamos en una suposición, por lo tanto, podemos suponer que no nos sobra el dinero y queremos construir la red de carreteras con menos kilómetros, la más económica. El último dato que nos falta es que las ciudades se encuentran formando un cuadrado de lado 10 km. Así tenemos el siguiente diagrama:

En principio, el problema no parece tan difícil, ya que todas los posibles formas de unir los vértices de un cuadrado usando el menor número de carreteras (segmentos de rectas empezando y terminando en ciudades) son los que presentamos a continuación:

Y se puede comprobar que los de la primera fila suman una distancia total de 30 km, los de la segunda (usando el teorema de Pitágoras) de 20+√200 km que son algo más de 34 km. Así que parece claro que gana cualquiera de los diseños de la primera fila. Pero ¿son esas todas las posibles soluciones?

 

En principio no, porque hay otros diseños con la misma longitud que los de la primera fila y que presentan algunas ventajas sobre las anteriores, como las dos que presentamos ahora:

Si nos fijamos estos dos diseños tienen también una longitud de 30 km y la ventaja a la que nos referíamos es que la distancia más larga entre los pueblos es más corta que la distancia más larga en aquellos diseños como el que tenía forma de U: para los de forma de U la distancia más larga posible entre dos pueblos es de 30 km, mientras que en el diseño en H la distancia más larga entre dos pueblos es de 20 km.

Pero todavía lo podemos hacer mejor.  Si consideramos unir cada par de ciudades diagonalmente opuestas por sendas carreteras con un cruce (o una rotonda si tenemos un alcalde al que le gusten mucho: por aquí por el sur, el de Dos Hermanas, por ejemplo), tendremos un diseño en X:

 

La longitud total de esa red de carreteras es poco más de 28 km (de nuevo usando Pitágoras). Y parece que ya no se va a poder mejorar, pero estaremos equivocados

Entonces, ¿tenemos diseño ganador? Pues no, porque podemos modificar ligeramente los diseños en H hasta obtener algo así:

Está demostrado que la longitud mínima se alcanza cuando escogemos los puntos de cruce de las carreteras  de forma que éstas formen un ángulo de 120º en los puntos en los que se bifurcan.

 

Es fácil calcular cómo se ha de escoger el punto en el que las carreteras se bifurcan para que sea óptimo el diseño.

Si nos fijamos  el triángulo ABC es un triángulo rectángulo (el ángulo en C es de 90º) y el ángulo en B debe ser la mitad de 120º , 60º, por lo tanto, puesto que los ángulos internos de un triángulo suman 180º, tenemos que el ángulo en A (en el triángulo ABC) es de 30º. Si hacemos una  copia del triángulo ABC (pegando por el lado AC), y nos fijamos en el triángulo ABB’, éste es un triángulo equilátero (puesto que los ángulos en A, B y B’ son de 60º los 3) y por tanto BC es la mitad de AB, como AC vale 5 km, usando el teorema de Pitágoras tenemos que el lado BC mide 5/ √3 y por lo tanto,  obtenemos que la longitud total de esta red de carreteras es de 10+10√km que es algo más de 27 km y es el ganador absoluto.

Ahora es el momento en el que planteo: ¿y si en vez de cuatro ciudades son tres todas a la misma distancia? ¿Y cinco?

Si queréis ver la solución a estos problemas, se puede este vídeo maravilloso (está en inglés, pero creo que es suficientemente ilustrativo y muy recomendable), donde se da la solución para los distintos casos, pero lo más interesante es que llega a dicha solución con la única ayuda de unas pompas de jabón. Por cierto, esto me da una idea de la que hablaros otro día: de las matemáticas de las pompas de jabón. Pero eso será en otra ocasión.

 

 

El teorema más importante del siglo XX

teorema.

(Del lat. theorēma, y este del gr. θεώρημα).

1. m. Proposición demostrable lógicamente partiendo de axiomas o de otros teoremas ya demostrados, mediante reglas de inferencia aceptadas.

DICCIONARIO DE LA LENGUA ESPAÑOLA – Vigésima segunda edición

 

Ésta es la definición de teorema que encontramos en el Diccionario de la Lengua Española de la R.A.E. Si queremos tratar de explicarlo de una forma más llana y asequible para todos los públicos, podríamos decir que un teorema es un resultado matemático, una afirmación,  de un hecho relevante que se ha demostrado basándose en otros teoremas (anteriormente demostrados) o también en axiomas, que son declaraciones aceptadas por todos.

Estoy segura que todos los que están leyendo esta entrada conocen más de un teorema. Por ejemplo, el famoso teorema de Pitágoras gracias al cual, por ejemplo, podemos calcular la distancia entre 2 puntos en un plano, sin más que conocer sus coordenadas, como ya vimos por aquí hace no mucho tiempo. A lo largo de la historia muchos matemáticos han dedicado sus esfuerzos a demostrar teoremas consiguiendo con ello el avance de las Matemáticas, y como consecuencia, sirviendo de soporte a otras Ciencias,  permitiendo y contribuyendo al avance de nuestra civilización.

Ahora bien, ¿se puede uno plantear hacer una clasificación de teoremas en función de su importancia? ¿Cómo se mide la importancia de un teorema? Parece razonable aceptar que una medida de la importancia de un resultado matemático es la cantidad de veces que éste ha sido utilizado. Pero aunque razonable, es una medida que es imposible determinar, ¿cómo saber cuántas veces se ha utilizado el teorema de Pitágoras desde su prueba hasta nuestros días? No, no se puede calcular.

¿Y si nos restringimos al siglo XX? En el siglo pasado y gracias a las publicaciones científicas, tenemos mejor catalogados los trabajos de matemáticas y de cualquier otra ciencia que fueron publicados. Es por esta razón por lo que la comunidad científica acepta como medida del impacto de un trabajo de investigación el número de veces que éste ha sido citado en otros trabajos. Existen bases da datos que pueden ser consultados por los investigadores para conocer el impacto, es decir, el número de veces que su trabajo o cualquier trabajo, ha sido citado por otros. Si queremos hacer una analogía con redes sociales, en algún sentido y con muchas comillas, es como medir la importancia de un tweet en Twitter por la cantidad de veces que ha sido retuiteado, o en Facebook, por la cantidad de veces que ha sido compartido en los muros de otros.

Henri Poincaré

Alguien podría pensar que en lugar de mirar estos indicadores numéricos, se podrían clasificar los resultados matemáticos acudiendo a la voz de expertos en Matemáticas que los evaluasen en función de criterios tales como dificultad, trascendencia… Pero debido a la diversificación de las Matemáticas, sobre todo en el siglo pasado, no existe ningún matemático que pueda ejercer esta  tarea porque ninguno conoce toda la Matemática, parece ser que fue Poincaré el último matemático que conocía y entendía toda la matemática de su época.

Así las cosas, no nos queda otra opción razonable, si queremos identificar el teorema más importante del siglo XX, que atender al  número de veces que éste ha sido citado en otros trabajos.

Cuando planteas la pregunta «¿cuál es el teorema más importante del siglo XX?» son muchos los que nombran al Último Teorema de Fermat o el Teorema de los 4 Colores, por ejemplo, puesto que han sido éstos dos teoremas, sobre todo el primero, que, independientemente de la importancia del resultado, han sido bastante mediáticos. Sin embargo, ninguno de los 2 ha sido el teorema más importante del siglo pasado si atendemos como medida el número de veces que ha sido citado. Posiblemente debido al hecho de que se demostraron cuando el siglo estaba bastante avanzado: el último teorema de Fermat se demostró en 1995 y el teorema de los 4 colores en 1976.

 

Kazimierz Kuratowski

El teorema del siglo XX que más veces ha sido citado es el Teorema de Kuratowski. Este teorema sirve para caracterizar qué grafos son planos. Ya hablamos en esta misma sección de grafos planos y de este teorema, cuando hablamos del diseño del mapa del metro de Londres. Un grafo es plano si se puede dibujar sin que las líneas que unen a los puntos se corten entre ellas. Si tenemos, por ejemplo, el siguiente grafo, ¿es plano?

Efectivamente, lo es, porque se puede dibujar sin cruces entre las líneas como podemos ver en la figura siguiente:

Pero no siempre es tan inmediato decidir si el grafo es plano o no, porque, por ejemplo, puede tener muchos vértices y muchas conexiones. Lo que asegura el teorema de Kuratowski es que los grafos planos son aquellos que no contienen ni al grafo K5 ni al grafo K 3,3, que son los que aparecen en la figura siguiente.

El hecho de que este teorema haya sido tan citado desde su publicación en 1930 se debe también a la aplicabilidad de la Teoría de Grafos en general y del estudio de la planaridad de los mismos en particular, no sólo al diseño de circuitos como ya comenté anteriormente, sino también en multitud de problemas relacionados con la Informática Gráfica.

Pues bien, el teorema más citado del siglo XX lleva el nombre del matemático polaco Kazimierz Kuratowski por cuestión de días. Dos matemáticos norteamericanos, Orrin Frink y Paul A Smith, demostraron el mismo resultado, independientemente y casi a la vez, pero como el de Kuratowski ya estaba publicado, el trabajo de Frink y Smith nunca se publicó. Se quedaron a las puertas de dejar su nombre al teorema más importante del siglo XX.

Mind the map

 

Hoy vamos a hablar del metro, pero no de tarifazos ni de noticias que nos ponen mal cuerpo, vamos a intentar abstraernos durante unos minutos de la realidad.

Hoy, y ahora que los niños salieron a jugar, vamos a hablar de planos de metro, concretamente del plano del metro de Londres, y de cómo un desconocido  ingeniero consiguió revolucionar parte de los conceptos de diseño en el siglo XX.

 

¿Que qué tiene que ver esto con Matemáticas?

 

Pues, mucho. Es el ejemplo que algunos de los que enseñamos Teoría de Grafos usamos para mostrar a nuestros estudiantes la importancia de la representación, el dibujo, de un grafo.

 

¿Qué es un grafo?

 

De forma coloquial y sencilla, un grafo es un conjunto de elementos, a los que llamaremos vértices, que se relacionan entre ellos por parejas, no necesariamente todos, definiendo lo que llamamos aristas del grafo.

Podemos pensar, por ejemplo que queremos diseñar un circuito con 4 componentes, todas unidos con todas, por parejas. A las componentes, que harán el papel de vértices del grafo, las llamamos en una alarde de originalidad {1, 2, 3, 4}. En ese caso, las conexiones que tenemos que dibujar, que harán el papel de aristas, serán {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}. Al grafo así definido se le conoce como K4.

Vamos a dibujar el circuito. Una posible representación sería ésta.

Está bonita, sí. Pero es que… no queremos que las conexiones se corten entre ellas. Pensamos un poco más el posible diseño del circuito y nos damos cuenta de que si lo pintamos, por ejemplo, como en la siguiente figura, no hay cruce entre las conexiones.

¡Bingo!

Bueno, este circuito ha sido muy fácil y hemos resuelto el problema del cruce de las conexiones sin despeinarnos. Vamos a poner una componente más, una ná más. Tenemos que dibujar 5 vértices, las 5 componentes, {1, 2, 3, 4, 5} y unir cada una de ellas con las otras 4.

Muy mono, sí. Pero, ¿lo podemos dibujar sin cruces?

  Les dejo unos minutos para que lo intenten.

 

 

 

No, no se agobien, no es posible. De hecho es uno de los teoremas más famosos de la Teoría de Grafos, el Teorema de Kuratowski.

 

Hasta aquí espero haberles convencidos de la importancia del dibujo de un grafo como aplicación, por ejemplo, en el diseño de circuito.

 

¿Qué tiene todo esto que ver con el mapa del metro de Londres?

 

Los primeros mapas del metro de Londres eran geográficos, básicamente, consistían en dibujar sobre un plano de la ciudad los recorridos de las distintas líneas.

Mapa del metro de Londres en 1908

Fue Harry Beck, ingeniero electrónico (para que no digan que sólo hablo de matemáticos) empleado en el metro de Londres, el primero que se percató de que al usuario no le interesaba conocer el recorrido del metro bajo tierra, sino simplemente, conocer la posición relativa de las líneas y estaciones para realizar los trasbordos que necesitase.

Se le ocurrió entonces, en 1931, que en realidad, más que un diseño geográfico, lo que resultaría útil sería un diseño topológico, con menos curvas y direcciones en las líneas, y, de broma, hizo su primer diseño basado en los utilizados en circuitos eléctricos. Aún un poco reticentes, lanzaron la idea de Beck entre los usuarios y fue aceptada con entusiasmo por los pasajeros del metro.

Mapa de Beck de 1933

Y hasta hoy, esa idea topológica del mapa de Beck, es la más utilizada en el mundo para este tipo de planos. Esto es, sin tener en cuenta la situación  geográfica de las estaciones en el mapa de la ciudad, salvo su posición respecto al Támesis, en el caso del mapa del metro de Londres.  Incluso hasta en nuestro metro de Sevilla, aunque aquí, sinceramente, aún podríamos permitirnos el geográfico.

 

Plano del metro de Sevilla

Volviendo al de Londres y a la pregunta de que qué tiene que ver el plano de un metro con las Matemáticas, en general, o con la Teoría de Grafos, en particular, pues, eso, que es otro ejemplo más, como el del diseño de circuitos sin cruces,  de la importancia del dibujo de un grafo. Puesto que podemos entender las estaciones como vértices y las líneas como aristas.

De hecho, Beck, a lo largo de su trayectoria, introdujo diversos cambios a su diseño original en pos de conseguir mayor claridad en el plano.

En 1936, entre otros cambios, eliminó curvas y sólo permitió ángulos de 45º y 90º.

Mapa de Beck de 1936

En 1940, le pidieron, entre otros detalles, que incorporase ángulos de 60º también, idea que se desechó posteriormente por enturbiar la claridad del plano.

Mapa de Beck de 1941

Se puede consultar aquí la evolución de los mapas de del metro de Londres y observar qué tipo de modificaciones iban apareciendo siempre para mejorar la usabilidad de los mismos, hasta llegar a la versión actual en la que, como no puede ser de otra manera, se referencia a Harry Beck como creador del diseño. Diseño que habida cuenta de la cantidad de merchandising que ha generado (camisetas, tazas, etc.) debe haber sido uno de los más rentables del siglo pasado, supongo.

Pues todo esto para decidir cómo dibujar las líneas de metro y las distintas estaciones. Pero hay otro problema a la hora de diseñar mapas que es el de poner etiquetas con los nombres, por ejemplo, de las estaciones. Tienen que ser pequeños para que las dimensiones del mapa completo no sean desmesuradas pero lo suficientemente grandes para que el usuario las pueda leer. De este tipo de problemas, del de etiquetado de mapas también se ocupan investigadores matemáticos e informáticos, pero eso se escapa de este café que estamos compartiendo hablando de Beck.

Mapa actual del metro de Tokio

De lo que no hay duda es de que la idea original de Harry Beck, aparte de su utilidad práctica, es también un hermoso ejemplo de arte.

Este mapa, de 2003, está en el London Transport Museum

Yo me bajo en ésta. Hasta la próxima.